Вопрос:

Как эффективно рассчитать корни куба, используя десятичные в Python

python arbitrary-precision

421 просмотра

1 ответ

414 Репутация автора

Я новичок в использовании десятичного модуля в Python, и мне было интересно, какой самый эффективный метод для вычисления корней куба (или любого корня на самом деле). Я пытался, num ** (Decimal(1)/Decimal(3)но это заняло довольно много времени. Например, приведенный ниже код занимает около 20 секунд на процессоре Intel i5 под управлением Python 3:

from decimal import *

getcontext().prec = 10000
a0 = Decimal(3.0)

import time
beg = time.time()
cuber = a0**(Decimal(1)/Decimal(3))
end = time.time()
print(end-beg)

Я знаю, что можно сделать что-то лучше, потому что написание простого алгоритма Ньютона значительно сокращает время выполнения (см. Код ниже). Итак, мой вопрос в том, что является хорошим методом (желательно встроенным) для получения целочисленных корней десятичных дробей?

Быстрый метод Ньютона, который намного быстрее (~ 0,2 секунды) ниже:

def cube_root( A):
    guess = (A-Decimal(1))/Decimal(3)
    x0 = (Decimal(2) * guess + A / Decimal(guess*guess) )/Decimal(3.0)
    while 1:
        xn =(Decimal(2) * x0 + A / Decimal(x0*x0) )/Decimal(3.0)
        if xn == x0:
            break
        x0 = xn
    return xn

beg = time.time()
print(cuber - cube_root(a0))
end = time.time()
print(end-beg)

Пример вывода всего приведенного выше кода в моей системе:

23.898984670639038
0E-9999
0.10790443420410156
Автор: jman Источник Размещён: 08.11.2017 11:33

Ответы (1)


2 плюса

52932 Репутация автора

Решение

Для такого кубического корня низкого порядка, Ньютон будет вашим лучшим выбором. Я сделал цикл более эффективным, удалив внутренний тест, и получил улучшение скорости примерно на 5%. Снятие лишних Decimalконверсий получилось еще на 2-3%.

def cube_root( A): 
    d1 = Decimal(1)
    d2 = Decimal(2)
    d3 = Decimal(3)

    x0 = (A-d1)/d3
    xn = (d2 * x0 + A / Decimal(x0*x0) ) / d3

    while xn != x0:
        x0 = xn
        xn = (d2 * x0 + A / Decimal(x0*x0) ) / d3

    return xn
Автор: Prune Размещён: 09.11.2017 12:42
Вопросы из категории :
32x32