Бесконечный цикл при попытке найти корень куба неидеального куба с помощью поиска пополам - PullRequest
Новая
       15

Бесконечный цикл при попытке найти корень куба неидеального куба с помощью поиска пополам

2 голосов
/ 23 марта 2019

Этот код дает довольно точный результат, когда deltanum = 0.0000000000001, но попадает в бесконечный цикл, когда deltanum = 0.00000000000001 (добавляя еще один ноль в deltanum).

Это происходит только для неидеальных кубов, отлично работает для идеальных кубов, таких как 1000. Почему?

Я новичок в программировании, после ОССУ. 

num = 100
high = num
low = 0
icount = 0
cuberoot = (high + low)/2      #cuberoot of num
deltanum = 0.00000000000001
while abs(cuberoot**3 - num)>=deltanum:
    icount+=1
    print(icount)
    if cuberoot**3 > num:
        high = cuberoot
    elif cuberoot**3 < num:
        low = cuberoot
    else:
        break
    cuberoot = (high + low)/2
print("Cube root: " + str(cuberoot))
print("Number of iterations: " + str(icount))

Ответы [ 2 ]

2 голосов
/ 23 марта 2019

Вы используете float с.float математика имеет недостатки с точки зрения точности - ваша дельта может быть слишком маленькой, чтобы работать правильно, и ваше решение переключается между значениями, даже не достигая предела условий while.См. Не работает ли математика с плавающей запятой? , чтобы больше рассуждать о том, почему иногда с плавающей запятой "разбивается".

Вы также можете ограничить его определенным количеством повторений: 

num = 100
high = num
low = 0
icount = 0
maxcount = 100000
cuberoot = (high + low)/2      #cuberoot of num
deltanum = 0.00000000000001
while abs(cuberoot**3 - num)>=deltanum:
    icount+=1
    print(icount)
    if cuberoot**3 > num:
        high = cuberoot
    elif cuberoot**3 < num:
        low = cuberoot
    else:
        break
    cuberoot = (high + low)/2

    if icount > maxcount:
        print("Unstable solution reached after ",maxcount, "tries")
        break
print("Cube root: " + str(cuberoot) + " yields " + str(cuberoot**3))
print("Number of iterations: " + str(icount))

Вывод: 

Unstable solution reached after  100000 tries
Cube root: 4.641588833612779 yields 100.00000000000003
Number of iterations: 100001
0 голосов
/ 23 марта 2019

Большинство людей назвали бы это epsilon и использовали бы delta для cuberoot**3 - num.

К концу вы надеетесь, что это выражение, 

    cuberoot = (high + low)/2

купит вам примерно еще один бит точности в вашем ответе на каждую итерацию. (Рядом с началом каждый раз приблизительно сокращается количество битов ошибок пополам.)

Вы жалуетесь, что IEEE-754 double имеет ограниченную точность при вычислении кубов, а также различия. Пятьдесят три бита дают вам почти шестнадцать десятичных цифр, и ваш эпсилон равен 1e-14. Но, как вы обнаружили, ввод num длиной в несколько цифр сожрет у вас на полях.

Для более точных вычислений вы можете использовать Десятичное число . Или загляните в библиотеку gmp .

Вы верите, что выполняется некоторый инвариант цикла, что величины cuberoot и cuberoot ** 3 будут меняться на каждой итерации. Это просто проверить. Просто назначьте их временным переменным и убедитесь, что они меняются. Завершите цикл раньше, если они этого не сделают. В более общем смысле, чтобы обнаружить колебания между несколькими ограничивающими значениями, поместите предыдущие значения в set и завершите работу рано, увидев повторяющееся значение.

...