Вычисления корня из произведения

#алгоритм #c #cpp

Доброго времени суток!
Дано нескольких чисел порядка 10^12, не являющихся квадратами, произведение которых
гарантированно является квадратом некоторого числа. Проблема в том, что, произведение
это, очевидно, > 10^20 то есть значительно превышает размер unsigned long long.
Собственно, вопрос: как из этого произведения вычислить точный корень за как можно
меньшее время?
Появляется естественное желание раскладывать числа на простые множители, после чего
перемножать заново, но их брать степени в два раза меньше. Но разложение таких чисел
каждого займет много времени и памяти.
Заранее спасибо всем откликнувшимся!    

Ответы

Ответ 1

Давайте попробуем вот как:

Пусть наши числа a, b, и их разложение на простые множители выглядит так:



Можно посчитать t = НОД(a, b), не раскладывая числа на множители при помощи алгоритма
Евклида, тогда



где 



Рассмотрим числа



Эти числа обязаны являться квадратами, т. к. каждый простой показатель степени входит
либо в a₀, либо в b₀ (ясно, почему?). Из них можно извлечь корень.

Далее,



Всё.



В качестве альтернативного решения: вычислим приблизительный корень типа double из
каждого сомножителя. Точность вычисления корня (sqrt(double)) 52 значащих бита, то
есть 15 десятичных разрядов. Для чисел точностью в 12 разрядов корень будет около 6
разрядов, то есть точность корня будет 15 - 9 = 6 знаков после запятой. То же для второго
сомножителя. Перемножим полученные корни. Точность произведения будет 5 знаков после
запятой. Округлив произведение до целого, получим точный результат (для этого достаточен
был бы 1 знак после запятой, а у нас их аж 5).



PS: почему бы не включить математическую нотацию здесь, как и на маткоде?


Ответ 2

GNU MP не спасёт отца русской демократии?


Ответ 3

Алгоритм VladD можно распространить на случай нескольких чисел. Для этого надо в
цикле брать пару очередных элементов массива и вычислять их НОД и НОК. НОК помещать
в конец массива (как на рисунке), а НОД перемножать.
Если корень извлекается нацело, то через (n-1) шагов он будет равен произведению НОД.


Ответ 4

Например, вот:Алгоритмы нахождения квадратного корня.


Ответ 5

Берите любую библиотеку реализующую Big Integer/BigInt и будет вам счастье...