The Bisection Method and Calculating Nth Roots

Introduction

The bisection method is a root finding method in which intervals are repeatedly bisected into sub-intervals until a solution is found. It can be used to calculate square roots, cube roots, or any other root to any given precision (or until you run out of memory) of a positive real integer.

In the following example, the estimation of the square root (SQRT) of some value (v) can be generated from large integers by:

SQRT(v * 10^2d) / 10^d <---------  which gives d number of digits (in decimal or base 10)

This works because:

SQRT(v * 100) / 10  <---------  gives a single digit

SQRT(v * 10000) / 100  <---------  gives 2 digits

SQRT(v * 1000000) / 1000  <---------  gives 3 digits

We apply this algorithm to calculate a few digits of the square root of 2:

1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875
343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557
999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087
143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617
298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684
929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686
060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466
521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045
072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450
725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591
120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128
229518488472089694633862891562882765952635140542267653239694617511291602408715510135150455
381287560052631468017127402653969470240300517495318862925631385188163478001569369176881852
378684052287837629389214300655869568685964595155501644724509836896036887323114389415576651
040883914292338113206052433629485317049915771756228549741438999188021762430965206564211827
316726257539594717255934637238632261482742622208671155839599926521176252698917540988159348
640083457085181472231814204070426509056532333398436457865796796519267292399875366617215982
578860263363617827495994219403777753681426217738799194551397231274066898329989895386728822
856378697749662519966583525776198939322845344735694794962952168891485492538904755828834526
096524096542889394538646625744927556381964410316979833061852019379384940057156333720548068
540575867999670121372239475821426306585132217408832382947287617393647467837431960001592188
807347857617252211867490424977366929207311096369721608933708661156734585334833295254675851
644710757848602463600834449114818587655554286455123314219926311332517970608436559704352856
410087918500760361009159465670676883605571740076756905096136719401324935605240185999105062
108163597726431380605467010293569971042425105781749531057255934984451126922780344913506637
568747760283162829605532422426957534529028838768446429173282770888318087025339852338122749
990812371892540726475367850304821591801886167108972869229201197599880703818543332536460211
082299279293072871780799888099176741774108983060800326311816427988231171543638696617029999
34161614878686018045505553986913115186010386375325004558186044804075024119518430567453368

Background

I keep finding myself having to derive this same equation over and over again throughout the years for various applications. Will Microsoft ever give us a "SQRT" function for BigIntegers? Or any n^th root functions?

Using the Code

This code is in C#. You will have to add a reference to System.Numerics to use this code (in .NET 4.0 or higher).

public class BigMath
{
    /// <summary>
    /// Calculates the positive (and real) nth Root of the given positive (and real) value
    /// </summary>
    /// <param name="value">value</param>
    /// <param name="root">the root</param>
    /// <param name="remainder">remainder</param>
    /// <returns>the nth root of the value</returns>
    public static BigInteger nthRoot(BigInteger value, int root, out BigInteger remainder)
    {
        if (root < 1) throw new Exception("root must be greater than or equal to 1");
        if (value < 0) throw new Exception("value must be a positive integer");
        
        //special conditions
        if (value == 1)
        {
            remainder = 0;
            return 1;
        }
        if (value == 0)
        {
            remainder = 0;
            return 0;
        }
        if (root == 1)
        {
            remainder = 0;
            return value;
        }
        
        //set the upper and lower limits
        var upperbound = value;
        var lowerbound = BigInteger.Parse("0");
        
        while (true)
        {
            var nval = (upperbound + lowerbound) / 2;
            var tstsq = BigInteger.Pow(nval, root);
            if (tstsq > value) upperbound = nval;
            if (tstsq < value)
            {
                lowerbound = nval;
            }
            if (tstsq == value)
            {
                lowerbound = nval;
                break;
            }
            if (lowerbound == upperbound - 1) break;
        }
        remainder = value - BigInteger.Pow(lowerbound, root);
        return lowerbound;
    }
}

Call the nthRoot method like this:

BigInteger rm;
var nroot = BigMath.nthRoot(BigInteger.Parse("2" + new string('0', 100)), 2, out rm);

Now "nroot" will contain the n^th root and "rm" will contain the whole integer remainder.

Points of Interest

1. This formula is guaranteed to terminate
2. This method is very simple yet powerful
3. There might be huge speed-ups by initializing the upper and lower boundaries with log values
4. This method should be easily extendable into the complex plane (i.e.):

public static List<ComplexBigInteger> nthRoot(ComplexBigInteger value, int root, out ComplexBigInteger remainder)

where ComplexBigInteger is a structure containing the real and imaginary part.

References

• http://en.wikipedia.org/wiki/Bisection_method
• http://en.wikipedia.org/wiki/Newton%27s_method