ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 03 Dec 2015 14:32:16 -0600def type of mpmath matrices in cythonhttp://ask.sagemath.org/question/31210/def-type-of-mpmath-matrices-in-cython/ 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?
Mon, 30 Nov 2015 12:43:17 -0600http://ask.sagemath.org/question/31210/def-type-of-mpmath-matrices-in-cython/Answer by vdelecroix for <p>I'm trying to speed up the exact <em>iterative</em> 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?</p>
http://ask.sagemath.org/question/31210/def-type-of-mpmath-matrices-in-cython/?answer=31295#post-id-31295The 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](http://flintlib.org/) 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()
208987640Thu, 03 Dec 2015 14:32:16 -0600http://ask.sagemath.org/question/31210/def-type-of-mpmath-matrices-in-cython/?answer=31295#post-id-31295