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).
public class BigMath
{
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");
if (value == 1)
{
remainder = 0;
return 1;
}
if (value == 0)
{
remainder = 0;
return 0;
}
if (root == 1)
{
remainder = 0;
return value;
}
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 nth root and "rm
" will contain the whole integer remainder.
Points of Interest
- This formula is guaranteed to terminate
- This method is very simple yet powerful
- There might be huge speed-ups by initializing the upper and lower boundaries with log values
- 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