Friday, October 10, 2008

F# square root approximation function

So I've been messing around in F#, trying to get a feel for the language, when a suitable challenge crossed my mind while reading an article on neat hacks. In particular, a square root approximation hack used in Quake 3. I'm not going to duplicate that code - what I really wanted to do was make something legitimate, so I went with Newton's Iteration function instead.

The idea is simple - starting with your number, and a guess at the square root of the number, iteratively refine the guess using simple arithmetic until you've decided that your guess is close enough.

Here's my implementation, in C#:

    1 static decimal mySqrt(decimal number, int iterations) {

    2     Func<decimal, int, decimal> rec = null; rec = (guess, iter) =>

    3     {

    4         if (iter == 0) return guess;

    5         return rec((guess + (number / guess)) / 2, iter - 1);

    6     };

    7 

    8     return rec(number / 2, iterations);

    9 }


This implementation uses a recursive lambda function. I could have stuck with a for-loop which would have been more efficient in C#, but my ultimate goal was to use this problem to help me understand F# better. Here's the same function in F#:

    1 #light

    2 

    3 let fsqrt n i =

    4   let rec guess g i =

    5     match i with

    6     | 0 -> g

    7     | _ -> guess ((g + (n / g)) / 2M) (i - 1)

    8   guess (n / 2M) i;;


In both of these functions I'm allowing the caller to specify how many refining iterations to perform. I'm considering writing a method that will determine the fitness of a guess.

I'd like to compare this solution against the official .NET implementation of Math.Sqrt, but unfortunately that function is a stub - it's implemented in MSVCRT by calling the 'fsqrt' opcode, as answered in my StackOverflow question on the subject. If anyone has any more insight into how this works on the processor, please post an answer there - I *really* want to know how it works...

No comments: