find all multiplicands and multipliers for a number

Brian Gladman blindanagram at nowhere.net
Sun Apr 12 21:07:39 CEST 2015


On 12/04/2015 15:29, Steven D'Aprano wrote:

>> 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):
>>
>> http://ccgi.gladman.plus.com/wp/?page_id=1500
> 
> Um, "simple sieve"? You're using Miller-Rabin to check for candidate prime
> factors. I don't think that counts as a simple sieve :-)
> 
What I meant here is that the underlying sieve on which factoring
depends - Primes() - is a simple one.  I'm sorry that I didn't make this
clearer.  I agree, of course, that the factoring code itself is more
complex than others are experimenting with but I am using it in
situations where I want it to work reasonbly well for quite large
numbers.

> 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.

Yes, I have a more complex version but the simple one works well enough
in this context and finds very large primes that would otherwise stall
the code.

Thanks for taking a look.

   Brian




More information about the Python-list mailing list