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
|
|