Нужен алгоритм для квадратного корня, который обеспечивает "остаток"

Question

Я пишу калькулятор без десятичных чисел (поддерживает только числа Rational), но я бы хотел иметь возможность использовать квадратный корень.

Когда функция квадратного корня нажимается для (скажем) числа 12, я хотел бы просто упростить / «уменьшить» квадратный корень и вернуть 2 * sqrt (3) - в (2 * 2) * 3 и извлечение sqrt (2 * 2) как 2.

Я использую biginteger, который имеет очень хороший метод gcd () и метод pow (), который ограничен положительными параметрами (что имеет смысл, если вы не пытаетесь делать именно то, что я пытаюсь сделать.

Я мог бы предложить несколько итерационных способов сделать это, но они могут занять некоторое время с числами в диапазоне сотен цифр.

Я надеюсь, что есть какой-то милый, простой, не повторяющийся трюк, с которым я не сталкивался.

Просто чтобы уточнить: у меня есть намерение добавить мнимые числа, поэтому я планирую такие результаты:

17 + 4i √3  
-----------  
     9

Без длинных потоков десятичных дробей.

Answer 1

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

Существует целый ряд методов вычисления квадратного корня .С их помощью вы можете выразить результат как целое число плюс остаток меньше 1.

Answer 2

Может быть, попробуйте найти самый совершенный квадрат, который меньше вашего числа.Это даст вам часть уравнения, тогда вам нужно будет обработать только оставшуюся часть, которая является разницей между вашим числом и найденным вами идеальным квадратом.Это также ухудшается по мере увеличения числа, но, возможно, не так быстро.