Yesterday I coded up an idea from a 1952 paper by G G Alway.
From the paper A method of factorisation using a high-speed computer:
This process is manifestly simple. On the pilot model of the ACE we have used it to establish the primality or discover a factor of a twelve decimal digit number in less than 15 minutes, each step in the above process taking 1 millisecond.
…
EDITORIAL NOTE: ROSELYN LIPKIS reports that, as applied to the SWAC, the above method speeds up the factoring process by a factor of 8. All six steps A-F are performed in approximately 1.3 millisecond
Unfortunately, the interpreted nature of BBC Basic means there’s no speedup to be had - not with my coding anyway - compared to naive trial division, because division isn’t expensive enough for the gain to show. (If I replicate the division computations, to emulate a slower division, it becomes clear.)
I would expect that a 6502 version should show the gain though.
What G G Alway found was a way to express most of the divisions as an integer recurrence relationship on the remainder terms. It might be that even in modern CPUs, there’s a gain to be had, although it’s also true that other techniques might make greater gains. The larger the number being factorised, the greater proportion of divisions eliminated.
Alway’s paper was followed in 1957 by a paper by Dijkstra, who found a way to do only one division, at the cost of a more complex approach. As ever, he was quite opinionated about it:
The less efficient steps of the process for large n (i.e. small f) could be avoided by carrying out divisions for small values of f… However we strongly advise not to do this.
If the process described above is started at f = 3, the whole computation can be checked at the end…
In a posthumously published paper Alway 1971 A general factorising algorithm written in 1970, G G Alway revisited his method, and extended it to include Dijkstra’s approach as an option, and also to skip multiples of three as an option, delivering a 1.5x speedup. I haven’t (yet) coded this up.
(Alway’s papers are paywalled; Dijkstra’s is not.)
(It’s possible my code is flawed in some way - don’t rely on it!)
