Wanted: Efficient Algorithm to Square an Integer Number

[Jim Horn]

(03-06-2019 11:24 PM)Thomas Okken Wrote:  When squaring a number, you can save one multiplication here, since a_low * b_high and a_high * b_low are the same in this case. The difference is going to be even more pronounced if you're implementing 32-bit multiplication on an 8-bit CPU, and I imagine similar optimizations come into play when implementing it in hardware.

Exactly, Thomas! Back when HP's 9836 was a potent workstation (8MHz 68000!) I benchmarked it by having it compute Ackerman's function of (4,2), which is 2^65536 - 3. In Rocky Mountain BASIC. The initial version took about 45 minutes but changing to use the symmetries of squaring cut that almost in half.

Of course, the same program on a modern PC takes a small fraction of a second, to say nothing of optimized assembly...