find all multiplicands and multipliers for a number
steve+comp.lang.python at pearwood.info
Sun Apr 12 16:29:05 CEST 2015
On Sun, 12 Apr 2015 07:34 pm, Brian Gladman wrote:
> On 11/04/2015 03:04, Steven D'Aprano wrote:
>> It may be a bit slow for very large numbers. On my computer, this takes
>> 20 seconds:
>> py> pyprimes.factors.factorise(2**111+1)
>> [3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
>> but that is the nature of factorising large numbers.
> I don'tknow how well it compares more generally but where large amounts
> of memory are available a simple sieve works quite well. I have an
> implementation available here (in Python 3):
Um, "simple sieve"? You're using Miller-Rabin to check for candidate prime
factors. I don't think that counts as a simple sieve :-)
>>>> from number_theory import factors
>>>> print(tuple(factor(2 ** 111 + 1)))
> ((3, 2), (1777, 1) , (3331, 1), (17539, 1), (25781083, 1),
> (107775231312019, 1))
> runs in less than 2 seconds on my laptop.
Although it is not directly comparable to the sieve version I used above, on
my machine I get:
py> import number_theory
py> with Stopwatch():
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019]
time taken: 5.823970 seconds
so there is a quite good speedup available from using Miller-Rabin. But it's
not a simple sieve any more.
By the way, it is possible to get guaranteed deterministic
(non-probabilistic) results with Miller-Rabin, for small integers. By small
I mean less than 2**64. See my pyprimes for details.
More information about the Python-list