Java - Find SQRT using Algorithm

You can solve the problem in two ways with out using the built in function System.Math.Sqrt.

Method 1 - Like binary search, have a minimum and maximum possible values. Do the square operation and compare the result. Then adjust minimum or maximum until we find the correct sqrt of the given number. NOTE: This is NOT a perfect square root and it has got accuracy of 4 decimal points. To access the Java source code for method1, click here.

Method 2 - The traditional way of doing with out calculator or any assumption is using the algorithm. It will be perfect square root up to N number of decimal points meaning the limitation of float and double. Method 2 is explained on this page.

Source Code

import java.io.*;

import java.lang.*;

class SqrtAlgorithm

{

public static double SqrtByAlogorithm(double x)

{

long numeric = (long)x;

long n = numeric;

long fraction = (long)((x - numeric) * 1000000); // 6 digits

long f = fraction;

int numdigits = 0, fnumdigits = 0, currdigits = 0;

int tempresult = 0;

int bOdd = 0, part = 0, tens = 1;

int fractioncount = 0;

double result = 0;

int k, f1, f2, i, num, temp, quotient;

for (numdigits = 0; n >= 10; numdigits++)

n = (n / 10);

numdigits++;

for (fnumdigits = 0; f >= 10; fnumdigits++)

f = (f / 10);

fnumdigits++;

if ((numdigits % 2) == 1)

bOdd = 1;

while (true)

{

tens = 1;

currdigits = (bOdd == 1) ? (numdigits - 1) : (numdigits - 2);

for (k = 0; k < currdigits; k++)

tens *= 10;

part = (int)numeric / tens;

// Get the Nearest Multiplication Factor

num = part;

quotient = tempresult * 2;

i = 0;

temp = 0;

for (i = 1; ; i++)

{

if (quotient == 0)

{

if (num - i * i < 0)

{

tempresult = (i - 1);

break;

}

}

else

{

temp = quotient * 10 + i;

if (num - i * temp < 0)

{

tempresult = quotient / 2 * 10 + i - 1;

break;

}

}

}

// Done with Nearest Multiplication Factor

f1 = tempresult / 10;

f2 = tempresult % 10;

if (f1 == 0)

numeric = numeric - (tempresult * tempresult * tens);

else

numeric = numeric - ((f1 * 2 * 10 + f2) * f2 * tens);

if (numeric == 0 && fraction == 0)

{

if (currdigits > 0)

{

// Handle the Zero case

tens = 1;

currdigits = currdigits / 2;

for (k = 0; k < currdigits; k++)

tens *= 10;

tempresult *= tens;

}

break;

}

if (bOdd == 1)

{

numdigits -= 1;

bOdd = 0;

}

else

numdigits -= 2;

if (numdigits <= 0)

{

if (numeric > 0 || fraction > 0)

{

if (fractioncount >= 5)

break;

// Handle the fraction part for integer numbers

fractioncount++;

numeric *= 100;

if (fraction > 0)

{

// Handle the fraction part for real numbers

fnumdigits -= 2;

tens = 1;

for (k = 0; k < fnumdigits; k++)

tens *= 10;

numeric += fraction / tens;

fraction = fraction % tens;

}

numdigits += 2;

}

else

break;

}

}

if (fractioncount == 0)

result = tempresult;

else

{

tens = 1;

for (k = 0; k < fractioncount; k++)

tens *= 10;

result = (double)tempresult / tens;

}

return result;

}

public static void main(String[] args)

{

for (double d = 0; d <= 10000; d += 50)

{

System.out.print("sqrt(");

System.out.print(d);

System.out.print(") = ");

System.out.print(SqrtByAlogorithm(d));

System.out.print(", ");

System.out.println(Math.sqrt(d));

}

}

}

Output

D:\Program Files\Java\jdk1.6.0_23\bin>javac SqrtAlgorithm.java

D:\Program Files\Java\jdk1.6.0_23\bin>java SqrtAlgorithm

sqrt(0.0) = 0.0, 0.0

sqrt(50.0) = 7.07106, 7.0710678118654755

sqrt(100.0) = 10.0, 10.0

sqrt(150.0) = 12.24744, 12.24744871391589

sqrt(200.0) = 14.14213, 14.142135623730951

sqrt(250.0) = 15.81138, 15.811388300841896

sqrt(300.0) = 17.3205, 17.320508075688775

sqrt(350.0) = 18.70828, 18.708286933869708

sqrt(400.0) = 20.0, 20.0

sqrt(450.0) = 21.2132, 21.213203435596427

sqrt(500.0) = 22.36067, 22.360679774997898

sqrt(550.0) = 23.45207, 23.45207879911715

sqrt(600.0) = 24.49489, 24.49489742783178

sqrt(650.0) = 25.49509, 25.495097567963924

sqrt(700.0) = 26.45751, 26.457513110645905

sqrt(750.0) = 27.38612, 27.386127875258307

sqrt(800.0) = 28.28427, 28.284271247461902

sqrt(850.0) = 29.15475, 29.154759474226502

sqrt(900.0) = 30.0, 30.0

sqrt(950.0) = 30.82207, 30.822070014844883

sqrt(1000.0) = 31.62277, 31.622776601683793

sqrt(1050.0) = 32.4037, 32.4037034920393

sqrt(1100.0) = 33.16624, 33.166247903554

sqrt(1150.0) = 33.91164, 33.91164991562634

sqrt(1200.0) = 34.64101, 34.64101615137755

sqrt(1250.0) = 35.35533, 35.35533905932738

sqrt(1300.0) = 36.05551, 36.05551275463989

sqrt(1350.0) = 36.74234, 36.742346141747674

sqrt(1400.0) = 37.41657, 37.416573867739416

sqrt(1450.0) = 38.07886, 38.07886552931954

sqrt(1500.0) = 38.72983, 38.72983346207417

sqrt(1550.0) = 39.37003, 39.370039370059054

sqrt(1600.0) = 40.0, 40.0

sqrt(1650.0) = 40.62019, 40.620192023179804

sqrt(1700.0) = 41.23105, 41.23105625617661

sqrt(1750.0) = 41.833, 41.83300132670378

sqrt(1800.0) = 42.4264, 42.42640687119285

sqrt(1850.0) = 43.01162, 43.01162633521314

sqrt(1900.0) = 43.58898, 43.58898943540674

sqrt(1950.0) = 44.1588, 44.15880433163923

sqrt(2000.0) = 44.72135, 44.721359549995796

sqrt(2050.0) = 45.27692, 45.27692569068709

sqrt(2100.0) = 45.82575, 45.8257569495584

sqrt(2150.0) = 46.36809, 46.36809247747852

sqrt(2200.0) = 46.90415, 46.9041575982343

sqrt(2250.0) = 47.43416, 47.43416490252569

sqrt(2300.0) = 47.95831, 47.958315233127195

sqrt(2350.0) = 48.47679, 48.47679857416329

sqrt(2400.0) = 48.98979, 48.98979485566356

sqrt(2450.0) = 49.49747, 49.49747468305833

sqrt(2500.0) = 50.0, 50.0

sqrt(2550.0) = 50.49752, 50.49752469181039

sqrt(2600.0) = 50.99019, 50.99019513592785

sqrt(2650.0) = 51.47815, 51.478150704935004

sqrt(2700.0) = 51.96152, 51.96152422706632

sqrt(2750.0) = 52.44044, 52.44044240850758

sqrt(2800.0) = 52.91502, 52.91502622129181

sqrt(2850.0) = 53.38539, 53.38539126015655

sqrt(2900.0) = 53.85164, 53.85164807134504

sqrt(2950.0) = 54.3139, 54.31390245600108

sqrt(3000.0) = 54.77225, 54.772255750516614

sqrt(3050.0) = 55.2268, 55.226805085936306

sqrt(3100.0) = 55.67764, 55.67764362830022

sqrt(3150.0) = 56.12486, 56.124860801609124

sqrt(3200.0) = 56.56854, 56.568542494923804

sqrt(3250.0) = 57.00877, 57.0087712549569

sqrt(3300.0) = 57.44562, 57.445626465380286

sqrt(3350.0) = 57.87918, 57.879184513951124

sqrt(3400.0) = 58.30951, 58.309518948453004

sqrt(3450.0) = 58.7367, 58.73670062235365

sqrt(3500.0) = 59.16079, 59.16079783099616

sqrt(3550.0) = 59.58187, 59.58187643906493

sqrt(3600.0) = 60.0, 60.0

sqrt(3650.0) = 60.41522, 60.41522986797286

sqrt(3700.0) = 60.82762, 60.8276253029822

sqrt(3750.0) = 61.23724, 61.237243569579455

sqrt(3800.0) = 61.64414, 61.644140029689765

sqrt(3850.0) = 62.04836, 62.048368229954285

sqrt(3900.0) = 62.44997, 62.44997998398398

sqrt(3950.0) = 62.84902, 62.849025449882674

sqrt(4000.0) = 63.24555, 63.245553203367585

sqrt(4050.0) = 63.63961, 63.63961030678928

sqrt(4100.0) = 64.03124, 64.03124237432849

sqrt(4150.0) = 64.42049, 64.42049363362563

sqrt(4200.0) = 64.8074, 64.8074069840786

sqrt(4250.0) = 65.19202, 65.19202405202648

sqrt(4300.0) = 65.57438, 65.57438524302

sqrt(4350.0) = 65.95452, 65.95452979136459

sqrt(4400.0) = 66.33249, 66.332495807108

sqrt(4450.0) = 66.70832, 66.70832032063167

sqrt(4500.0) = 67.08203, 67.08203932499369

sqrt(4550.0) = 67.45368, 67.45368781616021

sqrt(4600.0) = 67.82329, 67.82329983125268

sqrt(4650.0) = 68.1909, 68.19090848492928

sqrt(4700.0) = 68.55654, 68.55654600401044

sqrt(4750.0) = 68.92024, 68.92024376045111

sqrt(4800.0) = 69.28203, 69.2820323027551

sqrt(4850.0) = 69.64194, 69.6419413859206

sqrt(4900.0) = 70.0, 70.0

sqrt(4950.0) = 70.35623, 70.35623639735144

sqrt(5000.0) = 70.71067, 70.71067811865476

sqrt(5050.0) = 71.06335, 71.06335201775947

sqrt(5100.0) = 71.41428, 71.4142842854285

sqrt(5150.0) = 71.7635, 71.76350047203663

sqrt(5200.0) = 72.11102, 72.11102550927978

sqrt(5250.0) = 72.45688, 72.4568837309472

sqrt(5300.0) = 72.80109, 72.80109889280519

sqrt(5350.0) = 73.14369, 73.14369419163897

sqrt(5400.0) = 73.48469, 73.48469228349535

sqrt(5450.0) = 73.82411, 73.824115301167

sqrt(5500.0) = 74.16198, 74.16198487095663

sqrt(5550.0) = 74.49832, 74.4983221287567

sqrt(5600.0) = 74.83314, 74.83314773547883

sqrt(5650.0) = 75.16648, 75.16648189186454

sqrt(5700.0) = 75.49834, 75.49834435270749

sqrt(5750.0) = 75.82875, 75.82875444051551

sqrt(5800.0) = 76.15773, 76.15773105863909

sqrt(5850.0) = 76.48529, 76.48529270389177

sqrt(5900.0) = 76.81145, 76.81145747868608

sqrt(5950.0) = 77.13624, 77.13624310270757

sqrt(6000.0) = 77.45966, 77.45966692414834

sqrt(6050.0) = 77.78174, 77.78174593052023

sqrt(6100.0) = 78.10249, 78.10249675906654

sqrt(6150.0) = 78.42193, 78.4219357067906

sqrt(6200.0) = 78.74007, 78.74007874011811

sqrt(6250.0) = 79.05694, 79.05694150420949

sqrt(6300.0) = 79.37253, 79.37253933193772

sqrt(6350.0) = 79.68688, 79.68688725254614

sqrt(6400.0) = 80.0, 80.0

sqrt(6450.0) = 80.31189, 80.31189202104505

sqrt(6500.0) = 80.62257, 80.62257748298549

sqrt(6550.0) = 80.93207, 80.93207028119323

sqrt(6600.0) = 81.24038, 81.24038404635961

sqrt(6650.0) = 81.54753, 81.54753215150045

sqrt(6700.0) = 81.85352, 81.8535277187245

sqrt(6750.0) = 82.15838, 82.15838362577492

sqrt(6800.0) = 82.46211, 82.46211251235322

sqrt(6850.0) = 82.76472, 82.76472678623425

sqrt(6900.0) = 83.06623, 83.06623862918075

sqrt(6950.0) = 83.36666, 83.36666000266533

sqrt(7000.0) = 83.666, 83.66600265340756

sqrt(7050.0) = 83.96427, 83.96427811873333

sqrt(7100.0) = 84.26149, 84.26149773176358

sqrt(7150.0) = 84.55767, 84.55767262643882

sqrt(7200.0) = 84.85281, 84.8528137423857

sqrt(7250.0) = 85.14693, 85.14693182963201

sqrt(7300.0) = 85.44003, 85.44003745317531

sqrt(7350.0) = 85.73214, 85.73214099741124

sqrt(7400.0) = 86.02325, 86.02325267042627

sqrt(7450.0) = 86.31338, 86.31338250816034

sqrt(7500.0) = 86.60254, 86.60254037844386

sqrt(7550.0) = 86.89073, 86.89073598491383

sqrt(7600.0) = 87.17797, 87.17797887081348

sqrt(7650.0) = 87.46427, 87.46427842267951

sqrt(7700.0) = 87.74964, 87.74964387392122

sqrt(7750.0) = 88.03408, 88.03408430829505

sqrt(7800.0) = 88.3176, 88.31760866327846

sqrt(7850.0) = 88.60022, 88.60022573334675

sqrt(7900.0) = 88.88194, 88.88194417315589

sqrt(7950.0) = 89.16277, 89.16277250063504

sqrt(8000.0) = 89.44271, 89.44271909999159

sqrt(8050.0) = 89.72179, 89.7217922246318

sqrt(8100.0) = 90.0, 90.0

sqrt(8150.0) = 90.27735, 90.27735042633894

sqrt(8200.0) = 90.55385, 90.55385138137417

sqrt(8250.0) = 90.82951, 90.82951062292474

sqrt(8300.0) = 91.10433, 91.10433579144299

sqrt(8350.0) = 91.37833, 91.37833441248533

sqrt(8400.0) = 91.65151, 91.6515138991168

sqrt(8450.0) = 91.92388, 91.92388155425118

sqrt(8500.0) = 92.19544, 92.19544457292888

sqrt(8550.0) = 92.46621, 92.46621004453465

sqrt(8600.0) = 92.73618, 92.73618495495704

sqrt(8650.0) = 93.00537, 93.00537618869137

sqrt(8700.0) = 93.27379, 93.27379053088815

sqrt(8750.0) = 93.54143, 93.54143466934853

sqrt(8800.0) = 93.80831, 93.8083151964686

sqrt(8850.0) = 94.07443, 94.0744386111339

sqrt(8900.0) = 94.33981, 94.33981132056604

sqrt(8950.0) = 94.60443, 94.6044396421225

sqrt(9000.0) = 94.86832, 94.86832980505137

sqrt(9050.0) = 95.13148, 95.13148795220224

sqrt(9100.0) = 95.39392, 95.39392014169457

sqrt(9150.0) = 95.65563, 95.65563234854496

sqrt(9200.0) = 95.91663, 95.91663046625439

sqrt(9250.0) = 96.17692, 96.17692030835673

sqrt(9300.0) = 96.4365, 96.43650760992955

sqrt(9350.0) = 96.69539, 96.69539802906858

sqrt(9400.0) = 96.95359, 96.95359714832658

sqrt(9450.0) = 97.21111, 97.21111047611791

sqrt(9500.0) = 97.46794, 97.46794344808964

sqrt(9550.0) = 97.7241, 97.72410142846032

sqrt(9600.0) = 97.97958, 97.97958971132712

sqrt(9650.0) = 98.23441, 98.2344135219425

sqrt(9700.0) = 98.48857, 98.48857801796105

sqrt(9750.0) = 98.74208, 98.74208829065749

sqrt(9800.0) = 98.99494, 98.99494936611666

sqrt(9850.0) = 99.24716, 99.24716620639605

sqrt(9900.0) = 99.49874, 99.498743710662

sqrt(9950.0) = 99.74968, 99.74968671630002

sqrt(10000.0) = 100.0, 100.0