Бинарный поиск для квадратного корня 2

Question

У меня проблема с тем, что мой алгоритм двоичного поиска для нахождения квадратного корня из 2, кажется, находится в бесконечном цикле и работает вечно:

num = 2
low = 1
high = num
i = 0
while((i**2) != 2): #was while(low<high): but wasnt working with it either
 i = low + (high - low) / 2;

 sqrt = i * i

 if (sqrt == num):
     print(i)
 elif(sqrt < num):
     low = i
 else:
     high = i
print(sqrt)    

testRoot = 2 ** (.5)
print(testRoot)

Я не уверен, есть ли проблема с моим циклом while или нет. Я предположил, что это будет довольно прямой алгоритм двоичного поиска с небольшой модификацией для учета аспекта квадратного корня.

Когда я запускаю свой код, я не могу заставить его производить вывод вообще. Я не уверен, есть ли реальная проблема с кодом или компилятором, поскольку я думал, что следовал алгоритму довольно близко к тому, что у меня было в прошлом.

Answer 1

Как сказано в нескольких других постах, сравнение i * i == 2 не может работать.

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

Таким образом, для обеспечения полной точности двойной итерации 53 раза (больше - бесполезно). Также обратите внимание, что проверка на равенство внутри цикла является контрпродуктивной.

num= 2
low= 1
hig= 2
for i in range(53):
    mid= 0.5 * (low + hig)
    if mid * mid < num:
        low= mid
    else:
        hig= mid

print(mid)

53 итерации здесь уместны, потому что начальные оценки являются точными для первого бита (1≤√2 <2). Для менее точных начальных оценок добавьте несколько итераций. </p>

Answer 2

Часто полезно провести некоторое исследование.

$ python
Python 3.6.6 
>>> import math

>>> import numpy
>>> import scipy
>>> import numpy
>>> math.sqrt(2) ** 2
 2.0000000000000004
>>> numpy.sqrt(2) ** 2
 2.0000000000000004
>>> scipy.sqrt(2) ** 2
 2.0000000000000004
>>> (2.0**(0.5))**2
 2.0000000000000004
>>> x =  math.sqrt(2) ** 2
>>> math.sqrt(x)
 1.4142135623730951
>>> math.sqrt(2)
 1.4142135623730951
>>> x*x
 4.000000000000002
>>> x**2
 4.000000000000002
>>> 1.414213562373095**2
 1.9999999999999996
>>> 1.41421356237309505**2
 2.0000000000000004
>>> 1.41421356237309505
 1.4142135623730951
>>> 1.41421356237309504
 1.4142135623730951
>>> 1.41421356237309504**2
 2.0000000000000004
>>> 1.41421356237309503**2
 1.9999999999999996
>>> 1.41421356237309503 * 1.41421356237309504
 2.0
>>> 1.41421356237309504 - 1.41421356237309503
 2.220446049250313e-16

Немного смазки для локтя может быть полезным. (и сбивает с толку!)

давайте посмотрим на ошибки

>>> s =set()
>>> exact = 0
>>> exact_over = 0
>>> exact_under = 0

>>>for i in range(100):
...     differ = (i - (i**0.5)**2)
...     s |= {differ}
...     exact += 1 if differ == 0 else 0
...     exact_over  += 1 if differ > 0  else 0
...     exact_under += 1 if differ < 0  else 0

>>> sorted(list(s)) 
[-1.4210854715202004e-14,
 -7.105427357601002e-15,
 -3.552713678800501e-15,
 -1.7763568394002505e-15,
 -8.881784197001252e-16,
 -4.440892098500626e-16,
 0.0,
 4.440892098500626e-16,
 8.881784197001252e-16,
 1.7763568394002505e-15,
 3.552713678800501e-15,
 7.105427357601002e-15,
 1.4210854715202004e-14]

>>> exact_under, exact, exact_over
(26, 49, 25)

Answer 3

Проблема в том, что использование == для чисел с плавающей запятой почти всегда является плохой практикой, и есть v a r i o u s вопросы по этому поводу. Вам следует заменить сравнение на abs(a - b) < precision. Также читайте комментарии под этот вопрос, очень полезно.

Мой исправленный код выглядит следующим образом (Python 3), замените 1e-6 на меньшее число, если вы хотите большей точности. Но учтите, что нецелесообразно быть «слишком точным», и рекомендуется точность 1.0e-15 или выше, если вы хотите, чтобы цикл прекратился, потому что само число с плавающей запятой имеет пределы точности.

num = 2
low = 1
high = num
i = 0
while abs((i**2) - num) > 1e-6:  # Note
    i = low + (high - low) / 2
    sqrt = i * i

    if abs(sqrt - num) < 1e-6:  # Note
        print(i)
    elif(sqrt < num):
        low = i
    else:
        high = i
print(sqrt)

testRoot = 2 ** (.5)
print(testRoot)

Answer 4

Как уже упоминалось в моем исходном комментарии и во всех ответах, квадратный корень из 2 равен иррациональным . Квадратный корень каждого целого числа, которое не является идеальным квадратом, иррационально в этом отношении, поэтому 2 не является особенным в этом отношении. Важно то, что x**2 == 2 никогда не будет истинным для любых x конечной точности (поскольку конечная точность - это еще один способ сказать, что число рационально).

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

Я бы хотел предложить более естественный подход. Вы можете проверить, точно ли значение вашего центра равно одной из границ. Это будет означать, что половина вашей разницы представляет менее одной цифры точности в вашем текущем предположении. Ваша формулировка центра уже правильна: i = low + (high - low) / 2 можно сравнить с low и high, используя ==, а i = (low + high) / 2 - нет. Это связано с тем, что точность high - low больше или равна точности любой границы, тогда как low + high может потерять некоторые цифры.

Итак, вот что я бы порекомендовал:

num = 2
low = 1
high = num
guess = low + (high - low) / 2
count = 0
while guess != low and guess != high:
    sqr = guess * guess

    if sqr == num:
        break
    elif(sqr < num):
        low = guess
    else:
        high = guess

    guess = low + (high - low) / 2
    count += 1
else:
    if abs(low * low - num) < abs(high * high - num):
        guess = low
    else:
        guess = high

print(count, ':', sqr)
print(num ** (.5), '~=', guess)

Я добавил count для проверки. Результат получается за 52 итерации с точностью до 1 знака точности:

52 : 2.0000000000000004
1.4142135623730951 ~= 1.4142135623730951 

Окончательная проверка по границам (предложение else в while) гарантирует, что вы получите самый близкий результат к желаемому результату, независимо от того, какой вы нажали первым.

Сходимость нормальна: 64-битное число с плавающей точкой в ​​формате IEEE-754 имеет 53 бита в мантиссе, поэтому имеет смысл, что вам придется вдвое сократить пространство поиска ровно столько раз чтобы получить результат (первый раз за пределами цикла).

Вот фрагмент, который я использовал для тестирования: https://ideone.com/FU9r82

Answer 5

Равенство между двумя числами с плавающей запятой является очень жестким условием, поскольку квадратный корень из 2 имеет бесконечное число цифр после десятичной точки. Попробуйте это while условие:

while (abs((i ** 2) - 2) > 1e-8)