Fibonacci problem causes Arithmetic overflow

user_130639 0
Viewed 192

The problem: create a function with one input. Return the index of an array containing the fibonacci sequence (starting from 0) whose element matches the input to the function.

  16 ~ │ def fib(n)
  17 ~ │   return 0 if n == 0
  18   │ 
  19 ~ │   last    = 0u128
  20 ~ │   current = 1u128
  21   │ 
  22 ~ │   (n - 1).times do
  23 ~ │     last, current = current, last + current
  24   │   end
  25 + │ 
  26 + │   current
  27   │ end
  28   │
  60   │ def usage
  61   │   progname = String.new(ARGV_UNSAFE.value)
  62   │ 
  63   │   STDERR.puts <<-H
  64   │   #{progname} <integer>
  65   │     Given Fibonacci; determine which fib value would
  66   │     exist at <integer> index.
  67   │   H
  68   │ 
  69   │   exit 1
  70   │ end
  71   │ 
  72   │ if ARGV.empty?
  73   │   usage
  74   │ end
  75   │ 
  76   │ begin
  77 ~ │   i = ARGV[0].to_i
  78 ~ │   puts fib i
  79   │ rescue e
  80   │   STDERR.puts e
  81   │   usage
  82   │ end

My solution to the problem is in no way elegant and I did it at 2AM when I was quite tired. So I'm not looking for a more elegant solution. What I am curious about is that if I run the resultant application with an input larger than 45 then I'm presented with Arithmetic overflow. I think I've done something wrong with my variable typing. I ran this in Ruby and it runs just fine so I know it's not a hardware issue...

Could someone help me find what I did wrong in this? I'm still digging, too. I just started working with Crystal this week. This is my second application/experiment with it. I really like, but I am not yet aware of some of its idiosyncrasies.

EDIT

Updated script to reflect suggested change and outcome of runtime from said change. With said change, I can now run the program successfully over the number 45 now but only up to about low 90s. So that's interesting. I'm gonna run through this and see where I may need to add additional explicit casting. It seems very unintuitive that changing the type at the time of initiation didn't "stick" through the entire runtime, which I tried first and that failed. Something doesn't make sense here to me.

Original Results

$ crystal build fib.cr
$ ./fib 45
1836311903
$ ./fib 46
Arithmetic overflow
$ ./fib.rb 460
985864329041134079854737521712801814394706432953315\
510410398508752777354792040897021902752675861

Latest Results

$ ./fib 92
12200160415121876738
$ ./fib 93
Arithmetic overflow
./fib <integer>
  Given Fibonacci; determine which fib value would
  exist at <integer> index.

Edit ^2

Now also decided that maybe ARGV[0] is the problem. So I changed the call to f() to:

 62 begin                                                                                                                                                                           
 63   i = ARGV[0].to_u64.as(UInt64)                                                                                                                                                 
 64   puts f i                                                                                                                                                                      
 65 rescue e                                                                                                                                                                        
 66   STDERR.puts e                                                                                                                                                                 
 67   usage                                                                                                                                                                         
 68 end

and added a debug print to show the types of the variables in use:

22   return 0 if p == 0                                                                                                                                                            
 23                                                                                                                                                                                 
 24   puts "p: %s\tfib_now: %s\tfib_last: %s\tfib_hold: %s\ti: %s" % [typeof(p), typeof(fib_now), typeof(fib_last), typeof(fib_hold), typeof(i)]                                    
 25   loop do

p: UInt64       fib_now: UInt64 fib_last: UInt64        fib_hold: UInt64        i: UInt64
Arithmetic overflow
./fib <integer>
  Given Fibonacci; determine which fib value would
  exist at <integer> index.

Edit ^3

Updated with latest code after bug fix solution by Jonne. Turns out the issue is that I'm hitting the limits of the structure even with 128 bit unsigned integers. Ruby handles this gracefully. Seems that in crystal, it's up to me to gracefully handle it.

crystal-lang
2 Answers

The default integer type in Crystal is Int32, so if you don't explicitly specify the type of an integer literal, you get that.

In particular the lines

fib_last = 0
fib_now  = 1

turn the variables into the effective type Int32. To fix this, make sure you specify the type of these integers, given you don't need negative numbers, UInt64 seems most appropriate here:

fib_last = 0u64
fib_now  = 1u64

Also note the the literal syntax I'm using here. Your 0.to_i64's create an In32 and then an Int64 out of that. The compiler will be smart enough to do this conversion at compile time in release builds, but I think it's nicer to just use the literal syntax.

Edit answering to to the updated question

Fibonacci is defined as F0 = 0, F1 = 1, Fn = Fn-2 + Fn-1, so 0, 1, 1, 2, 3, 5. Your algorithm is off by one. It calculates Fn+1 for a given n > 1, in other words 0, 1, 2, 3, 5, in yet other words it basically skips F2.

Here's one that does it correctly:

def fib(n)
  return 0 if n == 0

  last = 0u64
  current = 1u64

  (n - 1).times do
    last, current = current, last + current
  end

  current
end

This correctly gives 7540113804746346429 for F92 and 12200160415121876738 for F93. However it still overflows for F94 because that would be 19740274219868223167 which is bigger than 264 = 18446744073709551616, so it doesn't fit into UInt64. To clarify once more, your version tries to calculate F94 when being asked for F93, hence you get it "too early".

So if you want to support calculating Fn for n > 93 then you need to venture into the experimental Int128/UInt128 support or use BigInt.

user_21996870

I think one more thing should be mentioned to explain the Ruby/Crystal difference, besides the fact that integer literals default to Int32.

In Ruby, a dynamically typed interpreted language, there is no concept of variable type, only value type. All variables can hold values of any type.
This allows it to transparently turn a Fixnum into a Bignum behind the scenes when it would overflow.

Crystal on the contrary is a statically typed compiled language, it looks and feels like Ruby thanks to type inference and type unions, but the variables themselves are typed.
This allows it to catch a large number of errors at compile time and run Ruby-like code at C-like speed.

I think, but don't take my word for it, that Crystal could in theory match Ruby's behavior here, but it would be more trouble than good. It would require all operations on integers to return a type union with BigInt, at which point, why not leave the primitive types alone, and use big integers directly when necessary.

Long story short, if you need to work with very large integer values beyond what an UInt128 can hold, require "big" and declare the relevant variables BigInt.

edit: see also here for extreme cases, apparently BigInts can overflow too (I never knew) but there's an easy remedy.

user_155231600
Related