Square root calculation with iteration and recursion

ddanbe 2 3K Views

Whenever you hear the word recursion, factorials or Towers of Hanoi are never far away. Well here they get mentioned, because we are not going to talk about these guys at all!
Iteration and recursion are in fact quite similar: they both loop until a certain condition is met.
As an exercise, I wanted to iterate a function and also turn that iteration into a recursive call.
To try something different and not that difficult I used Heron’s method,(an ancient Greek) which is a simple formula to calculate a square root of a number. This method is a special case of the Newton-Raphson method, developed tens of centuries later. See wiki if you want details. Hope the comments in the code are sufficient to understand it all.
And of course if I or you ever want to calculate a square root, use Math.Sqrt!
But if for example you want to find a cubic root of a polynomial, iteration is a way to go. This is also a demo that C# is suitable to use in math applications.

sknake commented: great post +6 
using System;

namespace SquareRootMethods
{
    class Program
    {
        private const double VerySmall = 0.000000001;

        static void Main(string[] args)
        {
            // Number to take the square root of.
            double i = 4321.5; 
            // A good choice of a starting value limits the number of iterations.
            double x = InitVal(NumOfDigits(i));

            double r = HSqrt(i, x);          
            Console.WriteLine("The square root of {0} is (iterated) : {1}", i, r);

            double R = RecurHSqrt(i, x);
            Console.WriteLine("The square root of {0} is (recursive): {1}", i, R);

            Console.ReadKey();
        }

        // ----------------------------------------------------------------------------------
        // Determine the number of digits of a double without the fraction part.
        static int NumOfDigits(double d)
        {
            int n = (int)Math.Round(d); //
            int ndigs = 0;
            while (n > 0)
            {
                n/=10;
                ndigs++;
            }
            return ndigs;
        }

        // ----------------------------------------------------------------------------------
        // Set an initial value for the square root
        static double InitVal(int n)
        {
            return (n % 2) == 0 ? 7 * Math.Pow(10,(n - 2) / 2) : 2 * Math.Pow(10,(n - 1) / 2);
        }

        // ----------------------------------------------------------------------------------
        /// <summary>
        /// Calculate the square root of a number n according to Heron's method.
        /// This is a special case of the Newton-Raphson method.
        /// Iteration used.
        /// </summary>
        /// <param name="n"> The number to take the square root of.</param>
        /// <returns> Square root of number.</returns>
        static double HSqrt(double n, double x0)
        {        
            double x1 = x0;
            // Start loop and begin iteration
            do
            {
                // Set new calculated value to old value
                x0 = x1;
                // Calculate new value.
                x1 = 0.5 * (x0 + n / x0);
                // If the difference between the newly calculated value
                // and previous value gets small enough, we end the loop.
            } while (Math.Abs(x1 - x0) > VerySmall);
            return x1;
        }

        /// <summary>
        /// Calculate the square root of a number n according to Heron's method.
        /// This is a special case of the Newton-Raphson method.
        /// Recursion used.
        /// </summary>
        /// <param name="n"> The number to take the square root of.</param>
        /// <param name="x"> Initial guess.</param>
        /// <returns> Square root of number.</returns>
        static double RecurHSqrt(double n, double x)
        {
            if (Math.Abs(n - x * x) < VerySmall) return x;
            return RecurHSqrt(n, 0.5 * (x + n / x));
        }
    }
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview