15,799,491 members
Articles / General Programming / Algorithms
Tip/Trick

# The Bisection Method and Calculating Nth Roots

Rate me:
10 Nov 2014CPOL1 min read 21.9K   5   9
This is how to use the bisection method to calculate the nth root of a positive real number.

## 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 nth 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).

C#
```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:

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

Now "`nroot`" will contain the nth 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.):
C#
```public static List<ComplexBigInteger> nthRoot(ComplexBigInteger value, int root, out ComplexBigInteger remainder)
```

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

## References

Written By
United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First Prev Next
 much faster Nth root C# implementation TheSquid15-Aug-23 6:42 TheSquid 15-Aug-23 6:42
 I have a much faster Nth root C# implementation especially for large N degrees: GitHub - TheSquidCombatant/TheSquid.Numerics.Extensions: C# implementation of an extension method to quickly calculate an Nth root for BigInteger value. By Nikolai TheSquid.[^]
 My vote of 5 Thomas ktg11-Nov-14 19:49 Thomas ktg 11-Nov-14 19:49
 Re: My vote of 5 Cryptonite12-Nov-14 10:44 Cryptonite 12-Nov-14 10:44
 Newton YvesDaoust11-Nov-14 4:07 YvesDaoust 11-Nov-14 4:07
 Re: Newton Cryptonite11-Nov-14 12:39 Cryptonite 11-Nov-14 12:39
 Re: Newton Cryptonite11-Nov-14 12:51 Cryptonite 11-Nov-14 12:51
 Re: Newton Torben Trindkaer Nielsen12-Nov-14 2:31 Torben Trindkaer Nielsen 12-Nov-14 2:31
 Re: Newton Cryptonite12-Nov-14 7:35 Cryptonite 12-Nov-14 7:35
 Last Visit: 31-Dec-99 19:00     Last Update: 11-Dec-23 13:12 Refresh 1