Wanted: Efficient Algorithm to Square an Integer Number
|
03-06-2019, 03:54 PM
(This post was last modified: 03-06-2019 03:54 PM by Martin Hepperle.)
Post: #1
|
|||
|
|||
Wanted: Efficient Algorithm to Square an Integer Number
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 |
|||
03-06-2019, 08:10 PM
Post: #2
|
|||
|
|||
RE: Wanted: Efficient Algorithm to Square an Integer Number
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.
— Ian Abbott |
|||
03-06-2019, 08:16 PM
Post: #3
|
|||
|
|||
RE: Wanted: Efficient Algorithm to Square an Integer Number
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 |
|||
03-06-2019, 11:24 PM
Post: #4
|
|||
|
|||
RE: Wanted: Efficient Algorithm to Square an Integer Number
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. |
|||
03-06-2019, 11:47 PM
Post: #5
|
|||
|
|||
RE: Wanted: Efficient Algorithm to Square an Integer Number
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 |
|||
03-07-2019, 12:10 AM
Post: #6
|
|||
|
|||
RE: Wanted: Efficient Algorithm to Square an Integer Number
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-07-2019, 02:52 PM
(This post was last modified: 03-08-2019 12:21 PM by Martin Hepperle.)
Post: #7
|
|||
|
|||
RE: Wanted: Efficient Algorithm to Square an Integer Number
(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-08-2019, 12:26 AM
Post: #8
|
|||
|
|||
RE: Wanted: Efficient Algorithm to Square an Integer Number
(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... |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)