first & last digits of Fibonacci 2^32

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

first & last digits of Fibonacci 2^32

Post by srvaldez »

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
Post Reply