Writing a Square Root function from scratch

• How it works?
• C#
• Python

Most of the modern programming languages we use today have built in libraries to handle mathematical functions.Every language ships with a rich math library that can easily handle most of the mathematical tasks.Finding square root is one. Calculating square roots is so prevalent,that most of us have the square roots memorized up to certain extent.System.Math.Sqrt() is the .Net's answer to this widely used function.It takes a double datatype as a single parameter and returns the square root(as double).Well before programming languages it was the handheld calculators that made this function a household among users.In all my years i have never manually calculated the square root of any number until  recently i read about a method called Newton-Raphson's method.There are few other methods like the Babylonian and indian bakshali approximation,which i suggest to have a look at.

How it works?

To find the square root of a Given Number N

   Maintain a variable called G,with a initial value of 1.//G=1;

   Maintain a variable called Q

   Maintain a variable called AVG

STEP 1: Divide N by G  (N/G) and store the result in a variable  Q

STEP 2: Calculate the Average of Q and G and store in AVG

STEP 3: Check if AVG = = G

                  If AVG != G 

                      Assign the value of AVG to G and repeat STEP 1 through 3

                  If AVG == G

                      Exit as Square root found.(Current value in AVG and G is the square root)

Complete Iteration for getting the square root of 9

G=1  ;  N=9   ;  Square root = 3

On the last row both the variable G's value and the Average(step 2) equals and that is where you get your square root.So when your value stored in G equals the Average calculated you can stop and come out.

How it works?

using System;
namespace SquareRoot
{
    class Program
    {
        static double inputNumber;
        static double guess = 1;
        static double quotient = 0;
        static double avg = 0;
        static bool exit = false;

        static void Main(string[] args)
        {
            Console.WriteLine("Please enter the number:");
            if (double.TryParse(Console.ReadLine(), out inputNumber))
            {
                while (!exit)
                {
                    quotient = inputNumber / guess;
                    avg = (guess + quotient) / 2;
                    if (avg == guess)
                        exit = true;
                    else
                        guess = avg;
                }
                Console.WriteLine("The Square root of " 
                                  + inputNumber + " is: " +guess);
            }
            else
                Console.WriteLine("Your input doesn't seem to be numeric");

            
            Console.ReadLine();
            
        }
    }
}

A short implementation of the same in python.

number=float(169)
guess=float(1)
exitLoop=False

while not exitLoop:
    quot=number/guess
    avg=(guess+quot)/2
    if avg == guess:
        exitLoop=True
    else:
        guess=avg
        
print("Square root {0} is {1}.".format(number,guess))

Project Euler - Problem 98

• Problem 98
• Solution
• Console output

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 36². What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 96². We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

First of all we need to find out all anagrams in the given file.For the few of you who may think what is an anagram.Anagram is a word, phrase, or name formed by rearranging the letters of another word.A Simple example of that are the words ITEM and TIME.Both of the words have same set of characters,but give different meanings when rearranged.The following piece of LINQ gets all anagrams in the file.

var anagrams_1=textContent.Split(',')
                          .Select(str => new CustomString(str));
var anagrams =  anagrams_1.GroupBy(cstr => cstr.sortedString)
                            .Where(g => g.Count() > 1)
                            .Select(g => g.Key);

textContent is a string datatype housing the entire textual content pulled off from word.txt file.The CustomString struct is created for every word in the file and it stores two different states.Sorted String state and the  Original string.A sorted string will have its letters sorted left to right in a alphabetical order.The unsorted string will maintain its original arrangement of letters.In the case of words TIME and ITEM ,the sorted and unsorted original state would look like below.

          CustomString for TIME : Sorted String : EIMT, Original String: TIME

          CustomString for ITEM : Sorted String : EIMT, Original String: ITEM

       

          If we compare the Sorted string(EIMT)of both the words we can conclude quickly that these

          two are anagrams.

struct CustomString {

 public char[] charArrayOrg;
 public char[] sortedCharArr;
 public string sortedString;
 public string originalString;

 public CustomString(String source) {

   charArrayOrg = source.ToCharArray();
   sortedCharArr = source.ToCharArray();
   Array.Sort(sortedCharArr);
   sortedString = new String(sortedCharArr);
   originalString = new String(charArrayOrg);

}}

The extension method Select() takes every string and transforms it to a CustomString object.Then all the objects are grouped by its SortedString state.Each group in the LINQ result set will correspond to a unique anagram from the word.txt file.

Next we need to generate all possible square numbers that match the length of every anagram word(Brute Force). And we need to positionally apply each of the digits to every character in the word starting from left to right.
Lets take the anagrams TIME and ITEM(both 4 letters) to get the explanation straight.Our squares should match the length of the anagrams,in this case we will consider 1225(4 digits) which is the square of 35.

                                    1  2  2   5

                                    T  I  M  E

In the next step we rearrange the letters to form its anagram ITEM.As we rearrange the numbers get shuffled as you can see below.

                                   2  1   5  2

                                   I   T  E  M 


ForEach loop for Rearranging the letters.

    
foreach (char ch in match.originalString)
{
    bool elePlaced = false;
    while (!elePlaced)
    {
        var idx = ele.originalString.IndexOf(ch, startSearchAt);
        if (shufflerList[idx] == '\0')
        {
            shufflerList.RemoveAt(idx);
            shufflerList.Insert(idx,    
                        sqrSeedString[match.originalString.IndexOf(ch)]);
            elePlaced = true;
        }
        else
            startSearchAt = idx + 1;
    }
    startSearchAt = 0;
}

Lastly we need to check whether the newly formed number is a square or not.2152 is not a square number.