Fibonacci matrix-exponentiation: Difference between revisions
No edit summary |
No edit summary |
||
Line 23: | Line 23: | ||
Display only the 20 first digits and 20 last digits of each Fibonacci number. |
Display only the 20 first digits and 20 last digits of each Fibonacci number. |
||
;Extra: |
;Extra: |
||
Line 33: | Line 34: | ||
* [[Fibonacci sequence]] |
* [[Fibonacci sequence]] |
||
* [[Matrix-exponentiation operator]] |
* [[Matrix-exponentiation operator]] |
||
=={{header|Julia}}== |
|||
Because Julia uses the GMP library for its BigInt type, a BigInt cannot be larger in bits than about 2^37. This prevents generation of |
|||
the 2^64-th fibonacchi number, due to BigInt overflow. The Binet method actually overflows even with the 2^32-rd fibonacchi number, so the |
|||
Lucas method is used as the alternative method. |
|||
<lang julia>const b = [big"1" 1; 1 0] |
|||
matrixfibonacci(n) = n == 0 ? 0 : n == 1 ? 1 : (b^(n+1))[2,2] |
|||
# This is derived from the Schönhage-Strassen algorithm using Lucas numbers |
|||
function lucasfibonacci(n) |
|||
function inner(n) |
|||
if n == 0 |
|||
return zero(n), one(n) |
|||
end |
|||
u, v = inner(n >> 1) |
|||
q = (n & 2) - 1 |
|||
u *= u |
|||
v *= v |
|||
if isodd(n) |
|||
return u + v, 3 * v - 2 * (u - q) |
|||
end |
|||
return BigInt(2 * (v + q) - 3 * u), BigInt(u + v) |
|||
end |
|||
u, v = inner(n >> 1) |
|||
l = 2*v - u # the lucas function |
|||
if isodd(n) |
|||
q = (n & 2) - 1 |
|||
return v * l + q |
|||
end |
|||
return u * l |
|||
end |
|||
m2s(bits) = string(matrixfibonacci(big"2"^bits)) |
|||
l2s(bits) = string(lucasfibonacci(big"2"^bits)) |
|||
firstlast(s) = (length(s) < 44 ? s : s[1:20] * "..." * s[end-20+1:end]) |
|||
println("N", " "^23, "Matrix", " "^40, "Lucas\n", "-"^97) |
|||
println("2^32 ", rpad(firstlast(m2s(32)), 45), rpad(firstlast(l2s(32)), 45)) |
|||
# println("2^64 ", rpad(firstlast(m2s(44)), 45), rpad(firstlast(l2s(44)), 45)) |
|||
</lang>{{out}} |
|||
<pre> |
|||
N Matrix Lucas |
|||
------------------------------------------------------------------------------------------------- |
|||
2^32 61999319689381859818...39623735538208076347 61999319689381859818...39623735538208076347 |
|||
</pre> |
Revision as of 17:25, 31 January 2020
The Fibonacci sequence defined with matrix-exponentiation:
F0 = 0 F1 = 1
- Task
Write a function using matrix-exponentiation to generate Fibonacci number for n = 232 and n = 264.
Display only the 20 first digits and 20 last digits of each Fibonacci number.
- Extra
Generate the same Fibonacci numbers using Binet's formula below or another method.
- Related tasks
Julia
Because Julia uses the GMP library for its BigInt type, a BigInt cannot be larger in bits than about 2^37. This prevents generation of the 2^64-th fibonacchi number, due to BigInt overflow. The Binet method actually overflows even with the 2^32-rd fibonacchi number, so the Lucas method is used as the alternative method.
<lang julia>const b = [big"1" 1; 1 0] matrixfibonacci(n) = n == 0 ? 0 : n == 1 ? 1 : (b^(n+1))[2,2]
- This is derived from the Schönhage-Strassen algorithm using Lucas numbers
function lucasfibonacci(n)
function inner(n) if n == 0 return zero(n), one(n) end u, v = inner(n >> 1) q = (n & 2) - 1 u *= u v *= v if isodd(n) return u + v, 3 * v - 2 * (u - q) end return BigInt(2 * (v + q) - 3 * u), BigInt(u + v) end u, v = inner(n >> 1) l = 2*v - u # the lucas function if isodd(n) q = (n & 2) - 1 return v * l + q end return u * l
end
m2s(bits) = string(matrixfibonacci(big"2"^bits)) l2s(bits) = string(lucasfibonacci(big"2"^bits)) firstlast(s) = (length(s) < 44 ? s : s[1:20] * "..." * s[end-20+1:end])
println("N", " "^23, "Matrix", " "^40, "Lucas\n", "-"^97) println("2^32 ", rpad(firstlast(m2s(32)), 45), rpad(firstlast(l2s(32)), 45))
- println("2^64 ", rpad(firstlast(m2s(44)), 45), rpad(firstlast(l2s(44)), 45))
</lang>
- Output:
N Matrix Lucas ------------------------------------------------------------------------------------------------- 2^32 61999319689381859818...39623735538208076347 61999319689381859818...39623735538208076347