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.
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.