Click here to Skip to main content
11,802,442 members (70,539 online)
Click here to Skip to main content

Tagged as

Best Square Root Method - Algorithm - Function (Precision VS Speed)

, 15 Sep 2010 CPOL 148K 1.3K 89
Rate this:
Please Sign up or sign in to vote.
Square Root Methods Fast Algorithm Speed Precision computational Quake3 Fast Square Root Function Fast Gaming


I enjoy Game Programming with Directx and I noticed that the most called method throughout most of my games is the standard sqrt method in the Math.h and this made me search for faster functions than the standard sqrt. And after some searching, I found lots of functions that were much much faster but it's always a compromise between speed and precision. The main purpose of this article is to help people choose the best square-root method that suits their program.


In this article, I compare 14 different methods for computing the square root with the standard sqrt function as a reference, and for each method I show its precision and speed compared to the sqrt method.

What this Article is Not About

  1. Explaining how each method works
  2. New ways to compute the square root

Using the Code

The code is simple, it basically contains:

1. main.cpp

Calls all the methods and for each one of them, it computes the speed and precision relative to the sqrt function.

2. SquareRootmethods.h

This Header contains the implementation of the functions, and the reference of where I got them from.

First I calculate the Speed and Precision of the sqrt method which will be my reference.

For computing the Speed, I measure the time it takes to call the sqrt function (M-1) times and I assign this value to RefSpeed which will be my reference.

And for computing the Precision, I add the current result to the previous result in RefTotalPrecision every time I call the method. RefTotalPrecision will be my reference.

For measuring runtime duration (Speed) of the methods, I use the CDuration class found in this link, and I use dur as an instance of that class.

for(int j=0;j<AVG;j++)	
	for(int i=1;i<M;i++)
	   RefTotalPrecision+=sqrt((float) i);


And for the other methods I do the same calculations, but in the end, I reference them to the sqrt.

	for(int j=0;j<AVG;j++)	
		for(int i=1;i<M;i++)
		    TotalPrecision+=sqrt1((float) i);

cout<<"Precision = "


  1. I assume that the error in Precision whether larger or smaller than the reference is equal, that's why I use "abs".
  2. The Speed is referenced as the actual percentage, while the Precision is referenced as a decrease percentage.

You can modify the value of M as you like, I initially assign it with 10000.

You can modify AVG as well, the higher it is, the more accurate the results.

#define M 10000   
#define AVG 10   

Points of Interest

Precision wise, the sqrt standard method is the best. But the other functions can be much faster even 5 times faster. I would personally choose Method N# 14 as it has high precision and high speed, but I'll leave it for you to choose. Smile | :)

I took 5 samples and averaged them and here is the output:


According to the analysis the above Methods Performance Ranks (Speed x Precision) is:


NOTE: The performance of these methods depends highly on your processor and may change from one computer to another.




Algorithm: Babylonian Method + some manipulations on IEEE 32 bit floating point representation

float sqrt1(const float x)  
    int i;
    float x;
  } u;
  u.x = x;
  u.i = (1<<29) + (u.i >> 1) - (1<<22); 
  // Two Babylonian Steps (simplified from:)
  // u.x = 0.5f * (u.x + x/u.x);
  // u.x = 0.5f * (u.x + x/u.x);
  u.x =       u.x + x/u.x;
  u.x = 0.25f*u.x + x/u.x;

  return u.x;



Algorithm: The Magic Number (Quake 3)

#define SQRT_MAGIC_F 0x5f3759df 
 float  sqrt2(const float x)
  const float xhalf = 0.5f*x;
  union // get bits for floating value
    float x;
    int i;
  } u;
  u.x = x;
  u.i = SQRT_MAGIC_F - (u.i >> 1);  // gives initial guess y0
  return x*u.x*(1.5f - xhalf*u.x*u.x);// Newton step, repeating increases accuracy 



Algorithm: Log base 2 approximation and Newton's Method

float sqrt3(const float x)  
    int i;
    float x;
  } u;

  u.x = x;
  u.i = (1<<29) + (u.i >> 1) - (1<<22); 
  return u.x;


Reference: I got it a long time a go from a forum and I forgot, please contact me if you know its reference.

Algorithm: Bakhsali Approximation

float sqrt4(const float m)
   int i=0; 
   while( (i*i) <= m )
   float d = m - i*i; 
 float p=d/(2*i); 
 float a=i+p; 
   return a-(p*p)/(2*a);



Algorithm: Babylonian Method

   float sqrt5(const float m)
   float i=0;
   float x1,x2;
   while( (i*i) <= m )
   for(int j=0;j<10;j++)
   return x2;



Algorithm: Dependant on IEEE representation and only works for 32 bits

double sqrt6 (double y) 
    double x, z, tempf;
    unsigned long *tfptr = ((unsigned long *)&tempf) + 1;
    tempf = y;
   *tfptr = (0xbfcdd90a - *tfptr)>>1; 
 x =  tempf;
 z =  y*0.5;                       
 x = (1.5*x) - (x*x)*(x*z);    //The more you make replicates of this statement 
                               //the higher the accuracy, here only 2 replicates are used  
  x = (1.5*x) - (x*x)*(x*z);       
  return x*y; 



Algorithm: Dependant on IEEE representation and only works for 32 bits

float sqrt7(float x)
   unsigned int i = *(unsigned int*) &x; 
   // adjust bias
   i  += 127 << 23;
   // approximation of square root
   i >>= 1; 
   return *(float*) &i;



Algorithm: Babylonian Method

double sqrt9( const double fg)
 double n = fg / 2.0;
 double lstX = 0.0; 
 while(n != lstX)  
 lstX = n;
 n = (n + fg/n) / 2.0; 
 return n;



Algorithm: Babylonian Method

 double Abs(double Nbr)
 if( Nbr >= 0 ) 
  return Nbr; 
  return -Nbr;

double sqrt10(double Nbr)
 double Number = Nbr / 2; 
 const double Tolerance = 1.0e-7; 
  Number = (Number + Nbr / Number) / 2;
 }while( Abs(Number * Number - Nbr) > Tolerance);
 return Number;



Algorithm: Newton's Approximation Method

double sqrt11(const double number)e
const double ACCURACY=0.001;
double lower, upper, guess;

 if (number < 1)
  lower = number;
  upper = 1;
  lower = 1;
  upper = number;

 while ((upper-lower) > ACCURACY)
  guess = (lower + upper)/2;
  if(guess*guess > number)
   upper =guess;
   lower = guess; 
 return (lower + upper)/2;




Algorithm: Newton's Approximation Method

 double sqrt12( unsigned long N )
    double n, p, low, high;
    if( 2 > N )
        return( N );
    low  = 0;
    high = N;
    while( high > low + 1 )
        n = (high + low) / 2;
        p = n * n;
        if( N < p )
            high = n;
        else if( N > p )
            low = n;
    return( N == p ? n : low );



Algorithm: Babylonian Method

double sqrt13( int n )
	// double a = (eventually the main method will plug values into a)
	double a = (double) n;
	double x = 1;
	// For loop to get the square root value of the entered number.
	for( int i = 0; i < n; i++)
		x = 0.5 * ( x+a / x );
	return x;


Reference: N/A

Algorithm: Assembly fsqrt

double sqrt13(double n)
     fld n


Reference: N/A

Algorithm: Assembly fsqrt 2

double inline __declspec (naked) __fastcall sqrt14(double n)
	_asm fld qword ptr [esp+4]
	_asm fsqrt
	_asm ret 8


1.3 (15 September 2010)

  • Added Method N#14 (which is the best method till now)
  • Added modified source code

1.2 (24 June 2010)

  • Added Method N#13
  • Added the Methods Performance Rank
  • Added modified source code

1.1 (3 April 2010)

  • Added Precision Timer instead of clock because it's more precise
  • Added the average feature

1.0 (31 March 2010)

  • Initial release

I hope that this article would at least slightly help those who are interested in this issue.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Mahmoud Hesham El-Magdoub
Software Developer (Senior) Free Lancer
Egypt Egypt
BSc Computer Engineering, Cairo University, Egypt.

I love teaching and learning and I'm constantly changing Smile | :)
Feel free to discuss anything with me.

A Freelance UX designer, Code is my tool brush, I design for experience !

My Website

You may also be interested in...

Comments and Discussions

BugTimings Pin
Member 1138475128-Apr-15 9:11
memberMember 1138475128-Apr-15 9:11 
Questiongreat article - exactly what I need :-) Pin
Matth Moestl22-Apr-15 0:58
professionalMatth Moestl22-Apr-15 0:58 
QuestionNot sure methods are best Pin
Member 105861256-May-14 1:17
memberMember 105861256-May-14 1:17 
QuestionGCC code for testing Pin
Member 1055101029-Apr-14 20:58
memberMember 1055101029-Apr-14 20:58 
Questionobjective-c Pin
10z28-Apr-14 8:04
member10z28-Apr-14 8:04 
Suggestionanother way to do it Pin
Marcos Lohmann20-Nov-13 4:40
memberMarcos Lohmann20-Nov-13 4:40 
GeneralRe: another way to do it Pin
Marcos Lohmann20-Nov-13 5:41
memberMarcos Lohmann20-Nov-13 5:41 
SuggestionFurther advice on precision calculation Pin
Conor Manning22-Feb-13 8:22
memberConor Manning22-Feb-13 8:22 
QuestionGood Read Pin
Bassam Abdul-Baki29-May-12 7:26
memberBassam Abdul-Baki29-May-12 7:26 
AnswerRe: Good Read Pin
Mahmoud Hesham El-Magdoub5-Jun-12 20:33
memberMahmoud Hesham El-Magdoub5-Jun-12 20:33 
Questionactual time taken by the methods? Pin
utkarshs28-May-12 6:47
memberutkarshs28-May-12 6:47 
AnswerRe: actual time taken by the methods? Pin
Mahmoud Hesham El-Magdoub28-May-12 7:41
memberMahmoud Hesham El-Magdoub28-May-12 7:41 
GeneralRe: actual time taken by the methods? Pin
utkarshs29-May-12 17:19
memberutkarshs29-May-12 17:19 
GeneralRe: actual time taken by the methods? Pin
Mahmoud Hesham El-Magdoub5-Jun-12 20:40
memberMahmoud Hesham El-Magdoub5-Jun-12 20:40 
GeneralAn Improvement to method #13 (x86) Pin
Lior Kogan5-Jul-10 9:58
memberLior Kogan5-Jul-10 9:58 
GeneralRe: An Improvement to method #13 (x86) Pin
Mahmoud Hesham El-Magdoub15-Sep-10 6:47
memberMahmoud Hesham El-Magdoub15-Sep-10 6:47 
General[My vote of 2] Precision calculation is broken Pin
Peter_in_278028-Jun-10 14:14
memberPeter_in_278028-Jun-10 14:14 
Generalquick sqrt, precission 100 Pin
=asm=7-Jun-10 21:21
member=asm=7-Jun-10 21:21 
GeneralRe: quick sqrt, precission 100 Pin
Mahmoud Hesham El-Magdoub23-Jun-10 23:37
memberMahmoud Hesham El-Magdoub23-Jun-10 23:37 
GeneralRe: quick sqrt, precission 100 Pin
supercat924-Jun-10 5:11
membersupercat924-Jun-10 5:11 
GeneralRe: quick sqrt, precission 100 Pin
Mahmoud Hesham El-Magdoub24-Jun-10 5:16
memberMahmoud Hesham El-Magdoub24-Jun-10 5:16 
GeneralRe: quick sqrt, precission 100 Pin
John M. Drescher16-Sep-10 4:10
memberJohn M. Drescher16-Sep-10 4:10 
GeneralPythagorean sums Pin
Member 31739737-Apr-10 10:07
memberMember 31739737-Apr-10 10:07 
GeneralRe: Pythagorean sums Pin
Mahmoud Hesham El-Magdoub7-Apr-10 21:12
memberMahmoud Hesham El-Magdoub7-Apr-10 21:12 
GeneralGood overview Pin
S. Töpfer5-Apr-10 23:58
memberS. Töpfer5-Apr-10 23:58 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.151002.1 | Last Updated 15 Sep 2010
Article Copyright 2010 by Mahmoud Hesham El-Magdoub
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid