Как разделить большие числа?

Question

У меня есть большое число (целое, без знака), хранящееся в 2 переменных (как вы можете видеть, старшая и младшая части числа):

unsigned long long int high;
unsigned long long int low;

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

Но мне нужно разделить такие цифры. Как это сделать? Я знаю, я могу вычесть N раз, но, может быть, есть более лучшие решения. ; -)

Язык: C

Answer 1

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

Я не претендую на полную корректность, но следующее должно помочь вам:

(1) Инициализировать результат в ноль.

(2) Сдвиньте делитель на максимально возможное число битов влево, не позволяя ему стать больше делимого.

(3) Вычтите сдвинутый делитель из дивиденда и прибавьте один к результату.

(4) Теперь сдвигайте делитель вправо до тех пор, пока он снова не станет меньше, чем оставшийся дивиденд, и для каждого результата сдвига вправо, сдвига влево на один бит. Вернитесь к (3), если условие остановки не выполнено. (Условие остановки должно быть чем-то вроде «делитель стал равным нулю», но я не уверен в этом.)

Действительно приятно вернуться к некоторым РЕАЛЬНЫМ проблемам программирования: -)

Answer 2

Я знаю, я могу вычесть N раз, но, может быть, есть и более лучшие решения.

Вычитание N раз может быть медленным, если N большое.

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

[Для таких номеров также может быть поддержка сторонних библиотек и / или компиляторов.]

Answer 3

Рассматривали ли вы какие-либо библиотеки с большим числом, например GNU MP BigNum ?

Answer 4

Если ваш процессор (или ваша библиотека C) имеет быстрое 64-битное деление, вы можете разбить 128-битное деление на части (так же, как вы делали бы 32-битное деление на процессорах с 16-битным подразделения).

Кстати, вы можете использовать всевозможные приемы, если знаете, какие типичные значения будут для дивиденда и делителя. Каков источник этих чисел? Если многие ваши дела могут быть решены быстро, это может быть нормально, случайный случай занимает много времени.

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

Answer 5

Вы можете делать сложение и вычитание произвольно больших двоичных объектов, используя цикл ассемблера и инструкции «сложение / вычитание с переносом (adc / sbb)». Вы можете реализовать другие операции, используя их. Я никогда не занимался расследованием дел, кроме этих двух лично.

Answer 6

Вы могли бы реализовать алгоритм типа "BigInt", который делит на строковые массивы. Создайте массив из 1 строки для каждой пары high и low и выполните деление. Сохраните результат в другом строковом массиве, а затем преобразуйте обратно в пару высоких и низких целых чисел.

Поскольку язык C, массив, вероятно, будет символьным массивом. Считайте это аналогом "массива строк", о котором я упоминал выше.

Answer 7

Вот еще одна библиотека, выполняющая 128-битную арифметику. GnuCash: Math128 .

Answer 8

Согласно моим комментариям ниже, мой предыдущий ответ был глупым.

Быстро, мой новый ответ будет таким: когда я пытался сделать это в прошлом, это почти всегда включало смещение, потому что это единственная операция, которая может быть применена к нескольким «словам», если хотите, это выглядит так же, как если бы это было одно большое слово (за исключением необходимости отслеживать биты переноса).

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

Answer 9

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