Given a 32-bit floating point number x stored in IEEE 754 floating point format, find the inverse square root of x, i.e., x-1/2.
A simple solution is to do floating point arithmetic.
Following is an example function.
C++14
#include <bits/stdc++.h>
using namespace std;
float InverseSquareRoot( float x)
{
return 1/ sqrt (x);
}
int main()
{
cout << InverseSquareRoot(0.5) << endl;
cout << InverseSquareRoot(3.6) << endl;
cout << InverseSquareRoot(1.0) << endl;
return 0;
}
|
Java
import java.io.*;
class GFG {
static float InverseSquareRoot( float x)
{
return 1 / ( float )Math.sqrt(x);
}
public static void main(String[] args)
{
System.out.println(InverseSquareRoot( 0 .5f));
System.out.println(InverseSquareRoot( 3 .6f));
System.out.println(InverseSquareRoot( 1 .0f));
}
}
|
Python3
from math import ceil, sqrt
def InverseSquareRoot(x) :
return 1 / sqrt(x)
print (InverseSquareRoot( 0.5 ) )
print (InverseSquareRoot( 3.6 ) )
print (InverseSquareRoot( 1.0 ) )
|
C#
using System;
class GFG {
static float InverseSquareRoot( float x)
{
return 1 / ( float )Math.Sqrt(x);
}
public static void Main()
{
Console.WriteLine(InverseSquareRoot(0.5f));
Console.WriteLine(InverseSquareRoot(3.6f));
Console.WriteLine(InverseSquareRoot(1.0f));
}
}
|
Javascript
<script>
function InverseSquareRoot(x)
{
return 1 / Math.sqrt(x);
}
document.write(InverseSquareRoot(0.5) + "<br/>" );
document.write(InverseSquareRoot(3.6) + "<br/>" );
document.write(InverseSquareRoot(1.0) + "<br/>" );
</script>
|
Output
1.41421
0.527046
1
Time Complexity: O(1)
Auxiliary Space: O(1)
Following is a fast and interesting method based for the same. See this for a detailed explanation.
C++14
#include <bits/stdc++.h>
using namespace std;
float InverseSquareRoot( float x)
{
float xhalf = 0.5f * x;
int i = *( int *)&x;
i = 0x5f3759d5 - (i >> 1);
x = *( float *)&i;
x = x * (1.5f - xhalf * x * x);
return x;
}
int main()
{
cout << InverseSquareRoot(0.5) << endl;
cout << InverseSquareRoot(3.6) << endl;
cout << InverseSquareRoot(1.0) << endl;
return 0;
}
|
Java
public class Main {
static float inverseSquareRoot( float x)
{
float xhalf = 0 .5f * x;
int i = Float.floatToIntBits(x);
i = 0x5f3759d5 - (i >> 1 );
x = Float.intBitsToFloat(i);
x = x * ( 1 .5f - xhalf * x * x);
return x;
}
public static void main(String[] args)
{
System.out.println(inverseSquareRoot( 0 .5f));
System.out.println(inverseSquareRoot( 3 .6f));
System.out.println(inverseSquareRoot( 1 .0f));
}
}
|
Python3
import struct
def inverse_square_root(x):
xhalf = 0.5 * x
i = struct.unpack( 'i' , struct.pack( 'f' , x))[ 0 ]
i = 0x5f3759d5 - (i >> 1 )
x = struct.unpack( 'f' , struct.pack( 'i' , i))[ 0 ]
x = x * ( 1.5 - xhalf * x * x)
return x
print (inverse_square_root( 0.5 ))
print (inverse_square_root( 3.6 ))
print (inverse_square_root( 1.0 ))
|
C#
using System;
public class MainClass
{
static float inverseSquareRoot( float x)
{
float xhalf = 0.5f * x;
int i = BitConverter.ToInt32(BitConverter.GetBytes(x), 0);
i = 0x5f3759d5 - (i >> 1);
x = BitConverter.ToSingle(BitConverter.GetBytes(i), 0);
x = x * (1.5f - xhalf * x * x);
return x;
}
public static void Main( string [] args)
{
Console.WriteLine(inverseSquareRoot(0.5f));
Console.WriteLine(inverseSquareRoot(3.6f));
Console.WriteLine(inverseSquareRoot(1.0f));
}
}
|
Javascript
function inverseSquareRoot(x) {
let xhalf = 0.5 * x;
let i = new Float32Array(1);
let y = new Int32Array(i.buffer);
i[0] = x;
y[0] = 0x5f3759d5 - (y[0] >> 1);
x = i[0];
x = x * (1.5 - xhalf * x * x);
return x;
}
console.log(inverseSquareRoot(0.5));
console.log(inverseSquareRoot(3.6));
console.log(inverseSquareRoot(1.0));
|
Output
1.41386
0.526715
0.998307
Time Complexity: O(1)
Auxiliary Space: O(1)
Source:
http://en.wikipedia.org/wiki/Fast_inverse_square_root