формула вычисления корня из числа

#python #алгоритм

Как устроен модуль math, т.е. в том модуле прописана формула, функция. Мне надо написать
в своей программе функция вычисления корня из числа, не используя "import math", но
нигде не могу найти устройство модуля (что бы взять его за основу).
P.S. помогите с кодом
    

Ответы

Ответ 1

Для начала вычисляете две крайние точки - единица и само исходное число.
Потом берёте первую пробу из промежутка между этими крайними точками. Например, можно
брать их среднее арифметическое.

Возводите пробу в квадрат и сравниваете с исходным числом.
Если больше - то следующую пробу выбираете как половину промежутка между старой пробой
и меньшим крайним числом. А новым большим крайним числом становится старая проба.
Если меньше - то, соответственно новую пробу берёте как половину между старой пробой
и большим крайним числом. А новым меньшим крайним числом становится старая проба.

И таким образом каждый раз уточняя значения пробы и крайних чисел повторяете до тех
пор, пока разница между исходным числом и квадратом пробы не станет меньше какой-то
заранее выбранной допустимой погрешности.

UPD: Если вам удобнее видеть перед глазами формулы, чем текстовое описание, то можно
погуглить по запросу "численные методы квадратный корень".
Например. вот первая же ссылка на хорошую статью в Википедии. Там алгоритм немножко
другой, чем тот, что я привёл, но опирается на тот же принцип последовательных приближений.
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


Ответ 2

Существует множество алгоритмов по вычислению корня из числа, например, книга Структура
и интерпретация компьютерных программ показывает простое решение, использующее метод
Ньютона:

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


Зная примерное значение, этот метод позволяет найти лучшее приближение (вычисляя
среднее в данном случае) до тех пор пока желаемая точность не получена.

Пример:

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


Можно посмотреть как реализация Decimal.sqrt() вычисляет корень с заданной точностью:

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


Или вот алгоритм без умножений/делений из ответа @mathmandan, который находит целый
квадратный корень:

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<>= 1
        i -= 1
    d = n - (m << i)  # d = n-m^2
    for k in range(i - 1, -1, -1):
        j = 1 << k
        # n-(m+2^k)^2 = n-m^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


Пример:

>>> isqrt(12345678901234567**2)
12345678901234567


Ответ 3

c**(1/b)
с-число
b-какой нужен корень(квадратный,кубический и.т.д.)