Рекурсивное деление с использованием массива больших чисел базы 2 ^ 64 - PullRequest
Новая
       5

Рекурсивное деление с использованием массива больших чисел базы 2 ^ 64

1 голос
/ 14 ноября 2011

Мне нужно иметь возможность разделить два больших целых числа A и B и получить результирующее отношение Q и остаток R. Я нашел много постов о «просто делении, как в начальной школе», но не понимаю, как это относится к этому случаю, где база составляет 2 ^ 64.

Например, скажем, у меня было число A, составленное из a_2 = 120, a_1 = 2 и a_0 = 240, где a_2 соответствует 2 ^ (64 * 2), a_1 - 2 ^ (64 * 1) и т. Д. и я хочу разделить его на B, с b_1 = 1300 и b_0, равным 3.

Как бы я поступил так?

Спасибо

1 Ответ

0 голосов
/ 14 ноября 2011

В классе Java BigInteger есть метод divAndRemainder (BigInteger val), который возвращает (Q, R) в виде массива.

Пример: 

BigInteger a=new BigInteger("2").pow("128").multiply("120").add(new BigInteger("2").pow("64").multiply("2")).add(new BigInteger("240"));
BigInteger b=new BigInteger("2").pow("64").multiply("1300").add(new BigInteger("3"));
BigInteger[] qr=a.divideAndRemainder(b);

Хотя это не вполне то, что вы просите, не так ли?

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

Если я (сейчас) понимаю, о чем вы спрашиваете, у вас может быть последовательность из 4-битных чисел (шестнадцатеричный код) и 8-битный процессор, который может выполнять операции mod, div, add, multiply. Как разбить его на куски, чтобы решить деление чисел произвольной ширины?

Например, вы можете проверить, что в десятичном виде, 1441/3 = 480r1. В вашей 8-битной машине вы хотите (Q, R) для уравнения (0x05a1 / 0x3). Вы можете вычислить слева направо, взяв остаток и применив его к старшему фрагменту следующей цифры. Итак, вы вычисляете 0x5 / 0x3 = 1r2, затем 0x2a / 0x3 = er0, затем 0x01 / 0x3 = 0r1. Последовательность "1e0" из результатов соответствует ожидаемому значению (0x1e0 = 480), а последний остаток соответствует ожидаемому значению 1.

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

...