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

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.

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

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

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.

(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

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