Unhandled exception: Arithmetic overflow (OverflowError)

Help & Support
1 
def fib(n)
  if n <= 1
    1
  else
    fib(n - 1) + fib(n - 2)
  end
end

puts fib(49)
---------------
Unhandled exception: Arithmetic overflow (OverflowError)
  from fib.cr:5:16 in 'fib'
  from fib.cr:5:5 in 'fib'
  from fib.cr:5:5 in 'fib'
  from fib.cr:5:5 in 'fib'
  from fib.cr:9:6 in '__crystal_main'
  from /usr/share/crystal/src/crystal/main.cr:129:5 in 'main_user_code'
  from /usr/share/crystal/src/crystal/main.cr:115:7 in 'main'
  from /usr/share/crystal/src/crystal/main.cr:141:3 in 'main'
  from /lib/x86_64-linux-gnu/libc.so.6 in '__libc_start_main'
  from ./fib in '_start'
  from ???

How can I fix it? Many thx!

2

Crystal auto reduce the return value as Int32, but fib(49) is far far large than a 32 bit integer.
you have to specify the correct type manually, as following:

require "big"

def fib(n) : BigInt
  if n <= 1
    1.to_big_i
  else
    (fib(n - 1) + fib(n - 2)).to_big_i
  end
end

puts fib(49)

# => 12586269025

But, use BigInt has a side effect, it is far far slow than Int32, please always specify exact limit type instead of the arbitrarily large integers.

1 Like
3

Thx friend!

4

FYI, the Fibonacci series starts: 0, 1, 1, 2, 3, … not from 1.

So do:

def fib(n)
  if n < 2
    n
 else....
1 Like
5

By the way, I found it there Fibonacci benchmark - The Crystal Programming Language

6

Yeh, you’ll see that error in allot of code, but it’s mathematically incorrect.
It throws the correct F(n) values off by 1 position.