On Sun, 12 Apr 2015 02:31 am, Paul Rubin wrote: > Steven D'Aprano <steve+comp.lang.pyt...@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 -- https://mail.python.org/mailman/listinfo/python-list
