SML fibonacci large numbers

Question

I tried to write my own fib function that works for large numbers (over 50) and I had no luck. First I tried the obvious solution but that overflows way to quicly. my next solution was this

    $fun fib(a:int, b:int, index:int) = if(index = 1) then
    $                                      (a+b)
    $                                   else
    $                                       fib(b, (a+b), index - 1);

Unfortunatly this also overflows.

Sebastian Paaske Tørholm · Accepted Answer · 2012-09-07 22:41:59Z

4

You need to take a look at the IntInf module, which provides access to arbitrary precision integers.

You can convert from Int.int to IntInf.int using IntInf.fromInt.

Note, for any operations you do on them, you have to use IntInf.<operation> instead of the Int counterpart. This includes things like addition and the likes.

edited Sep 7, 2012 at 22:41

answered Sep 7, 2012 at 22:36

Sebastian Paaske Tørholm

51.3k11 gold badges103 silver badges123 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Katianie Over a year ago

so replace "int" with IntInf?

Makarius · Accepted Answer · 2013-03-01 15:35:32Z

0

Note that in Poly/ML, both structure Int and IntInf offer unbounded (big) integers by default. Since the implementation uses the GNU MP library at the bottom if it, and small machine integers in the range where this is still possible, it is also quite fast.

answered Mar 1, 2013 at 15:35

Makarius

2,24421 silver badges20 bronze badges

Collectives™ on Stack Overflow

SML fibonacci large numbers

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related