Wanted: Efficient Algorithm to Square an Integer Number

[Martin Hepperle]

Hi,

some programming languages (like (Turbo Pascal) offer special functions to square an integer number. These are said to be faster than multiplying the number by itself.

Where can I find algorithms like this? I searched the internet for a while and I am aware of Donald Knuth's books, but I did not find a suitable algorithm.

Some time ago I had a document describing many clever tricks for working with numbers in various digital representations (8 ... 64 bit integers, IEEE floating point). Many involved magic numbers and overflows etc.. It contained algorithms like inverting all bits in a number and similar. But I cannot find it anymore.
Any ideas, hints, links?

Thank you,
Martin

[ijabbott]

I'm not aware of clever tricks for squaring an integer (and most modern CPUs have fast multiply instructions), but this seems like another opportunity to recommend the book Hacker's Delight (2nd Edition) by Henry S. Warren, Jr.

[David Hayden]

On any modern CPU, it's likely that multiplying a number by itself will be about as fast as it gets.

If you're just looking for the intellectual joy, here's the book that we used for my "Computer Arithmetic" course in 1986. It was a real eye-opener: redundant number systems, fast carries, wallace trees, all sorts of cool stuff. I took the course from the author.
https://www.amazon.com/Computer-Number-S...0131642111

[Thomas Okken]

Many years ago, I wrote a program to visualize the Mandelbrot set on my Macintosh. This was the original model, with the 7.83 MHz 68000 CPU.

To get as much speed as possible, I coded the iteration using fixed-point math, in assembly language. This required, among other things, calculating a couple of 32-bit multiplications, and since the 68000 could only multiply 16-bit numbers, this required performing four multiplications and combining their results: a_low * b_low + (a_low * b_high + a_high * b_low) << 16 + a_high * b_high << 32.

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.

[Gerson W. Barbosa]

Not the best method, but this can be done entirely with integer operations and no multiplications whatsoever (lines 17 & 18 and lines 20 & 21 are shift left and shift right operations, respectively).

More details in this old forum thread:

OT: primitive mult/div algorithms

00 { 43-Byte Prgm }
01▸LBL "ISQ"
02 ABS
03 0
04 STO 00
05 X<>Y
06 ENTER
07 ENTER
08▸LBL 00
09 CF 00
10 0
11 BIT?
12 SF 00
13 R↓
14 X<>Y
15 FS? 00
16 STO+ 00
17 -1
18 ROTXY
19 X<>Y
20 2
21 BASE÷
22 X>0?
23 GTO 00
24 RCL 00
25 END


42 XEQ ISQ -> 1764

[Druzyek]

If you're working with a microcontroller or processor without hardware multiply you might want to check out the Quarter Square and Russian peasant algorithms. I've found both to be fast depending on the architecture.

[Martin Hepperle]

(03-06-2019 08:10 PM)ijabbott Wrote:  I'm not aware of clever tricks for squaring an integer (and most modern CPUs have fast multiply instructions), but this seems like another opportunity to recommend the book Hacker's Delight (2nd Edition) by Henry S. Warren, Jr.

Thank you, this is very interesting and surely comes in handy for future coding problems.

My CPUs of interest are older and do not offer multiplication (e.g. 6800 and HP-Series-80 Capricorn).

I finally found this explanation for the existance of the Sqr() function in "FreePascal from Square One" (http://www.copperwood.com/pub/FreePascal...areOne.pdf):

"11.2. Sqr and Sqrt
Nothing complicated here. Sqr(X) squares X. It is completely equivalent to X * X,
and Pascal includes it because squaring is done so frequently in mathematics, and
also because (as we will discuss later) there is no exponentiation operator in Standard
Pascal and hence no clean notation for X raised to a power of two. FreePascal does
have an exponentiation operator, as I’ll explain shortly, and so with FreePascal, Sqr
is unnecessary."

So the Sqr() function in Pascal seems to be unrelated to speed, contrary to what I had thought.

Thank you all for your help,
Martin

[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...