Print Page - first & last digits of Fib 2^32

_Title "Fibon"
Dim As _Unsigned _Integer64 last9, fn
Dim As Double f
Dim As String s
Dim As Long c
fn = 4294967296 '2^32
m = 1000000000 '10^9
'using the Binet formula for the Fib number ( ( (1+sqr(5))/2 )^n - ( (1-sqr(5))/2 )^n )/sqr(5)
'the apprximation of which is the nearest integer of ( ((1+sqr(5))/2)^n )/sqr(5)
'we take the Log10 of the last expression log10((1+sqr(5))/2)*n)-log10(sqr(5)
'10^FractionalPart is approximately equal the the fib number, the integer part is the exponent
f = ((Log((1 + Sqr(5)) / 2) * fn) - Log(Sqr(5))) / Log(10)
f = f - Fix(f) 'Fractional part
f = 10## ^ f
s = _Trim$(Str$(f))
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
Function fib~&& (k As _Unsigned _Integer64, m As _Unsigned _Integer64)
Dim As _Unsigned _Integer64 b, x, y, xx, temp
Dim As Long i, bit_length
If k <= 1 Then
fib = k
Exit Function
End If
b = k
x = 1: y = 0
bit_length = Fix(Log(k) / Log(2)) 'Log2(n) giges the highest bit set of an integer
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 b And 1 Then 'if the least significant bit is 1 then
temp = x
x = (x + y) Mod m
y = temp
End If
b = b \ 2 'chop off the least significant bit for the next test
Next
fib = x
End Function

QB64.org Forum