How does the math module work? The formula, function is written in that module. I need to write in my program the function of calculating the root from a number without using "import math", but I cannot find the module device anywhere (to take it as a basis). PS help with code

  • First: thanks for the reply. Secondly: I know this function of the module, and thirdly, I wrote, I need NOT to USE the module - Alexander Bubnov
  • The math module most likely calls the native sqrt function from the C mathematical library. - dzhioev
  • And you can paint the sqrt function (I’m looking for the device of this function)? - Alexander Bubnov
  • Here you can find several algorithms - MaxU
  • Alexander, if my answer helped you, then mark it as a solution. - Xander

3 answers 3

First, calculate the two extreme points - the unit and the original number itself. Then take the first sample from the gap between these extreme points. For example, you can take their arithmetic average.

Square the sample and compare with the original number. If more - then choose the next sample as half the gap between the old sample and the lower extreme number. And the new large number becomes the old test. If it is less, then, respectively, a new sample is taken as half between the old sample and the large extreme number. And the new less extreme number is the old trial.

And in this way, each time specifying the values ​​of the sample and the extreme numbers, repeat until the difference between the initial number and the square of the sample becomes less than some predetermined permissible error.

UPD: If it is more convenient for you to see formulas before your eyes than a text description, you can google on request "numerical methods square root". For example. Here is the very first link to a good Wikipedia article. There, the algorithm is slightly different than the one that I cited, but it is based on the same principle of successive approximations. https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BD%D0 % B0% D1% 85% D0% BE% D0% B6% D0% B4% D0% B5% D0% BD% D0% B8% D1% 8F_% D0% BA% D0% BE% D1% 80% D0% BD % D1% 8F_n-% D0% BD% D0% BE% D0% B9_% D1% 81% D1% 82% D0% B5% D0% BF% D0% B5% D0% BD% D0% B8

    There are many algorithms for calculating the root of a number, for example, the book Structure and Interpretation of Computer Programs shows a simple solution using the Newton method :

     def sqrt(x): guess = 1.0 while not good_enough(guess, x): guess = improve(guess, x) return guess def improve(guess, x): return average(guess, x / guess) def average(x, y): return (x + y) / 2 def good_enough(guess, x): return abs(guess**2 - x) < 1e-12

    Knowing the approximate value, this method allows you to find the best approximation (calculating the average in this case) until the desired accuracy is obtained.

    Example:

     print("%.12f" % sqrt(2)) 1.414213562373

    You can see how the Decimal.sqrt() implementation calculates the root with a given accuracy :

     >>> import decimal >>> decimal.getcontext().prec = 60 >>> decimal.Decimal(2).sqrt() Decimal('1.41421356237309504880168872420969807856967187537694807317668')

    Or here is an algorithm without multiplications / divisions from the @mathmandan answer , which finds the whole square root:

     def isqrt(n): assert n >= 0 if n == 0: return 0 i = n.bit_length() >> 1 # i = floor( (1 + floor(log_2(n))) / 2 ) m = 1 << i # m = 2^i # # Fact: (2^(i + 1))^2 > n, so m has at least as many bits # as the floor of the square root of n. # # Proof: (2^(i+1))^2 = 2^(2i + 2) >= 2^(floor(log_2(n)) + 2) # >= 2^(ceil(log_2(n) + 1) >= 2^(log_2(n) + 1) > 2^(log_2(n)) = n. QED. # while (m << i) > n: # (m<<i) = m*(2^i) = m*m m >>= 1 i -= 1 d = n - (m << i) # d = nm^2 for k in range(i - 1, -1, -1): j = 1 << k # n-(m+2^k)^2 = nm^2-2*m*2^k-2^(2k) new_diff = d - (((m << 1) | j) << k) if new_diff >= 0: d = new_diff m |= j return m

    Example:

     >>> isqrt(12345678901234567**2) 12345678901234567

      c ** (1 / b) c-number b-what root is needed (square, cubic, etc.)