find all multiplicands and multipliers for a number

[Steven D'Aprano]

On Sun, 12 Apr 2015 02:31 am, Paul Rubin wrote:

> Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
>> [3, 3, 3, 3, 7, 19, 73, 87211, 262657, 1.4411518807585587e+17]
>> Oops, you have a float in there, how did that happen?
> 
> Looks like you are using a broken version of Python.

Well, we know about people who blame their tools ... *wink*

I'm really not using a broken version of Python. You're the one using /=
instead of integer division.

Ah, the penny drops! Are you using Python 2.7 with old-style division? That
would explain it.

Okay, let me do the experiment again, this time with old-division enabled,
using 2.7.


py> n = 2**111 + 1
py> with Stopwatch():
...     pyprimes.factors.factorise(n)
...
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
time taken: 24.011609 seconds
py> with Stopwatch():
...     list(fac(n))
...
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
time taken: 11.743913 seconds

That's certainly an improvement over what I got before, both in time and
correctness. I didn't expect that float arithmetic would be so much slower
than int arithmetic! Go figure.


Here's another demonstration:

py> m = 2**117 - 1
py> with Stopwatch():
...     pyprimes.factors.factorise(m)
...
[7, 73, 79, 937, 6553, 8191, 86113, 121369, 7830118297L]
time taken: 0.089402 seconds
py> with Stopwatch():
...     list(fac(m))
...
[7, 73, 79, 937, 6553, 8191, 86113, 121369, 7830118297L]
time taken: 0.047645 seconds


Nice! Except that your fac() function has a bug: it includes 1 as a prime
factor for some values, which is strictly incorrect.

py> list(fac(4))
[2, 2, 1]

That probably won't make much difference for the speed, but it will
certainly make a difference with the correctness.

Oh:

py> pyprimes.factors.factorise(-1234567)
[-1, 127, 9721]
py> list(fac(-1234567))
[-1234567]


-- 
Steven