Ask Your Question

def type of mpmath matrices in cython

asked 2015-11-30 19:43:17 +0200

Cython curious gravatar image

I'm trying to speed up the exact iterative calculation of the 1E9 th Fibonacci number, which has 208987640 digits. Working with Python and mpmath I've reached an acceptable time, but I'm looking to further reduce it using Cython. In this case the overload is due to the huge numbers, stored in Knuth's 2 x 2 matrices, that have been defined using Numpy and mpmath. For Cython to be helpful in this subject, I should define those matrices as static, but I don't know the type I should use to define it. Is there a special type for this case?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2015-12-03 21:32:16 +0200

vdelecroix gravatar image

updated 2015-12-07 00:17:32 +0200

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))
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()

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

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

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

EDIT: if you only want the number of digits there is of course much faster

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()
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2015-11-30 19:43:17 +0200

Seen: 339 times

Last updated: Dec 07 '15