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

OmniOutliner Pro 4.6 - Pro version of th...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
Alfred 3.1 - Quick launcher for apps and...
Alfred is an award-winning productivity application for OS X. Alfred saves you time when you search for files online or on your Mac. Be more productive with hotkeys, keywords, and file actions at... Read more
OmniOutliner 4.6 - Organize your ideas,...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
Default Folder X 5.0.6 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click on... Read more
Adobe Creative Cloud 3.8.0.310 - Access...
Adobe Creative Cloud costs $19.99/month for a single app, or $49.99/month for the entire suite. Introducing Adobe Creative Cloud desktop applications, including Adobe Photoshop CC and Illustrator CC... Read more
MYStuff Pro 2.0.25 - Create inventories...
MYStuff Pro is the most flexible way to create detail-rich inventories for your home or small business. Add items to MYStuff by dragging and dropping existing information, uploading new images, or... Read more
Viber 6.2.0 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device, so... Read more
Data Rescue 4.2.3 - Powerful hard drive...
Use Data Rescue to recover: crashed, corrupted or non-mounting hard drive deleted, damaged, or lost files reformatted or erased hard drive One powerful new feature found in Data Rescue 4 is... Read more
Microsoft Remote Desktop 8.0.34 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
Microsoft Remote Desktop 8.0.34 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more

Find out the story behind League of Ange...
If you’re looking for a new thrilling MMORPG to play with your friends then you’ll be excited to hear that there is a sequel to one of the most well known titles in the genre – namely League of Angels 2. With a brand new 3D engine offering... | Read more »
Naruto Shippuden: Ultimate Ninja Blazing...
I'm not sure if it's possible to say you are an anime fan but also never have seen one episode of Naruto. If it is, then I resemble that remark, and if not, I offer a hearty apology. [Read more] | Read more »
5 mobile games that let you explore spac...
No Man's Sky hasn't exactly turned out to be everything it was promised. Though its core concept of exploring an unimaginably vast universe of different planets is an intriguing one, the execution has left many PS4 and PC gamers feeling like they... | Read more »
Mummy madness in new action game Tomb He...
Hot on the tail of Bump Hero, ZPlay is giving gamers another reason to get screen bashing with a brand new release. Tomb Heroes is a challenging action game in which you battle enemies in various tombs around the world. You can select from nine... | Read more »
Siralim 2 (RPG / Roguelike) (Games)
Siralim 2 (RPG / Roguelike) 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Siralim 2 is an old-school monster catching RPG. Summon and customize hundreds of creatures to fight for you as... | Read more »
Clean Text (Productivity)
Clean Text 1.0 Device: iOS Universal Category: Productivity Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Gemini - A Journey of Two Stars (Games)
Gemini - A Journey of Two Stars 1.0.1 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.1 (iTunes) Description: *** SPECIAL LAUNCH SALE: $2.99 (25% off) *** "A mesmerizing and unexpectedly emotional journey." -- Los... | Read more »
How to get four NFL superstars for your...
Even though you're probably well on your way to building a top notch squad for the new season in Madden NFL Mobile, let's say you could beef it up by adding Rob Gronkowski, Antonio Brown, Von Miller, and Todd Gurley to your roster. That's... | Read more »
Cartoon Network Superstar Soccer: Goal!!...
Cartoon Network Superstar Soccer: Goal!!! – Multiplayer Sports Game Starring Your Favorite Characters 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Become a soccer superstar with your... | Read more »
NFL Huddle: What's new in Topps NFL...
Can you smell that? It's the scent of pigskin in the air, which either means that cliches be damned, pigs are flying in your neck of the woods, or the new NFL season is right around the corner. [Read more] | Read more »

Price Scanner via MacPrices.net

RESCUECOM 2016 Semi-Annual Computer Reliabili...
The beginning of a new school year is upon us again, in which students and parents have some very important choices to make, often including the purchase of a computer or tablet. Whether you are... Read more
VRS Design Damda Glide Series iPhone 7 and 7...
What makes the Damda Glide Series for the iPhone 7 and iPhone 7 Plus special? Case maker VRS Design says its Damda Glide Series is the first mobile case to incorporate a semi-automatic mechanism for... Read more
Apple refurbished iMacs available for up to $...
Apple has Certified Refurbished 2015 21″ & 27″ iMacs available for up to $350 off MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are available: - 21″ 3.... Read more
Clearance 2015 13-inch MacBook Airs available...
B&H Photo has clearance 2015 13″ MacBook Airs available for $350 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 1.6GHz/4GB/128GB MacBook Air (MJVE2LL/A): $829... Read more
Check Apple prices on any device with the iTr...
MacPrices is proud to offer readers a free iOS app (iPhones, iPads, & iPod touch) and Android app (Google Play and Amazon App Store) called iTracx, which allows you to glance at today’s lowest... Read more
Save $120 with Apple refurbished Time Capsule...
Apple has certified refurbished Time Capsules available for $120 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $179, $120 off (not... Read more
9-inch 32GB iPad Pros on sale for $70 off MSR...
B&H Photo has 9″ 32GB WiFi Apple iPad Pros on sale for $70 off MSRP, each including free shipping. B&H charges sales tax in NY only: - 9″ Space Gray 32GB WiFi iPad Pro: $529 $70 off MSRP - 9... Read more
Mac minis on sale for up to $140 off MSRP
Adorama has Mac minis on sale for up to $100 off MSRP including free shipping plus NY & NJ sales tax only: - 1.4GHz Mac mini: $449 $50 off MSRP - 2.6GHz Mac mini: $649 $50 off MSRP Amazon has the... Read more
Back To School with OtterBox Essentials
Back to school means back to an environment that is tough on tech. OtterBox has the back to school essentials you need to keep tech safe from drops, bumps, scratches and hallway havoc. Check out the... Read more
VRS Design Releases New iPhone 7 Plus Case Li...
With a device as large and costly as the iPhone 7 Plus, it is primal instinct to protect it from potential damage. According to a study by SquareTrade in 2012, iPhone damages cost Americans roughly $... Read more

Jobs Board

*Apple* Solutions Consultant - Apple (United...
Apple Solutions ConsultantJob Number: 51218534Pleasant Hill, California, United StatesPosted: Aug. 18, 2016Weekly Hours: 40.00Job SummaryAs an Apple Solutions Read more
*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 51218354 Fredericksburg, Virginia, United States Posted: Aug. 18, 2016 Weekly Hours: 40.00 **Job Summary** As an Apple Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* /Mac Support Engineer - GFI Digital,...
FI Digital, Inc. is currently seeking candidates for a full time Apple Support Engineer to add to our Maryland Heights, Missouri IT team. Candidates must be dynamic Read more
*Apple* Solutions Consultant - Apple (United...
Apple Solutions ConsultantJob Number: 51218534Pleasant Hill, California, United StatesPosted: Aug. 18, 2016Weekly Hours: 40.00Job SummaryAs an Apple Solutions Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.