Revision history [back]

The following works without any Cython (but I do not know what you mean with the "Knuth matrices")

sage: m = matrix(2, [1,1,1,0])
sage: all((m**i)[0,0] == fibonacci(i+1) for i in range(10))
True
sage: A = m **1000000000    # needs some seconds
sage: A[0,0].ndigits()
208987641

In the background the above code uses link text which performs very well with integers.

The following works without any Cython in 26s (but I do not know what you mean with the "Knuth matrices")

sage: m = matrix(2, [1,1,1,0])
sage: all((m**i)[0,0] == fibonacci(i+1) for i in range(10))
True
sage: %time A = m **1000000000    # needs some seconds
**999999999
CPU times: user 25.5 s, sys: 688 ms, total: 26.2 s
Wall time: 26.2 s
sage: A[0,0].ndigits()
208987641
208987640

In the background the above code uses link textflint which performs very well with integers.

The following works without any Cython in 26s (but I do not know what you mean with the "Knuth matrices")

sage: m = matrix(2, [1,1,1,0])
sage: all((m**i)[0,0] == fibonacci(i+1) for i in range(10))
True
sage: %time A = m **999999999
CPU times: user 25.5 s, sys: 688 ms, total: 26.2 s
Wall time: 26.2 s
sage: A[0,0].ndigits()
208987640

You can also check that the second columns are previous Fibonacci numbers:

sage: A[1,0] + A[1,1] == A[0,0]
True

In the background the above code integer matrices in Sage uses flint which performs very well with integers.well.

The following works without any Cython in 26s (but I do not know what you mean with the "Knuth matrices")

sage: m = matrix(2, [1,1,1,0])
sage: all((m**i)[0,0] == fibonacci(i+1) for i in range(10))
True
sage: %time A = m **999999999
CPU times: user 25.5 s, sys: 688 ms, total: 26.2 s
Wall time: 26.2 s
sage: A[0,0].ndigits()
208987640

You can also check that the second columns are previous Fibonacci numbers:

sage: A[0,1] == A[1,0]
True
sage: A[1,0] + A[1,1] == A[0,0]
True

In the background the integer matrices in Sage uses flint which performs very well.

The following works without any Cython in 26s (but I do not know what you mean with the "Knuth matrices")

sage: m = matrix(2, [1,1,1,0])
sage: all((m**i)[0,0] == fibonacci(i+1) for i in range(10))
True
sage: %time A = m **999999999
CPU times: user 25.5 s, sys: 688 ms, total: 26.2 s
Wall time: 26.2 s
sage: A[0,0].ndigits()
208987640

You can also check that the second columns are previous Fibonacci numbers:

sage: A[0,1] == A[1,0]
True
sage: A[1,0] + A[1,1] == A[0,0]
True

In the background the integer matrices in Sage uses flint which performs very well.

sage: s = RIF(5).sqrt()
sage: a = log(1/s) + 1000000000 * log((1+s)/2)
sage: b = a / RIF(10).log()
sage: b.unique_ceil()
208987640