Fibonacci matrix-exponentiation: Difference between revisions

</pre>

=={{header|Wren}}==

===Matrix exponentation===

{{trans|Go}}

{{libheader|Wren-big}}

{{libheader|Wren-fmt}}

A tough task for Wren which takes just under 3 minutes to process even the 1 millionth Fibonacci number. Judging by the times for the compiled, statically typed languages using GMP, the 10 millionth would likely take north of 4 hours so I haven't attempted it.

<lang ecmascript>import "/big" for BigInt

import "/fmt" for Fmt

var mul = Fn.new { |m1, m2|

var rows1 = m1.count

var cols1 = m1[0].count

var rows2 = m2.count

var cols2 = m2[0].count

if (cols1 != rows2) Fiber.abort("Matrices cannot be multiplied.")

var result = List.filled(rows1, null)

for (i in 0...rows1) {

result[i] = List.filled(cols2, null)

for (j in 0...cols2) {

result[i][j] = BigInt.zero

for (k in 0...rows2) {

var temp = m1[i][k] * m2[k][j]

result[i][j] = result[i][j] + temp

}

}

}

return result

}

var identityMatrix = Fn.new { |n|

if (n < 1) Fiber.abort("Size of identity matrix can't be less than 1")

var ident = List.filled(n, 0)

for (i in 0...n) {

ident[i] = List.filled(n, null)

for(j in 0...n) ident[i][j] = (i != j) ? BigInt.zero : BigInt.one

}

return ident

}

var pow = Fn.new { |m, n|

var le = m.count

if (le != m[0].count) Fiber.abort("Not a square matrix")

if (n < 0) Fiber.abort("Negative exponents not supported")

if (n == 0) return identityMatrix.call(le)

if (n == 1) return m

var pow = identityMatrix.call(le)

var base = m

var e = n

while (e > 0) {

var temp = e & BigInt.one

if (temp == BigInt.one) pow = mul.call(pow, base)

e = e >> 1

base = mul.call(base, base)

}

return pow

}

var fibonacci = Fn.new { |n|

if (n == 0) return BigInt.zero

var m = [[BigInt.one, BigInt.one], [BigInt.one, BigInt.zero]]

m = pow.call(m, n - 1)

return m[0][0]

}

var n = BigInt.zero

var i = 10

while (i <= 1e6) {

n = BigInt.new(i)

var s = fibonacci.call(n).toString

Fmt.print("The digits of the $,sth Fibonacci number ($,s) are:", i, s.count)

if (s.count > 20) {

Fmt.print(" First 20 : $s", s[0...20])

if (s.count < 40) {

Fmt.print(" Final $-2d : $s", s.count-20, s[20..-1])

} else {

Fmt.print(" Final 20 : $s", s[s.count-20..-1])

}

} else {

Fmt.print(" All $-2d : $s", s.count, s)

}

System.print()

i = i * 10

}

n = BigInt.one << 16

var s = fibonacci.call(n).toString

Fmt.print("The digits of the 2^16th Fibonacci number ($,s) are:", s.count)

Fmt.print(" First 20 : $s", s[0...20])

Fmt.print(" Final 20 : $s", s[s.count-20..-1])</lang>

{{out}}

<pre>

The digits of the 10th Fibonacci number (2) are:

All 2 : 55

The digits of the 100th Fibonacci number (21) are:

First 20 : 35422484817926191507

Final 1 : 5

The digits of the 1,000th Fibonacci number (209) are:

First 20 : 43466557686937456435

Final 20 : 76137795166849228875

The digits of the 10,000th Fibonacci number (2,090) are:

First 20 : 33644764876431783266

Final 20 : 66073310059947366875

The digits of the 100,000th Fibonacci number (20,899) are:

First 20 : 25974069347221724166

Final 20 : 49895374653428746875

The digits of the 1,000,000th Fibonacci number (208,988) are:

First 20 : 19532821287077577316

Final 20 : 68996526838242546875

The digits of the 2^16th Fibonacci number (13,696) are:

First 20 : 73199214460290552832

Final 20 : 97270190955307463227

</pre>

<br>

===Lucas method===

{{trans|Go}}

Much quicker than the matrix exponentiation method taking about 23 seconds to process the 1 millionth Fibonacci number and around 32 minutes to reach the 10 millionth.

Apart from the 2^16th number, the extra credit is still out of reach using this approach and unfortunately the Fibmod method is not available as Wren doesn't currently have a suitable library for arbitrary precision floating point calculations.

<lang ecmascript>import "/big" for BigInt

import "/fmt" for Fmt

var lucas = Fn.new { |n|

var inner // recursive function

inner = Fn.new { |n|

if (n == BigInt.zero) return [BigInt.zero, BigInt.one]

var t = n >> 1

var res = inner.call(t)

var u = res[0]

var v = res[1]

t = n & BigInt.two

var q = t - BigInt.one

var r = BigInt.zero

u = u.square

v = v.square

t = n & BigInt.one

if (t == BigInt.one) {

t = u - q

t = BigInt.two * t

r = BigInt.three * v

return [u + v, r - t]

} else {

t = BigInt.three * u

r = v + q

r = BigInt.two * r

return [r - t, u + v]

}

}

var t = n >> 1

var res = inner.call(t)

var u = res[0]

var v = res[1]

var l = BigInt.two * v

l = l - u // Lucas function

t = n & BigInt.one

if (t == BigInt.one) {

var q = n & BigInt.two

q = q - BigInt.one

t = v * l

return t + q

}

return u * l

}

var n = BigInt.zero

var i = 10

while (i <= 1e7) {

n = BigInt.new(i)

var s = lucas.call(n).toString

Fmt.print("The digits of the $,sth Fibonacci number ($,s) are:", i, s.count)

if (s.count > 20) {

Fmt.print(" First 20 : $s", s[0...20])

if (s.count < 40) {

Fmt.print(" Final $-2d : $s", s.count-20, s[20..-1])

} else {

Fmt.print(" Final 20 : $s", s[s.count-20..-1])

}

} else {

Fmt.print(" All $-2d : $s", s.count, s)

}

System.print()

i = i * 10

}

n = BigInt.one << 16

var s = lucas.call(n).toString

Fmt.print("The digits of the 2^16th Fibonacci number ($,s) are:", s.count)

Fmt.print(" First 20 : $s", s[0...20])

Fmt.print(" Final 20 : $s", s[s.count-20..-1])</lang>

{{out}}

As matrix exponentiation method, plus:

<pre>

The digits of the 10,000,000th Fibonacci number (2,089,877) are:

First 20 : 11298343782253997603

Final 20 : 86998673686380546875