BASIC User Group > Code Challenges

fibonacci(4784969)

<< < (2/22) > >>

John:
I tied to convert a Python version of the Fibonacci code challenge to ScriptBasic but I keep getting a seg fault and not sure why.

--- Code: Python ---fiboA = 0fiboB = 0def Fibonacci(n):  global fiboA  global fiboB  if n == 0:    fiboA = 0    fiboB = 1    return 0  Fibonacci(n // 2)  if (n % 2) == 0 :    t = fiboB + fiboB - fiboA    fiboA = fiboA * t    fiboB = fiboB * t    if ( n % 4 ) == 0 : fiboB = fiboB - 1    else              : fiboB = fiboB + 1  else:    t = fiboA + fiboA + fiboB    fiboA = fiboA * t    fiboB = fiboB * t    if (n % 4) == 1 : fiboA = fiboA + 1    else            : fiboA = fiboA - 1  return fiboA print Fibonacci(24) # => 46368

jrs@jrs-laptop:~/sb/examples/test\$ time python hippy.py
46368

real   0m0.025s
user   0m0.020s
sys   0m0.005s
jrs@jrs-laptop:~/sb/examples/test\$

print(Fast_Fibonacci(4784969))

real   0m35.497s
user   0m35.186s
sys   0m0.025s
jrs@jrs-laptop:~/sb/examples/test\$

--- Code: Script BASIC ---fiboA = 0fiboB = 0function Fast_Fibonacci(n)  if n = 0 then    fiboA = 0    fiboB = 1    Fast_Fibonacci = 0  end if  Fast_Fibonacci(n\2)  if (n % 2) = 0 then    t = fiboB + fiboB - fiboA    fiboA *= t    fiboB *= t    if (n % 4) = 0 then      fiboB -= 1    else      fiboB += 1    end if  else    t = fiboA + fiboA + fiboB    fiboA *= t    fiboB *= t    if (n % 4) = 1 then      fiboA += 1    else      fiboA -= 1    end if  end if  Fast_Fibonacci = fiboAend function ' print(Fast_Fibonacci(4784969)) print Fast_Fibonacci(24),"\n"
Any ideas?

John:
Seems I had a typo in my code.

--- Code: Script BASIC ---fiboA = 0fiboB = 0function Fibonacci(n)  if n then    Fibonacci(n \ 2)    if n and 1 then      t = fiboA + fiboA + fiboB      fiboA *= t      fiboB *= t      if (n and 3) = 1 then        fiboA += 1      else        fiboA -= 1      end if    else      t = fiboB + fiboB - fiboA      fiboA *= t      fiboB *= t      if n and 3 then        fiboB += 1      else        fiboB -= 1      end if    end if  else    fiboA = 0    fiboB = 1  end if  Fibonacci = fiboAend function print Fibonacci(24),"\n"
jrs@jrs-laptop:~/sb/examples/test\$ time scriba hippy.sb
46368

real   0m0.011s
user   0m0.007s
sys   0m0.004s
jrs@jrs-laptop:~/sb/examples/test\$ time scriba hippy.sb    <-- Fibonacci(4784969)
-nan

real   0m0.010s
user   0m0.004s
sys   0m0.006s
jrs@jrs-laptop:~/sb/examples/test\$

AIR:
Another way of doing it in Python.  I didn't write this, and don't fully understand all the calculations (I think it uses a MATRIX), but it's the fastest implementation I found.

--- Code: Python ---#!/usr/bin/env python def fib(n):    v1, v2, v3 = 1, 1, 0      for rec in bin(n)[3:]:         calc = v2*v2        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2    return v2 res = fib(4784969)
On my Macbook Pro, 2.5Ghz 4 Core i7:
\$ time ./fibo.py

real   0m1.100s
user   0m1.080s
sys   0m0.016s

On my RasPi:
\$ time ./fibo.py

real   0m25.947s
user   0m25.894s
sys   0m0.050s

AIR.

John:
The best ScriptBasic can do on 64 bit is Fibonacci(92) without overflowing  MAXINT.

Time:  0.009 seconds.

AIR:
Jali,

Can you code this so that it outputs the actual Fibonacci number for 1000000?