first & last digits of Fib 2^32

[jack]

see https://rosettacode.org/wiki/Fibonacci_matrix-exponentiation
due to the limits of double and integer I present a version that computes the first 7 and last 9 digits of fib 2^32

Code: QB64: [Select]

1. _Title "Fibon"
2. Dim As _Unsigned _Integer64 last9, fn
3. Dim As Double f
4. Dim As String s
5. Dim As Long c
6.  
7. fn = 4294967296 '2^32
8. m = 1000000000 '10^9
9.  
10. 'using the Binet formula for the Fib number  ( ( (1+sqr(5))/2 )^n - ( (1-sqr(5))/2 )^n )/sqr(5)
11. 'the apprximation of which is the nearest integer of ( ((1+sqr(5))/2)^n )/sqr(5)
12. 'we take the Log10 of the last expression log10((1+sqr(5))/2)*n)-log10(sqr(5)
13. '10^FractionalPart is approximately equal the the fib number, the integer part is the exponent
14. f = ((Log((1 + Sqr(5)) / 2) * fn) - Log(Sqr(5))) / Log(10)
15. f = f - Fix(f) 'Fractional part
16. f = 10## ^ f
17. s = _Trim$(Str$(f))
18. c = InStr(s, ".")
19. s = Left$(s, c - 1) + Mid$(s, c + 1)
20. s = Left$(s, 7)
21. last9 = fib(fn, m)
22. Print "the first"; Len(s); " digits of Fibonacci "; fn; " are "; s
23. Print "the last"; Len(_Trim$(Str$(last9))); " digits of Fibonacci "; fn; " are "; last9
24.  
25. Function fib~&& (k As _Unsigned _Integer64, m As _Unsigned _Integer64)
26.     Dim As _Unsigned _Integer64 b, x, y, xx, temp
27.     Dim As Long i, bit_length
28.     If k <= 1 Then
29.         fib = k
30.         Exit Function
31.     End If
32.     b = k
33.     x = 1: y = 0
34.     bit_length = Fix(Log(k) / Log(2)) 'Log2(n) giges the highest bit set of an integer
35.     For i = bit_length - 1 To 0 Step -1
36.         xx = x * x Mod m
37.         x = (xx + 2 * x * y) Mod m
38.         y = (xx + y * y) Mod m
39.         If b And 1 Then 'if the least significant bit is 1 then
40.             temp = x
41.             x = (x + y) Mod m
42.             y = temp
43.         End If
44.         b = b \ 2 'chop off the least significant bit for the next test
45.     Next
46.     fib = x
47. End Function
48.