example - finding the next decimal place of accuracy
The method here calculates the next decimal place of the adjacent values that are less than and greater than the root of the number we are looking for. (There is another method where the interval is always halved)
The square root of 12 lies between 3 and 4 as $${3^2 = 9 < 12 < 16 = 4^2}$$ Similarly $${3.4^2 < 12 < 3.5^2}$$ so $${3.4 < \sqrt{12} < 3.5}$$ and so on
input
user@linux-pc:~$ python nested_intervals.py -i 12
____ ____ ___ ______
| \ \ \ |
| D | | | _|
| / O | O | |
| |\ \ | | |
|_| \_\___/\___/___| Nested Intervals Algorithm
(c) sdw
the square root of 12.0 lies in the interval:
3.0 4.0
3.4 3.5
3.46 3.47
3.464 3.465
3.4641 3.4642
3.4641 3.46411
3.464101 3.464102
3.4641016 3.4641017
3.46410161 3.46410162
3.464101615 3.464101616
Here is the script
python script - nested intervals
# /bin/python #############
# nested_intervals.py #
###########################
import math
import re
import os
import sys
import string
from optparse import OptionParser
def logo():
print('')
print(' ____ ____ ___ ______')
print('| \ \ \ |')
print('| D | | | _|')
print('| / O | O | |')
print('| |\ \ | | |')
print('|_| \_\___/\___/___| Nested Intervals Algorithm')
print(' (c) sdw')
print('')
def calc_root(x_value,n_iter):
new_x = x_value
a = 0
i = 0
print "the square root of", x_value, "lies in the interval:"
print('')
for i in range(n_iter):
while a**2 < new_x: # -- check for new upper and lower limit
a = float(a + 1*10**(-i))
b = a
new_a = float(b - 1*10**(-i))
print('{:>20} {:<20}'.format(new_a,b)) # algorithm repaired 20211012
a = float(new_a) # + 1*10**(-(i+1)))
#a = float(new_a + 1*10**(-(i+1)))
#print a
i = i + 1
def main():
logo()
parser = OptionParser(usage='"%prog -i square_root [-n number_of_iterations]"')
parser.add_option("-i", dest="sqroot", help="enter the root you want to calculate")
parser.add_option("-n", dest="iter", help="enter the number of iterations")
(options, args) = parser.parse_args()
if not options.sqroot:
parser.error('no root given, use -i [square root]')
sq_value = float(options.sqroot)
if options.iter:
n_iter = int(options.iter)
if n_iter > 12:
print ("number of iterations is too high")
else:
calc_root(sq_value,n_iter)
else:
n_iter = 10
calc_root(sq_value,n_iter)
if __name__ == "__main__":
main()
method of halving the interval - halbieren des Intervalls
Here, in this method, you find the mid-value m of an interval [a,b]. Then, square the mid-value to determine in which section the square root lies. This gives you either [a,m] or [m,b] as the next interval. Now, repeat the process, over and over again until you have the desired accuracy.
example
output
user@linux-pc:~$ python halving_intervals.py -i 12 -n 36
____ ____ ___ ______
| \ \ \ |
| D | | | _|
| / O | O | |
| |\ \ | | |
|_| \_\___/\___/___| Halving Intervals Algorithm
(c) sdw
[ 3.0000000000 , 4.0000000000 ]
[ 3.0000000000 , 3.5000000000 ]
[ 3.2500000000 , 3.5000000000 ]
[ 3.3750000000 , 3.5000000000 ]
[ 3.4375000000 , 3.5000000000 ]
[ 3.4375000000 , 3.4687500000 ]
[ 3.4531250000 , 3.4687500000 ]
[ 3.4609375000 , 3.4687500000 ]
[ 3.4609375000 , 3.4648437500 ]
[ 3.4628906250 , 3.4648437500 ]
[ 3.4638671875 , 3.4648437500 ]
[ 3.4638671875 , 3.4643554688 ]
[ 3.4638671875 , 3.4641113281 ]
[ 3.4639892578 , 3.4641113281 ]
[ 3.4640502930 , 3.4641113281 ]
[ 3.4640808105 , 3.4641113281 ]
[ 3.4640960693 , 3.4641113281 ]
[ 3.4640960693 , 3.4641036987 ]
[ 3.4640998840 , 3.4641036987 ]
[ 3.4640998840 , 3.4641017914 ]
[ 3.4641008377 , 3.4641017914 ]
[ 3.4641013145 , 3.4641017914 ]
[ 3.4641015530 , 3.4641017914 ]
[ 3.4641015530 , 3.4641016722 ]
[ 3.4641016126 , 3.4641016722 ]
[ 3.4641016126 , 3.4641016424 ]
[ 3.4641016126 , 3.4641016275 ]
[ 3.4641016126 , 3.4641016200 ]
[ 3.4641016126 , 3.4641016163 ]
[ 3.4641016144 , 3.4641016163 ]
[ 3.4641016144 , 3.4641016154 ]
[ 3.4641016149 , 3.4641016154 ]
[ 3.4641016151 , 3.4641016154 ]
[ 3.4641016151 , 3.4641016152 ]
[ 3.4641016151 , 3.4641016152 ]
[ 3.4641016151 , 3.4641016152 ]
script
python script for halving the intervals
# /bin/python ------------------------------
# nested intervals - halving_intervals.py
# (c) Sebastian Williams
#--------------------------------------------
import math
import re
import os
import sys
import string
from Tkinter import *
from optparse import OptionParser
def calc_root(x_value,n_iter):
new_x = x_value
a = 0
b = 1
i = 0
while (b**2 <= new_x): #--- check if the upper limit squared is still less
a = a + 1 #--- than the root
b = b + 1
while (i < n_iter):
m = float((a + b)/2) # -- halve the current interval
if (m**2 < new_x): # -- check for new upper and lower limit
a = m
b = b
else:
if (m**2 > new_x):
b = m
a = a
i = i +1
print '[',("{0:.10f}".format(a)),#' m=', ("{0:.10f}".format(m)),' ', ("{0:.10f}".format(b)),'] '#, ("{0:.4f}".format(a**2)), ("{0:.4f}".format(m**2)), ("{0:.4f}".format(b**2))
print ', ',("{0:.10f}".format(b)),']'
def main():
parser = OptionParser(usage='"%prog -i date"')
parser.add_option("-i", dest="sqroot", help="enter the root you want to calulate")
parser.add_option("-n", dest="iter", help="enter the number of iterations")
(options, args) = parser.parse_args()
if not options.sqroot:
parser.error('no root given, use -i [square root]')
sq_value = float(options.sqroot)
if options.iter:
num_iter = float(options.iter)
calc_root(sq_value,num_iter)
else:
num_iter = 7
calc_root(sq_value,num_iter)
#graphic_display()
if __name__ == "__main__":
main()
Which algorithm is faster?
Hero of Alexandria - the Babylonian method
you can see the process on the following page