fork download
copy 
  1. def bisection_recursive(lo, hi, a):
  2.  
  3.     if (hi - lo <= 0.00001):
  4.  
  5.         return (lo + hi) / 2
  6.  
  7.     else:
  8.  
  9.         m = (lo + hi) / 2
  10.  
  11.         if( f(lo, a) * f(m, a) < 0 ):
  12.             return bisection_recursive(lo, m, a)
  13.         else:
  14.             return bisection_recursive(m, hi, a)
  15.  
  16. def f(x, a):
  17.  
  18.     return x * x - a
  19.  
  20. def bisection(lo, hi, a):
  21.  
  22.     EPS = 0.00001
  23.  
  24.     while not hi - lo <= EPS:
  25.  
  26.         m = (lo + hi) / 2
  27.  
  28.         print(f'[{lo}, {hi}]', lo, hi)
  29.  
  30.         if f(lo, a) * f(m, a) < 0:
  31.  
  32.             hi = m
  33.  
  34.         else:
  35.  
  36.             lo = m
  37.  
  38.     return m
  39.  
  40. def bisection2(lo, hi, a):
  41.  
  42.     EPS = 0.00001
  43.  
  44.     while not hi - lo <= EPS:
  45.  
  46.         m = (lo + hi) / 2
  47.  
  48.         x = lo * lo - a
  49.         y = m * m - a
  50.  
  51.         print(f'[{lo}, {hi}]')
  52.  
  53.         print()
  54.  
  55.         if (x > 0 and y < 0) or (x < 0 and y > 0):
  56.  
  57.             hi = m
  58.  
  59.         else:
  60.  
  61.             lo = m
  62.  
  63.     return hi
  64.  
  65. def main():
  66.  
  67.     n = int(input())
  68.  
  69.     res = bisection2(0, n + 5, n)
  70.  
  71.     res_rec = bisection_recursive(0, n + 5, n)
  72.  
  73.     print(res)
  74.     print()
  75.     print(res_rec)
  76. main()
  77.  
Success #stdin #stdout 0.03s 9328KB
comments (?)
stdin
copy 
9
stdout
copy 
[0, 14]

[0, 7.0]

[0, 3.5]

[1.75, 3.5]

[2.625, 3.5]

[2.625, 3.0625]

[2.84375, 3.0625]

[2.953125, 3.0625]

[2.953125, 3.0078125]

[2.98046875, 3.0078125]

[2.994140625, 3.0078125]

[2.994140625, 3.0009765625]

[2.99755859375, 3.0009765625]

[2.999267578125, 3.0009765625]

[2.999267578125, 3.0001220703125]

[2.99969482421875, 3.0001220703125]

[2.999908447265625, 3.0001220703125]

[2.999908447265625, 3.0000152587890625]

[2.9999618530273438, 3.0000152587890625]

[2.999988555908203, 3.0000152587890625]

[2.999988555908203, 3.000001907348633]

3.000001907348633

2.9999985694885254
https://ideone.com/Gv4be7
Bisection Method for SQRT
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!