for Dave Britten--get well soon

[Dave Britten]

(05-06-2014 03:06 AM)Don Shepherd Wrote:  Thanks for your work with that prime factor algorithm, I can't tell you how much pleasure I have had over the years adapting that for other machines.

I neglected to clarify this earlier, but while I didn't create the algorithm, I can take at least a little credit for finding it in the museum software library and pulling it out into the limelight. This is the original HP-67 version from Math Pac 2:

http://www.hpmuseum.org/software/67pacs/67factor.htm

I didn't study enough number theory in college to be able to provide an exhaustive deconstruction of the algorithm, but I think it perfectly captures the spirit of these kinds of calculators and computers: being able to strike the perfect balance between hardware resources and algorithmic complexity in order to provide genuine efficiency gains without losing sight of the problem domain. The naive prime factors algorithm - divide by 2 and all odd numbers, hopefully at least stopping early at SQRT(x) - just can't hope to compete with this elegant approach. And yet I'm sure there's still plenty of room for a better algorithm if silicon is no limitation.

My calculator doesn't need distributed map/reduce algorithms to evaluate multi-terabyte data sets in seconds; sometimes I just want to quickly factor a 9 digit number in less time than I would have to spend getting the answer from bigger iron.

There's your weekend philosophical discussion of why I mess with these old things.