У вас есть различные варианты здесь. Вы можете работать с библиотекой с плавающей точкой произвольной точности (например, MPFR с C или C ++, или mpmath или встроенной библиотекой decimal в Python). Если вы знаете, какую ошибку гарантирует библиотека, вы можете получить правильные десятичные цифры. Например, и MPFR, и Python decimal гарантируют правильное округление здесь, но у MPFR есть недостаток (для вашего конкретного случая использования получения десятичных цифр), что он работает в двоичном формате, поэтому вам также потребуетсядля анализа ошибки, вызванной двоичным и десятичным преобразованием.
Вы также можете работать с чистыми целочисленными методами, используя целочисленную библиотеку произвольной точности (например, GMP ) или языккоторый поддерживает целые числа произвольной точности из коробки (например, Java с его классом BigInteger: последние версии Java предоставляют метод BigInteger.sqrt): масштаб 2 на 10**2n, где n - это число знаков после запятой, которое вам нужно, возьмите квадратный корень integer (т. е. целую часть точного математического квадратного корня) и затем уменьшите на 10**n. Ниже приведен сравнительно простой, но эффективный алгоритм для вычисления целочисленных квадратных корней.
Самый простой вариант из коробки, если вы хотите использовать другой язык, это использовать Python's decimalбиблиотека. Вот весь код, который вам нужен, предполагая Python 3 (а не Python 2, где это будет ужасно медленно).
>>> from decimal import Decimal, getcontext
>>> getcontext().prec = 10**6 + 1 # number of significant digits needed
>>> sqrt2_digits = str(Decimal(2).sqrt())
Операция str(Decimal(2).sqrt()) занимает на моей машине менее 10 секунд. Давайте проверим длину и первую и последнюю сотню цифр (мы, очевидно, не можем воспроизвести весь вывод здесь):
>>> len(sqrt2_digits)
1000002
>>> sqrt2_digits[:100]
'1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157'
>>> sqrt2_digits[-100:]
'2637136344700072631923515210207475200984587509349804012374947972946621229489938420441930169048412044'
Есть небольшая проблема с этим: результат равен гарантированно будет правильно округлено, но это округлено , а не усечено . Таким образом, это означает, что эта последняя цифра «4» может быть результатом последнего раунда up , то есть фактическая цифра в этой позиции может быть «3», с «8» или «9». "(например) после него.
Мы можем обойти это, вычислив пару дополнительных цифр, а затем обрезав их (после двойной проверки, что округление этих дополнительных цифр невлияет на усечение).
>>> getcontext().prec = 10**6 + 3
>>> sqrt2_digits = str(Decimal(2).sqrt())
>>> sqrt2_digits[-102:]
'263713634470007263192351521020747520098458750934980401237494797294662122948993842044193016904841204391'
Таким образом, действительно, миллионная цифра после десятичной точки равна 3, а не 4. Обратите внимание, что если последние 3 цифры, вычисленные выше, были "400", мы все равно неЯ не знал, была ли миллионная цифра цифрой «3» или «4», поскольку эта цифра «400» снова может быть результатом округления. В этом случае вы можете вычислить еще одну две цифры и повторить попытку и т. Д., Остановившись, если у вас есть однозначный вывод. (Для дальнейшего чтения найдите «Дилемма производителя таблиц».)
(Обратите внимание, что установка режима округления модуля decimal на ROUND_DOWN не работает , так как *Метод 1056 * игнорирует режим округления.)
Если вы хотите сделать это, используя чисто целочисленную арифметику, Python 3.8 предлагает функцию math.isqrt для вычисления точных целочисленных квадратных корней. В этом случае мы будем использовать его следующим образом:
>>> from math import isqrt
>>> sqrt2_digits = str(isqrt(2*10**(2*10**6)))
Это займет немного больше времени: около 20 секунд на моем ноутбуке. Половина этого времени относится к двоично-десятичному преобразованию, неявному в вызове str. Но на этот раз мы получили усеченный результат напрямую, и нам не пришлось беспокоиться о возможности округления, дающего нам неправильные последние цифры.
Еще раз проверяя результаты:
>>> len(sqrt2_digits)
1000001
>>> sqrt2_digits[:100]
'1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572'
>>> sqrt2_digits[-100:]
'2637136344700072631923515210207475200984587509349804012374947972946621229489938420441930169048412043'
Это немного обманывает, потому что (на момент написания) Python 3.8 еще не был выпущен, хотя доступны бета-версии . Но в исходном коде CPython есть чистая версия алгоритма isqrt, написанная на Python, которую вы можете копировать, вставлять и использовать напрямую. Вот полностью:
import operator
def isqrt(n):
"""
Return the integer part of the square root of the input.
"""
n = operator.index(n)
if n < 0:
raise ValueError("isqrt() argument must be nonnegative")
if n == 0:
return 0
c = (n.bit_length() - 1) // 2
a = 1
d = 0
for s in reversed(range(c.bit_length())):
# Loop invariant: (a-1)**2 < (n >> 2*(c - d)) < (a+1)**2
e = d
d = c >> s
a = (a << d - e - 1) + (n >> 2*c - e - d + 1) // a
return a - (a*a > n)
Источник также содержит объяснение приведенного выше алгоритма и неофициальное доказательство его правильности.
Вы можете проверить, что результаты двумя вышеупомянутыми методами совпадают (по модулю дополнительной десятичной точки в первом результате). Они вычисляются совершенно разными методами, так что они служат проверкой работоспособности обоих методов.