## first & last digits of Fibonacci 2^32

General FreeBASIC programming questions.
srvaldez
Posts: 3060
Joined: Sep 25, 2005 21:54

### first & last digits of Fibonacci 2^32

see https://rosettacode.org/wiki/Fibonacci_ ... nentiation
due to the limits of double and integer I present here a program that computes the first 7 and last 9 digits of Fib(2^32)
this is a translation of a program found on page 14 of https://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf written in Aribas https://www.mathematik.uni-muenchen.de/ ... ribas.html

Code: Select all

' https://rosettacode.org/wiki/Fibonacci_matrix-exponentiation
/'------------------------------------------------------------------'/
/'
** Schnelle Berechnung der Fibonacci-Zahlen mittels der Formeln
** fib(2*k-1) = fib(k)**2 + fib(k-1)**2
** fib(2*k) = fib(k)**2 + 2*fib(k)*fib(k-1)
**
** Dabei werden alle Berechnungen mod m durchgef¨uhrt
'/
Function fib(Byval k As Ulongint, Byval m As Ulongint) As Ulongint
Dim As Ulongint x, y, xx, temp
Dim As Integer i, bit_length
If k <= 1 Then Return k
x = 1: y = 0
bit_length=Fix(Log(k)/Log(2))
For i = bit_length-1 To 0 Step -1
xx = x*x Mod m
x = (xx + 2*x*y) Mod m
y = (xx + y*y) Mod m
If Bit(k,i) Then
temp = x
x = (x + y) Mod m
y = temp
End If
Next
Return x
End Function

Dim As Ulongint last9, fn=4294967296ull, m=1000000000ull
Dim As Double t
Dim As String s
Dim As Long c

t=Timer
s=Trim(Str(10^Frac(((Log((1+Sqr(5))/2)*fn)-log(Sqr(5)))/Log(10))))
c=Instr(s, ".")
s=Left(s, c-1)+Mid(s, c+1)
s=Left(s,7)
last9=fib(fn, m)
Print "the first";Len(s);" digits of Fibonacci ";fn;" are ";s
Print "the last";Len(Trim(Str(last9)));" digits of Fibonacci ";fn;" are ";last9
t=timer-t
Print "time taken is";t;" seconds"
Sleep