Tail Recursion with Codon

[w-witt]

Hello,

So I took the Fibonacci code given:

from time import time

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

t0 = time()
ans = fib(40)
t1 = time()
print(f'Computed fib(40) = {ans} in {t1 - t0} seconds.')

I got the following results for the 50th number:

$ python3 fib.py 
Computed fib(50) = 12586269025 in 1055.9128770828247 seconds.

$ codon run -release fib.py
Computed fib(50) = 12586269025 in 33.1529 seconds.

I then attempted to rewrite the code using tail recursion. Given as:

from time import time

def fib_tail(n, a=0, b=1):
    if n == 0:
        return a
    else:
        return fib_tail(n - 1, b, a + b)

t0 = time()
ans = fib_tail(40)
t1 = time()
print(f'Computed fib(40) = {ans} in {t1 - t0} seconds.')

I then evaluated different values (40-100) and compared the runtime with Codon's runtime. What I found was that at the value of 100, the codon compiles and outputs the wrong value for the 100th Fibonacci number. Below are the outputs of python vs codon runtimes:

$ python3 fib_tail.py
Computed fib(50) = 12586269025 in 4.0531158447265625e-06 seconds.

$ codon run -release fib_tail.py
Computed fib(50) = 12586269025 in 0 seconds.

$ python3 fib_tail.py           
Computed fib(60) = 1548008755920 in 5.0067901611328125e-06 seconds.

$ codon run -release fib_tail.py
Computed fib(60) = 1548008755920 in 0 seconds.

$ python3 fib_tail.py           
Computed fib(70) = 190392490709135 in 6.9141387939453125e-06 seconds.

$ codon run -release fib_tail.py
Computed fib(70) = 190392490709135 in 0 seconds.

$ python3 fib_tail.py           
Computed fib(80) = 23416728348467685 in 7.867813110351562e-06 seconds.

$ codon run -release fib_tail.py
Computed fib(80) = 23416728348467685 in 0 seconds.

$ python3 fib_tail.py           
Computed fib(90) = 2880067194370816120 in 7.867813110351562e-06 seconds.

$ codon run -release fib_tail.py 
Computed fib(90) = 2880067194370816120 in 0 seconds.

$ python3 fib_tail.py            
Computed fib(100) = 354224848179261915075 in 6.9141387939453125e-06 seconds.

$ codon run -release fib_tail.py
Computed fib(100) = 3736710778780434371 in 0 seconds.

[elisbyberi]

https://docs.exaloop.io/language/overview/#data-types

Codon's int is a 64-bit signed integer, whereas Python's (after version 3) can be arbitrarily large.

fib(100) is too large.