Как максимально ускорить процесс извлечения корня в Python3?

Question

[Alex Setup]

Используя sqrt из стандартной библиотеки math, при извлечении корня из огромного (10**100) числа теряется точность. Тогда я начал использовать decimal для увеличения точности вычислений:
decimal.getcontext().prec = 1500
Но при использовании decimal скорость выполнения скрипта значительно уменьшается. Как можно это исправить?
Мне необходимо огромное количество цифр после запятой (600000 к примеру).
Есть ли альтернатива decimal?
P.S. :Желательно используя стандартные библиотеки

Comments

[Andy_U]

Не соблаговолит ли уважаемый сэр объяснить, что это:

Используя sqrt из стандартной библиотеки math, при извлечении корня из огромного (10**100) числа теряется точность.

означает? Лучше примером кода.

[Alex Setup]

Andy_U, Ну допустим вы извлекаете корень из
x=1000000000000000000000000000000000000000000000000000000000000000000000

from math import sqrt
sqrt(x)

программа выдаст неточный результат

[Andy_U]

1) Корень из 10^69 - это действительное число, которое неизбежно представляется в компьютере лишь приближенно.

2) При вызове sqrt int приводится к типу float. Только вот у вас x изначально занимает 56 байт, а после преобразования к float всего 24 (см. код ниже), что дополнительно приводит к потере "точности" в математическом смысле. Так что math.sqrt совсем не виноват.

# -*- coding: utf-8 -*-

import math
import sys

if __name__ == '__main__':
    x1 = 1000000000000000000000000000000000000000000000000000000000000000000000
    x2 = float(x1)

    print(sys.getsizeof(x1))
    print(sys.getsizeof(x2))

    y1 = math.sqrt(x1)
    y2 = math.sqrt(x2)
    print(y1-y2)

[Alex Setup]

Andy_U, Ваш ответ абсолютно понятен мне. Я и до Вашего ответа это знал, но суть вопроса в другом. Вы не туда капаете. Нужен эффективный способ повышения точности.

[Andy_U]

Alex Setup, Если мой ответ Вам понятен, почему Вы так неточно сформулировали вопрос, упирая на величину числа, как источник ошибок? Нет, чтобы спросить по арифметику с плавающей точкой произвольной разрядности (arbitrary precision arithmetic)? Тогда ответ такой - в стандартной библиотеке, кроме decimal, ничего больше нет. А в "природе" несколько пакетов иммется, типа bigfloat или mpmath. Кто быстрее - сами проверяйте.

[Andrey Dugin]

Это в какой области такая точность применяется - 600 тысяч знаков после запятой?

[Andrey Dugin]

Andy_U, альтернатива - при вызове numpy.sqrt число к float не приводится. Но работает раз в 5 медленнее.

[Alex Setup]

Andrey Dugin, Математический проект

[Andy_U]

Andrey Dugin, у меня numpy падает с ошибкой:

Traceback (most recent call last):
  File "H:/My Documents/PyCharm/tst/tst38.py", line 14, in <module>
    y1 = numpy.sqrt(x1)
AttributeError: 'int' object has no attribute 'sqrt'

[Andrey Dugin]

Andy_U, весь код покажите. Почему у Вас модуль numpy стал вдруг int?

[Andy_U]

Andrey Dugin, В коде выше поменяйте math на numpy.

[Andrey Dugin]

Andy_U, вот тут объяснено: Numpy log10 function: AttributeError: 'float' obje...

[Andy_U]

Andrey Dugin, Ну, вот Вы сами и объяснили, почему предложенный Вами автору вопроса вариант использовать numpy.sqrt для больших int не работает. Ну, как бы понятно, что numpy для таких фокусов не предназначен, поэтому я и разбираться не стал. Упало и упало.

P.S. Еще раз говорю, на слуху два варианта: bigfloat и mpmath (который, кстати, используется в sympy - ну, наверное, авторы его не зря выбрали?).

[Andrey Dugin]

Andy_U, я нигде не предлагал использовать numpy.sqrt для больших int. С Decimal работает корректно.

Answer 1

[Александр Варакосов]

Если бы операции с числами с повышенной точностью можно было производить "в лоб", то математический софт никогда не стал так раздут и жаден до ресурсов.
Подход здесь всегда одинаков, проблемная операция преобразуется в выражение которое может быть вычислено с приемлемой потерей точности. Например: выделяют порядок и операции производят только над мантиссой; разбивают операцию на несколько этапов, для корня можно представить значение в виде произведения и считать корни для множителей, и т.д. В первом приближении, берёте учебник линейки или анализа и вперёд.

Answer 2

[vreitech]

искать иные реализации извлечения корня для python3, проводить сравнительное тестирование.
наращивать вычислительную мощность железа, на котором ищутся корни.

Comments

[Alex Setup]

Ваш ответ очевиден. Но мне нужен метод решения задачи. В интернете мало что можно найти по данной теме!

[Alex Setup]

Плюс на многих реализациях также придется использовать повышение точности с помощью decimal

[vreitech]

а ещё есть scipy, numpy и theano.

[Alex Setup]

Филипп, Ну хотелось бы использовать только стандартные библиотеки

[Andrey Dugin]

Alex Setup, в мире научных вычислений это стандартные библиотеки.