Целочисленное деление произвольной точности, как обращаться с 32-битными остатками? - PullRequest
Новая
       36

Целочисленное деление произвольной точности, как обращаться с 32-битными остатками?

0 голосов
/ 19 мая 2019

Мне нужно разделить число N на другое число D, которое больше, чем длина моего слова, которая составляет 32 бита

В настоящее время я использую алгоритм, найденный здесь: http://justinparrtech.com/JustinParr-Tech/an-algorithm-for-arbitrary-precision-integer-division/

Я реализую свое решение для RISC-V ISA

Но на третьем этапе, когда Q = N / A, я не знаю, что делать в случае, если остаток также является 32-битным числом,потому что обычно я использовал бы этот остаток для деления следующего слова, но если это размер регистра, его невозможно принять во внимание.

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

1 Ответ

4 голосов
/ 20 мая 2019

Этот алгоритм ужасен.

Первым шагом должно быть определение знака результата (по знаку числителя и делителя);затем найдите величину числителя и делителя (и используйте ярлыки для «числитель равен 0» и «abs (делитель) равен 0 или 1» в случаях, когда фактическое деление можно избежать или невозможно), чтобы код, который делаетфактическое деление имеет дело только с положительными числами.

Второй шаг должен состоять в том, чтобы определить, является ли делитель достаточно маленьким, чтобы поместиться в одну цифру (с цифрами, которые находятся в любой базовой позиции, которая является самой большой, что ваш язык /поддерживает среду - например, для C с 32-разрядными целыми числами это может быть «base 65536», а для 64-разрядного языка ассемблера 80x86 (где вы можете использовать 128-разрядные числители) это может быть «base 18446744073709551616»).На этом этапе вы переходите к одному из 2 совершенно разных алгоритмов.

Маленький делитель

Это относительно тривиально "для каждой цифры в числителе {разделите цифру на делитель нанайти цифру в цикле результата} "(с последующим исправлением знака результата, определенного вами в начале).

Большой делитель

Для этого Iиспользовал бинарное деление.Идея состоит в том, чтобы сместить числитель и делитель влево / вправо, чтобы делитель стал максимально большим, не будучи больше числителя.Затем вы вычитаете делитель из числителя и устанавливаете бит в результате, который соответствует тому, насколько вы сместились влево / вправо;и повторите это так, чтобы (после начального смещения) это заканчивалось тем, что «сдвиньте все, что осталось от числителя влево; затем сравните с делителем, и если числитель больше делителя, вычтите делитель из числителя и установите бит в результате» в циклеэто завершается, когда от числителя ничего не осталось).

Не по теме Альтернатива

Для большинства случаев, когда вам нужно деление произвольной точности;Лучше использовать рациональные числа, где каждое число хранится в виде трех (произвольного размера) целых чисел - числителя, делителя и экспоненты (например, number = numerator/divisor * (1 << exponent)).В этом случае вам никогда не нужно делить - вы умножаете только на обратную.Это улучшает производительность, но также значительно повышает точность (например, вы можете рассчитать (1/3) * 6 и гарантировать отсутствие потери точности).

...