From: Josef 'Jupp' Schugt <jupp@...>
Date: 2007-08-26T02:01:20+09:00
Subject: Re: Inverse Square Root

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dave Pederson wrote:
> I was wondering if it is possible to include the quake fast inverse
> square root function in ruby?

I oppose this for three reasons:

1. Computing inverse square roots is already possible in Ruby with just
   one operation using the exponentiation operator

       ruby -e 'puts 0.0025 ** -0.50'
       20.0

   or with two operations using division and Math.sqrt

       ruby -e 'puts 1.0 / Math.sqrt(0.0025)'
       20.0

2. The fast computation of an inverse square root is too rarely used to
   be implemented as part of a general purpose language.

3. The algorithm is mediocre at best. Better ones with faster
   convergence are available - without much search one can find one that
   converges cubically (the one you proposed only converges
   quadratically):

   Task: Given $S$ compute $\frac{1}{\sqrt{S}}$.

   Solution: Starting from $x_0$ let

       \begin{equation}
           y_n = S \cdot {x_n}^2,
       \end{equation}

   and

       \begin{equation}
           x_{n+1} = \frac{x_n}{8} \cdot (15 - y_n \cdot (10 - 3 y_n))
       \end{equation}

   which can be evaluated in this way:

       void main() {
           double s = 0.0025;
           double x = 0.0, xn = 1.0, yn;
           while (x != xn) {
               yn = s * xn * xn;
               x = xn;
               xn *= 0.125 * (15.0 - yn * (10.0 - 3.0 * yn));
               printf("%.16f\n", xn);
           }
       }

   This algorithm can be found in Wikipedia at

       http://en.wikipedia.org/wiki/Methods_of_computing_square_roots


Please note that  20 = sqrt(400) = isqrt(1/400) = isqrt(0.0025).

Have fun,

Josef 'Jupp' Schugt
- --
Blog available at http://www.mynetcologne.de/~nc-schugtjo/blog/
PGP key with id 6CC6574F available at http://wwwkeys.de.pgp.net/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iD8DBQFG0GBbrhv7B2zGV08RAs0xAKCvVgf2K6jeKM3Qj5PinwfbP3sPEwCg6luF
OTscjST6YUwX9D8YjZXpkDg=
=iRgR
-----END PGP SIGNATURE-----