SML Fibonacci large number . Using int datatype

Question

I want big int in SML. please let me know direction.

I can make normal fibonacci. but I have to print fibo(100) only using int not intinf.

fun fibo 0 = 0
  | fibo n =
    if n <= 2
    then 1
    else fibo (n-1) + fibo(n-2)

Simon Shine Simon Shine · Accepted Answer · 2016-06-01T09:23:29

I have to print fibo(100)

only using int, not IntInf.int.

To address each of these,

Just printing (and not storing) fibo(100) does not necessarily involve finding a good representation for big numbers, so I would change this goal into "I have to find a way to represent big numbers so I can add them and display them."

But, as John points out, overflowing int values is not your only concern when calculating fibo(100). Just try your naive implementation for fibo(40) or so. It doesn't overflow, but it takes at least a few seconds on my computer. Now try fibo(41), fibo(42), etc. and witness the exponential growth. Your algorithm not only needs a representation of big integers, it also needs a sub-exponential resource usage.

E.g. by making the function tail-recursive:
```
fun fib n =
    let fun fib_ a b 0 = a (* or b *)
          | fib_ a b i = fib_ b (a+b) (i-1)
    in fib_ (Int.toLarge 0) (Int.toLarge 1) n end
```
You're essentially asking how to represent numbers that are bigger than ints using ints only, which, logically, is not possible. But perhaps you mean "by inventing a representation that uses multiple ints in series." That's exactly what IntInf.int does. See for example How to use IntInf or LargeInt in SML?.

A naive imlementation of big integers could keep lists of ints, add them pairwise and carry over when handle Overflow is triggered. Or simply strings of digit characters! But it sounds more like a mental exercise than something useful.