TweetFollow Us on Twitter

Fast Square Root Calc

Volume Number: 14 (1998)
Issue Number: 1
Column Tag: Assembler Workshop

Fast Square Root Calculation

by Guillaume Bédard, Frédéric Leblanc, Yohan Plourde and Pierre Marchand, Québec, Canada

Optimizing PowerPC Assembler Code to beat the Toolbox

Introduction

The calculation of the square root of a floating-point number is a frequently encountered task. However, the PowerPC processors don't have a square root instruction. The implementation presented here performs the square root of a double-precision number over the full range of representation of the IEEE 754 standard for normalized numbers (from 2.22507385851E-308 to 1.79769313486E308) with an accuracy of 15 or more decimal digits. It is very fast, at least six times faster than the Toolbox ROM call.

Theory of Operation

A floating point number has three components: a sign, a mantissa and an exponential part. For example, the number +3.5 x 10^4 (35 000) has a plus sign, a mantissa of 3.5 and an exponential part of 104. The mantissa consists of an integer part and a fractional part f.

A double precision number in IEEE 754 format has the same components: a sign bit s, an 11-bit exponent e and a 52 bit fraction f. The exponential part is expressed in powers of 2 and the exponent is biased by adding 1023 to the value of e. The mantissa is normalized to be of the form 1.f. Since the integer part of the normalized mantissa is always 1, it doesn't have to be included in the representation. The number is thus represented as follows: (-1)s x 1.f x 2^e+1023.

For example, the number 5.0 can be expressed in binary as 101.0, which means 101.0 x 2^0, which in turn is equal to 1.010 x 2^2, obtained by dividing the mantissa by 4 and multiplying 2^0 by 4. Therefore, the normalized mantissa is 1.010 and the exponent 2. Fraction f is then .01000000.... The biased exponent is obtained by adding 1023 to e and is 1025, or 10000000001 in binary. The double precision IEEE representation of 5.0 is finally:

-----------------------------------------------------------------------------
|  0 | 10000000001 | 01000000000000000000000000000000000000000000000000000  |
-----------------------------------------------------------------------------

or 4014000000000000 in hexadecimal notation for short.

First Approximation

Given this representation, a first approximation to the square root of a number is obtained by dividing the exponent by 2. If the number is an even power of 2 such as 16 or 64, the exact root is obtained. If the number is an odd power of 2 such as 8 or 32, 1/SQRT(2) times the square root is obtained. In general, the result will be within a factor SQRT(2) of the true value.

Refining the Approximation

The Newton-Raphson method is often used to obtain a more accurate value for the root x of a function f(x) once an initial approximation x0 is given:

[1]

This becomes, in the case of the square root of n, = x2 - n:where f(x)

[2]

An excellent approximation to the square root starting with the initial approximation given above is obtained within 5 iterations using equation [2]. This algorithm is already pretty fast, but its speed is limited by the fact that each iteration requires a double-precision division which is the slowest PowerPC floating-point instruction with 32 cycles on the MPC601 (Motorola, 1993).

Eliminating Divisions

Another approach is to use equation [1] with the function.

In this case, equation [1] becomes:

[3]

There is still a division by n, but since n is constant (it's the original number whose root we want to find), it can be replaced by multiplying by 1/n, which can be calculated once before the beginning of the iteration process. The five 32-cycle divisions are thus replaced by this single division followed by 5 much faster multiplications (5 cycles each). This approach is approximately three times faster than the preceding one. However, care must be taken for large numbers since the term in x02 can cause the operation to overflow.

Use of a table

Finally, an approach that is even faster consists in using a table to obtain a more accurate first approximation. In order to do so, the range of possible values of fraction f (0 to ~1) is divided into 16 sub-ranges by using the first 4 bits of f as an index into a table which contains the first two coefficients of the Taylor expansion of the square root of the mantissa (1.0 to ~2) over that sub-range.

The Taylor expansion is given in general by:

[4]

the first two terms of which yield, in the case where f(x) = SQRT(x):

[5]

The square root of x is thus approximated by 16 straight-line segments. The table therefore contains the values of

A =

and B =

for each of the 16 sub-ranges as shown in Figure 1. This first approximation gives an accuracy of about 1.5 %.

Figure 1. Approximation by straight line segment.

To reach the desired accuracy of 15 digits, equation [2] is applied twice to the result of equation [5]. To avoid having to perform two divisions by repeating the iteration, the two iterations are folded together as follows, which contains only one division:

and

[6]

In order to perform these calculation, the exponent of x and n is reduced to -1 (1022 biased), so that floating-point operations apply only to the values of the mantissa and don't overflow if the exponent is very large. The value of these numbers will therefore be in the range 0.5 to 1.0 since the mantissa is in the range 1.0 to 2.0. If the original exponent was odd, the mantissa is multiplied by SQRT(2) before applying equation [6].

Finally, the original exponent divided by two is restored at the end.

The Code

The SQRoot function shown in Listing 1 has been implemented in CodeWarrior C/C++ version 10.

Listing 1: SQRoot.c

// On entry, fp1 contains a positive number between 2.22507385851E-308
// and 1.79769313486E308. On exit, the result is in fp1.

asm long double SQRoot(long double num);   // prototype

float Table[35] = {
0.353553390593, 0.707106781187, 0.364434493428, 0.685994340570,
0.375000000000, 0.666666666667, 0.385275875186, 0.648885684523,
0.395284707521, 0.632455532034, 0.405046293650, 0.617213399848,
0.414578098794, 0.603022689156, 0.423895623945, 0.589767824620,
0.433012701892, 0.577350269190, 0.441941738242, 0.565685424949,
0.450693909433, 0.554700196225, 0.459279326772, 0.544331053952,
0.467707173347, 0.534522483825, 0.475985819116, 0.525225731439,
0.484122918276, 0.516397779494, 0.492125492126, 0.508000508001,
1.414213562373, 0.000000000000, 0.000000000000 };

asm long double Sqrt(long double num) {

   lwz   r3,Table(rtoc)      // address of Table[]
   lhz   r4,24(sp)           // load
                             // Sign(1)+Exponent(11)+Mantissa(4)
   andi.   r5,r4,0xF         // keep only Mantissa(4)
   ori   r5,r5,0x3FE0        // exponent = -1+BIAS = 1022
   sth   r5,24(sp)           // save reduced number

   rlwinm   r5,r5,3,25,28    // take 8*Mantissa(4) as index
   lfd   fp1,24(sp)          // load reduced number
   lfsux   fp4,r5,r3         // load coefficient A
   lfs   fp5,4(r5)           // load coefficient B
   lfs   fp3,128(r3)         // load SQRT(2)
   fmr   fp2,fp1             // copy reduced number
   rlwinm.   r5,r4,31,18,28  // divide exponent by 2
   beq   @@2                 // if (exponent == 0) then done

   fmadd   fp2,fp2,fp5,fp4   // approximation SQRT(x) = A + B*x
   andi.   r4,r4,0x10        // check if exponent even
   beq   @@1                 // if (exponent even) do iteration
   fmul   fp2,fp2,fp3        // multiply reduced number by SQRT(2)
   fadd   fp1,fp1,fp1        // adjust exponent of original number

@@1:   fadd   fp3,fp2,fp2    // 2*x
   fmul   fp5,fp2,fp1        // x*n
   fadd   fp3,fp3,fp3        // 4*x
   fmadd   fp4,fp2,fp2,fp1   // x*x + n
   fmul   fp5,fp3,fp5        // 4*x*x*n
   fmul   fp6,fp2,fp4        // denominator = x*(x*x + n)
   fmadd   fp5,fp4,fp4,fp5   // numerator = (x*x + n)*(x*x + n) +
                             // 4*x*x*n
   fdiv   fp1,fp5,fp6        // double precision division
   andi.   r5,r5,0x7FF0      // mask exponent 
   addi   r5,r5,0x1FE0       // rectify new exponent

@@2:   sth   r5,132(r3)      // save constant C (power of 2) 
   lfd   fp2,132(r3)         // load constant C
   fmul   fp1,fp1,fp2        // multiply by C to replace exponent
   blr                       // done, the result is in fp1
}

Performance

The code presented above runs in less than 100 cycles, which means less than 1 microsecond on a 7200/75 Power Macintosh and is more than six times faster than the ROM code. The code could be modified to make use of the floating reciprocal square root estimate instruction (frsqrte) that is available on the MPC603 and MPC604 processors, and which has an accuracy of 5 bits. It is not available on the MPC601, however. The method used here could also be used to evaluate other transcendental functions.

Performance was measured by running the code a thousand times and calling a simple timing routine found in (Motorola, 1993), that we called myGetTime(). It uses the real-time clock of the MPC 601 processor (RTCU and RTCL registers) and is shown in Listing 2. The routine would have to be modified to run on MPC603 or MPC604 processors, since they don't have the same real-time clock mechanism.

The code doesn't support denormalized numbers (below 2.22507385851E-308). This could easily be implemented albeit at the cost of a slight reduction in performance.

Listing 2: myGetTime.c

asm long myGetTime()
   {
lp:    mfspr   r4,4           // RTCU
   mfspr   r3,5               // RTCL
   mfspr   r5,4               // RTCU again
    cmpw      r4,r5           // if RTCU has changed, try again
    bne      lp
    rlwinm   r3,r3,25,7,31    // shift right since bits 25-31 are
                              // not used
    blr                       // the result is in r3. 1 unit is
                              // worth 128 ns.
   }

To run the code, a very simple interface using the SIOUX library is provided in Listing 3.

Listing 3: main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fp.h>

void main()
   {
   long double   num, num2;
   long startTime, endTime, time;
   short i;


   do {
   printf("%2s","> ");           // caret
   scanf("%Lf",&num);           // read long double
   if (num < 0.0) num = 0.0;     // replace by 0.0 if negative
   startTime = myGetTime();
   for (i = 0; i < 1000; i++)    // repeat 1000 times
   num2 = SQRoot(num);              // call our function
   endTime = myGetTime();
   time = endTime - startTime;
   if (num > 1e-6 && num < 1e7)
      printf("%7s%Lf\n","root = ",num2);   // show result
   else
      printf("%7s%Le\n","root = ",num2);
   printf("%7s%d\n","time = ", time);      // show elapsed time
   }
   while (1);                              // repeat until Quit
   }

References

PowerPC 601 RISC Microprocessor User's Manual, Motorola MPC601UM/AD Rev 1, 1993.


The first three authors are undergraduate students in Computer Science at Université Laval in Québec, Canada. This work was done as an assignment in a course on Computer Architecture given by the fourth author.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Garmin Express 7.0.0.0 - Manage your Gar...
Garmin Express is your essential tool for managing your Garmin devices. Update maps, golf courses and device software. You can even register your device. Update maps Update software Register your... Read more
ClipGrab 3.8.12 - Download videos from Y...
ClipGrab is a free downloader and converter for YouTube, Vimeo, Facebook and many other online video sites. It converts downloaded videos to MPEG4, MP3 or other formats in just one easy step Version... Read more
VMware Fusion 11.5.5 - Run Windows apps...
VMware Fusion and Fusion Pro - virtualization software for running Windows, Linux, and other systems on a Mac without rebooting. The latest version includes full support for Windows 10, macOS Mojave... Read more
Civilization VI 1.3.0 - Next iteration o...
Civilization® VI is the award-winning experience. Expand your empire across the map, advance your culture, and compete against history’s greatest leaders to build a civilization that will stand the... Read more
Corel Painter 20.1.0.285 - Digital art s...
Corel Painter lets you advance your digital art style with painted textures, subtle glazing brushwork, interactive gradients, and realistic Natural-Media. Easily transition from traditional to... Read more
iTubeDownloader 6.5.19 - Easily download...
iTubeDownloader is a powerful-yet-simple YouTube downloader for the masses. Because it contains a proprietary browser, you can browse YouTube like you normally would. When you see something you want... Read more
OmniFocus 3.8 - GTD task manager with iO...
OmniFocus is an organizer app. It uses projects to organize tasks naturally, and then add tags to organize across projects. Easily enter tasks when you’re on the go, and process them when you have... Read more
Hazel 4.4.5 - Create rules for organizin...
Hazel is your personal housekeeper, organizing and cleaning folders based on rules you define. Hazel can also manage your trash and uninstall your applications. Organize your files using a familiar... Read more
Macs Fan Control 1.5.7 - Monitor and con...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
Acorn 6.6 - Bitmap image editor.
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more

Latest Forum Discussions

See All

Steam Link Spotlight - Signs of the Sojo...
Steam Link Spotlight is a feature where we look at PC games that play exceptionally well using the Steam Link app. Our last entry was XCOM: Chimera Squad. Read about how it plays using Steam Link's new mouse and keyboard support over here. | Read more »
Steampunk Tower 2, DreamGate's sequ...
Steampunk Tower 2 is a DreamGate's follow up to their previous tower defence game. It's available now for both iOS and Android as a free-to-play title and will see players defending their lone base by kitting it out with a variety of turrets. [... | Read more »
Clash Royale: The Road to Legendary Aren...
Supercell recently celebrated its 10th anniversary and their best title, Clash Royale, is as good as it's ever been. Even for lapsed players, returning to the game is as easy as can be. If you want to join us in picking the game back up, we've put... | Read more »
Pokemon Go Fest 2020 will be a virtual e...
Niantic has announced that Pokemon Go Fest will still take place this year although understandably it won't be a physical event. Instead, it will become a virtual celebration and is set to be held on 25th and 26th July. [Read more] | Read more »
Marvel Future Fight's major May upd...
Marvel Future Fight's latest update has now landed, and it sounds like a big one. The focus this time around is on Marvel's Guardians of the Galaxy, and it introduces all-new characters, quests, and uniforms for players to collect. [Read more] | Read more »
SINoALICE, Yoko Taro and Pokelabo's...
Yoko Taro and developer Pokelabo's SINoALICE has now opened for pre-registration over on the App Store. It's already amassed 1.5 million Android pre-registrations, and it's currently slated to launch on July 1st. [Read more] | Read more »
Masketeers: Idle Has Fallen's lates...
Masketeers: Idle Has Fallen is the latest endeavour from Appxplore, the folks behind Crab War, Thor: War of Tapnarok and Light A Way. It's an idle RPG that's currently available for Android in Early Access and will head to iOS at a later date. [... | Read more »
Evil Hunter Tycoon celebrates 2 million...
Evil Hunter Tycoon has proved to be quite the hit since launching back in March, with its most recent milestone being 2 million downloads. To celebrate the achievement, developer Super Planet has released a new updated called Darkness' Front Yard... | Read more »
Peak's Edge is an intriguing roguel...
Peak's Edge is an upcoming roguelike puzzle game from developer Kenny Sun that's heading for both iOS and Android on June 4th as a free-to-play title. It will see players rolling a pyramid shape through a variety of different levels. [Read more] | Read more »
Clash Royale: The Road to Legendary Aren...
Supercell recently celebrated its 10th anniversary and their best title, Clash Royale, is as good as it's ever been. Even for lapsed players, returning to the game is as easy as can be. If you want to join us in picking the game back up, we've put... | Read more »

Price Scanner via MacPrices.net

Sams Club Sales Event: $100 off every Apple W...
Sams Club is discounting all Apple Watch Series 5 models by $100 off Apple’s MSRP through June 3, 2020. Choose free shipping or free local store pickup (if available). Sale prices for online orders... Read more
New 16″ MacBook Pros now on sale for up to $2...
Apple reseller DataVision is now offering new 16″ Apple MacBook Pros for up to $255 off MSRP, each including free shipping. Prices start at $2194. DataVision charges sales tax for NY, NJ, PA, and CA... Read more
Apple now offering Certified Refurbished iPho...
Apple is now offering Certified Refurbished iPhone Xr models in the refurbished section of their online store starting at $499. Each iPhone comes with Apple’s standard one-year warranty, ships free,... Read more
Sale! Get a 10.2″ 32GB WiFi iPad for only $27...
Walmart has new 10.2″ 32GB WiFi iPads on sale for $50 off Apple’s MSRP, only $279. These are the same iPads sold by Apple in their retail and online stores. Be sure to select Walmart as the seller... Read more
Apple resellers offer new 2020 Mac minis for...
Apple resellers are offering new 2020 Mac minis for up to $50 off Apple’s MSRP with prices available starting at $759. Shipping is free: (1) B&H Photo: – 2020 4-Core Mac mini: $759 $40 off MSRP... Read more
Sprint is offering the Apple iPhone 11 free t...
Did you miss out on Sprint’s recent free iPhone SE promotion? No worries. Sprint has the 64GB iPhone 11 available for $0 per month for new lines when you trade-in a qualifying phone in any condition... Read more
Apple has clearance 2019 13″ 1.4GHz MacBook P...
Apple has Certified Refurbished 2019 13″ 1.4GHz 4-Core Touch Bar MacBook Pros available today starting at $979 and up to $440 off original MSRP. Apple’s one-year warranty is included, shipping is... Read more
Apple restocks 2019 MacBook Airs starting at...
Apple has clearance, Certified Refurbished, 2019 13″ MacBook Airs available again starting at $779. Each MacBook features a new outer case, comes with a standard Apple one-year warranty, and is... Read more
Apple restocks clearance Mac minis for only $...
Apple has restocked Certified Refurbished 2018 4-Core Mac minis for only $599. Each mini comes with a new outer case plus a standard Apple one-year warranty. Shipping is free: – 3.6GHz Quad-Core... Read more
Apple’s new 2020 13″ MacBook Airs on sale for...
B&H Photo has Apple’s new 2020 13″ 4-Core and 6-Core MacBook Airs on sale today for $50-$100 off Apple’s MSRP, starting at $949. Expedited shipping is free to many addresses in the US. The... Read more

Jobs Board

*Apple* Mac Desktop Support - Global Dimensi...
…Operate and support an Active Directory (AD) server-client environment for all Apple devices operating on the BUMED network + Leverage necessary industry enterprise Read more
Surgical Technologist III, *Apple* Hill Sur...
Surgical Technologist III, Apple Hill Surgical Center - Full Time Tracking Code D5.29.2020 Job Description Surgical Technologist III Apple Hill Surgical Center Read more
Security Officer - *Apple* Store - NANA (Un...
**Security Officer \- Apple Store** **Description** About NMS Built on a culture of safety and integrity, NMSdelivers award\-winning, integrated support services to Read more
Transition Into Practice Program (TIP) - Sept...
…Academy-Transition into Practice (TIP) Residency program at St Mary Medical Center in Apple Valley, CA. **We are seekingRegistered Nurses who are:** + New graduate Read more
Essbase Developer - *Apple* - Theorem, LLC...
Job Summary Apple is seeking an experienced, detail-minded Essbase developer to join our worldwide business development and strategy team. If you are someone who Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.