On Sunday 29 June 2003 05:42, Pierre Abbat wrote:
I am investigating 64-100 sequences, which are chains of bases such that
the number written 100 in each is written 64 in the next (e.g. 8,10,16,42).
I quickly wrote a Python program to compute them. It is now computing the
square of a 1555000 digit number and has been doing so since the 17th. What
squaring algorithm is Python using?
I don't know offhand, but:
(a) Python is interpreted;
(b) the Python interpreter is open source, so it shouldn't be hard to find
out how it does big integer arithmetic;
(c) you might also look for a dependence on the GNU multi-precision library
(GMP) since that is an obvious candidate;
(d) whatever method it's using doesn't seem to be very efficient - you have
been running for 10 days to execute something which mprime/Prime95 would
accomplish in a small fraction of a second.
Is there a faster way of squaring
numbers where the number of digits doubles at each iteration?
There is x^2 code in the published mprime/Prime95 source. To do what you
require would obviously require you to hack together something to load the
initial work vectors read the result back out when you've finished. Also
you would need to start with twice the FFT run length you would require for
the multiplication modulo 2^p-1 (so there is room for the double-length
result) double the run length again for each squaring. But it looks more
like lots of work than being difficult.
An alternative approach, cobble something together using GMP, which is
reasonably efficient for general work, though not blindingly so.
Regards
Brian Beesley
_
Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
