Wanted: Efficient Algorithm to Square an Integer Number
03-06-2019, 11:24 PM
Post: #4
 Thomas Okken Senior Member Posts: 1,788 Joined: Feb 2014
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.
 « Next Oldest | Next Newest »

 Messages In This Thread Wanted: Efficient Algorithm to Square an Integer Number - Martin Hepperle - 03-06-2019, 03:54 PM RE: Wanted: Efficient Algorithm to Square an Integer Number - ijabbott - 03-06-2019, 08:10 PM RE: Wanted: Efficient Algorithm to Square an Integer Number - Martin Hepperle - 03-07-2019, 02:52 PM RE: Wanted: Efficient Algorithm to Square an Integer Number - David Hayden - 03-06-2019, 08:16 PM RE: Wanted: Efficient Algorithm to Square an Integer Number - Thomas Okken - 03-06-2019 11:24 PM RE: Wanted: Efficient Algorithm to Square an Integer Number - Jim Horn - 03-08-2019, 12:26 AM RE: Wanted: Efficient Algorithm to Square an Integer Number - Gerson W. Barbosa - 03-06-2019, 11:47 PM RE: Wanted: Efficient Algorithm to Square an Integer Number - Druzyek - 03-07-2019, 12:10 AM

User(s) browsing this thread: 1 Guest(s)