Как реализовать длинное деление на огромные числа (bignums)

Question

Я пытаюсь реализовать длинное деление для бигнумов. К сожалению, я не могу использовать такую ​​библиотеку, как GMP, из-за ограничений встроенного программирования. Кроме того, я хочу научиться выполнять интеллектуальные упражнения. До сих пор у меня сложение и умножение выполнялись с использованием массивов байтов любой длины (поэтому каждый байт подобен цифре с основанием 256).

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

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

-edit: мне нужны алгоритмы, которые работают, когда дивиденд составляет ~ 4000 бит, а делитель ~ 2000 бит

-edit: будет ли этот алгоритм работать с base-256? http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-edit: Это алгоритм (деление Ньютона), который я действительно должен использовать? http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

Answer 1

Если вы хотите учиться, начните с карандашного и бумажного метода, который вы использовали в начальной школе.Верьте или нет, это по сути тот же алгоритм O (n ^ 2), который используется в большинстве библиотек bignum для чисел, которые находятся в диапазоне, который вы ищете.Сложный первый шаг называется «частной оценкой», и это, вероятно, будет самым трудным для понимания.Как только вы поймете это, все остальное придет легко.

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

Answer 2

Используете ли вы void Four1 (long double [], int, int) в своем коде, а затем сворачиваете, а затем хорошо выполняете обратное преобразование, я получил умножение на работу, но когда я попытался выполнить деление таким же образом, оно выпало один результат, затем выход, так что я не могу помочь, но если у вас есть том под названием «Числовые рецепты в C ++», перейдите к концу, и вы найдете то, что вы ищете на самом деле, он начинается на страницах с 916 по 926.

Answer 3

Этому вопросу более 2 лет, но для чисел этого размера вы можете посмотреть исходный код OpenSSL.Он выполняет RSA с числами этого размера, поэтому имеет множество математических процедур, оптимизированных для чисел от 1000 до 4000 бит.