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:
Post a Comment