Python. Calculating the square root of a number with dimension 10^300?
Good afternoon!
Please tell me how to calculate the square root of a number with dimension 10^300?
Module function math
int(m.sqrt(N))
Works correctly, but not for large values.
2 answers
The presented algorithm works only for integers. The module math cannot be used in this case due to rounding errors. You can also look for alternative solutions, extended comments or optimization using the search query Integer square root or isqrt. I took the implementation example from of this question. There are also orders of magnitude faster implementations using third-party mathematical modules.
def isqrt(x):
"""
Вычисляет квадратный корень любого сколь угожно большего целого числа
Функция возвращает кортеж (a, r), где a ** 2 + r = x
a - наибольшее целое такое, что a**2 <= x, а r - это остаток
Если x - идельный квадрат, то остаток равен нулю
Алгоритм использовался в алгоритме "длиннорукий квадратный корень", описанный по адресу
http://mathforum.org/library/drmath/view/52656.html
Tobin Fricke 2014-04-23
Max Planck Institute for Gravitational Physics
Hannover, Germany
"""
N = 0 # Исходные данные на текущей итерации
a = 0 # Решение на текущей итерации
# Число будет обработано начиная с MSB, 2 бита за раз
# MSB - Most significant bit, старший бит, наиболее значимый бит
L = x.bit_length()
L += (L % 2) # Округление до следующего четного
for i in range(L, -1, -1):
# Следующие два бита
n = (x >> (2*i)) & 0b11
# Проверка на то, можем ли мы уменьшить остаток
if ((N - a*a) << 2) + n >= (a << 2) + 1:
b = 1
else:
b = 0
a = (a << 1) | b # Добавляем следующий бит решения
N = (N << 2) | n # Добавляем следующий бит исходных данных
return a, N-a*a
assert(isqrt(287588743834685763847583454323427 ** 2)[0] == 287588743834685763847583454323427)
#
assert(isqrt(10 ** 300)[0] == 10 ** 150)
#
assert(isqrt(2 ** 1578)[0] == 2 ** 789)
assert(isqrt(2 ** 83470)[0] == 2 ** (83470 // 2))
assert(all(isqrt(i ** 2)[0] == i for i in range(10**5)) is True)
Even without the module math python returns values correctly:
print(math.sqrt(10 ** 300)) # 1e+150
print((10 ** 300) ** 0.5) # 1e+150
1e+150 this means that the result of the calculations is 10 to the power of 150, and this is the correct result for the square root of 10^300.
3.2e-87 - "3.2 * 10^-87"
0.01e+62 - "0.01 * 10^62"
Etc.
You just need to learn how to read such numbers and that's it