Desktop | Mobile
Monday, September 17, 2007, 04:59 AM JST
Posted by Yanto Suryono
Have you ever thought how your calculator computes the result when you press the "1/x" button ? and have you ever thought how your computer computes the reciprocal ?

Reciprocal of a value is a special case of a division, where the numerator is 1.0. In mathematical form, we can write it as follows:



\frac{1}{x} = y



where x is the operand and y is the result. Rewriting the equation gives us:



1-xy = 0



And expanding y to its binary representation gives us:



1-x \left(\sum_{i=n\_start}^{n\_end} a_i 2^i\right) = 0



Alright! Now we have a much nicer equation to solve, don't we ? For those we don't get it yet, all we have to do is to loop the i from the n_start to n_stop, check if the equation becomes negative if we set
ai to 1, and if it is, then ai is 0 for the particular i.

The nice thing is, all multiplications involved are with the power of two numbers, which either in software or hardware can be replaced with shift operations.

Below is a very simple Perl program to verify, which tests i from 32 to -32 (quite overkill! )


#!/usr/bin/perl

$X=$ARGV[0];

$n = 32;
$Y = 0.0;

printf("Digit x*y y\n");
while ($n >= -32) {
if (1 - $X * ($Y + 2**$n) > 0) {
$Y += 2**$n;
printf("2^%-3d %5.10f %5.10f\n", $n, $X*$Y, $Y);
}
$n--;
}

printf "\n";
printf "Computed Result: %.10f\n", $Y;
printf "Calculated Result: %.10f\n", 1.0/$X;


The program's output, with parameter of 2.345 is:


Digit x*y y
2^-2 0.5862500000 0.2500000000
2^-3 0.8793750000 0.3750000000
2^-5 0.9526562500 0.4062500000
2^-6 0.9892968750 0.4218750000
2^-8 0.9984570313 0.4257812500
2^-11 0.9996020508 0.4262695312
2^-13 0.9998883057 0.4263916016
2^-15 0.9999598694 0.4264221191
2^-16 0.9999956512 0.4264373779
2^-20 0.9999978876 0.4264383316
2^-21 0.9999990058 0.4264388084
2^-22 0.9999995649 0.4264390469
2^-23 0.9999998444 0.4264391661
2^-24 0.9999999842 0.4264392257
2^-28 0.9999999929 0.4264392294
2^-29 0.9999999973 0.4264392313
2^-30 0.9999999995 0.4264392322

Computed Result: 0.4264392322
Calculated Result: 0.4264392324


Note that the xy is updated towards 1.0 and y to the reciprocal of x (2.345) for each iteration.






Leave a Comment

Fields with * are required.