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

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

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

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

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

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

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

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

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


java biginteger sqrt
person Bill K    schedule 21.06.2011    source источник
comment
Я надеюсь, что вы имели в виду 2*sqrt(3) для квадратного корня из 12.   -  person Ted Hopp    schedule 22.06.2011
comment
Поскольку для подавляющего большинства чисел этот результат может быть не уникальным (или это так, и я упускаю здесь какую-то очевидную математическую теорему? Здесь немного поздно ;) ), вам нужно указать свои требования немного более четко. Очевидно, вы могли бы использовать множители числа, но тогда это проблема факторизации, и мы все знаем, как это получается для больших чисел.   -  person Voo    schedule 22.06.2011
comment
Спасибо @ted, я знал, что сделаю это где-нибудь!   -  person Bill K    schedule 22.06.2011
comment
@voo, использующий методы gcd() и isPrime() BigInteger, удивительно быстр даже для довольно больших чисел. В настоящее время я использую их для уменьшения дробей (в настоящее время я возвращаю результаты, такие как 3 1/2 для 7/2, что требует небольшого факторинга)   -  person Bill K    schedule 22.06.2011
comment
Между прочим, изначально я собирался хранить свой Rational как набор простых чисел, каждое из которых либо выше, либо ниже дроби. Это сделало бы эту проблему тривиальной, а также сделало бы все дроби самосокращающимися, но gcd() оказался настолько быстрым, что мое решение разложить его на множители и сохранить с факторингом казалось преждевременной оптимизацией.   -  person Bill K    schedule 22.06.2011
comment
@Bill - я считаю, что метод проверки простоты BigInteger называется isProbablyPrime, что дает вам представление о том, что вы получаете, когда используете его. Это статистический тест, и он не дает однозначного ответа. Возможно, априорное представление простого фактора не было преждевременной оптимизацией. :)   -  person Ted Hopp    schedule 22.06.2011

Ответы (2)


arrow_upward
4
arrow_downward

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

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

person Ted Hopp    schedule 21.06.2011
comment
Все методы вычисления квадратного корня, казалось, основаны на возвращении числа, очень близкого к квадратному корню. Например, 578 должно возвращать 2*sqr(17), а не число около 24. - person Bill K; 22.06.2011
comment
Вот почему вам нужна уникальная простая факторизация числа. - person YXD; 22.06.2011
comment
Да, думаю, простого решения нет. Я подожду еще немного, но вы, вероятно, правы, мне просто придется заняться факторингом и поиском пар. Хорошей новостью является то, что этот же метод решит кубические корни :) - person Bill K; 22.06.2011

arrow_upward
0
arrow_downward

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

person Brad Gardner    schedule 21.06.2011
comment
Хм, интуитивно я не думаю, что это сработает. Самый высокий совершенный квадрат, меньший моего числа, может не быть фактором моего числа, что означало бы, что его нельзя использовать, и мне пришлось бы перейти к следующему наивысшему квадрату (итеративное решение, которого я пытался избежать) - person Bill K; 22.06.2011
comment
Хороший момент, полностью разнесенный по фактору. Вы должны были бы включить то, что не дает вам многого. Кроме некоторых основных оптимизаций, я не уверен, что вы можете многое сделать. - person Brad Gardner; 22.06.2011