Как реализовать деление в столбик для огромного количества (сверхбольшие числа)

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

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

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

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

править: Этот алгоритм будет работать с основой 256? http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

править: Действительно ли это - алгоритм (подразделение ньютона), я должен действительно использовать? http://en.wikipedia.org/wiki/Division_ (цифровой) #Newton. E2.80.93Raphson_division

7
задан Chris 8 July 2010 в 01:13
поделиться

1 ответ

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

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

5
ответ дан 7 December 2019 в 09:56
поделиться
Другие вопросы по тегам:

Похожие вопросы: