Long integers, xrange and number theory

[Mark Edward Tristan Dickinson]

Bengt Richter wrote:

> I suspect the xrange vs generator efficiency worry is disproportionate ;-)
> (see below).

I suspect you're right!  In unscientific tests, there doesn't seem to
be any perceptible difference in running times between the xrange,
generator and while loop solutions.  The running time of the Lehman
algorithm is almost certainly dominated by the calls to isSquare().

> Remember, Python is not C++, so if you want speed, I think you might gain more
> by avoiding recalculations (which a good optimizer would do for you in a
> static situation) than you'll lose by using a generator in place of xrange.

I'm not really that worried about speed: it's more important to me
that each function is obviously an implementation of the relevant
algorithm.  So I've tried to go for clarity over efficiency.  (Or
maybe I'm just making excuses for not bothering with the
optimizations---I've got a limited amount of time to get this all
working :) )

Anyway, the existence of Python has certainly been a boon to this
project.  The software previously used in the number theory course was
written in Turbo Pascal and ran only under MS-DOS!

> But I'd be interested to know the time for the example factor 22073477 of 720676707764753
> if you just plug in xxrange, and then if you optimize to avoid the recalculations.
> And then with local bindings, if you're curious. Or if you have an URL to all the
> relevant code I might try it.

The code is at:

http://www.math.lsa.umich.edu/~dickinsm/575f02/ElemNum.py

Lehman() is somewhere in there, at about line 560 or so.

Thanks to everyone for their helpful responses.

Mark