Я чувствую необходимость добавить это на основе моего комментария. Это не ответ, а объяснение фона.
Библиотека bignum использует так называемые конечности - ищите mp_limb_t в источнике gmp, которые обычно являются целочисленным полем фиксированного размера.
Когда вы делаете что-то вроде сложения, один из способов (хотя и неэффективный) подойти к этому - сделать это:
doublelimb r = limb_a + limb_b + carryfrompreviousiteration
Этот конечный элемент двойного размера ловит переполнение limb_a + limb_b в случае, если сумма больше, чем размер конечности. Так что, если сумма больше, чем 2 ^ 32, если мы используем uint32_t в качестве размера конечности, переполнение может быть обнаружено.
Зачем нам это нужно? Ну, что вы обычно делаете, это перебираете все конечности - вы делали это сами, деля свое целое число на части и проходя каждую из них - но мы делаем это сначала LSL (поэтому сначала наименьшая конечность), как вы делали арифметику от руки.
Это может показаться неэффективным, но это всего лишь способ C делать вещи. Чтобы действительно разбить большие пушки, x86 имеет adc в качестве инструкции - добавьте с переносом. Это делает арифметику и для ваших полей и устанавливает бит переноса, если арифметика превышает размер регистра. В следующий раз, когда вы сделаете add или adc, процессор также учитывает бит переноса. В вычитании это называется флагом заимствования.
Это также относится к операциям смены. Таким образом, эта особенность процессора имеет решающее значение для быстрой работы Bignums. Итак, дело в том, что в микросхеме для этого есть электронная схема - выполнение в программном обеспечении всегда будет медленнее.
Не вдаваясь в подробности, операции строятся из этой способности складывать, сдвигать, вычитать и т. Д. Они имеют решающее значение. Да, и вы используете полную ширину регистра вашего процессора на каждую ветвь, если вы все делаете правильно.
Второй пункт - конверсия между базами. Вы не можете взять значение в середине числа и изменить его основание, потому что вы не можете объяснить переполнение от цифры под ним в исходной базе, и это число не может объяснить переполнение от цифры внизу ... и так далее. Короче говоря, каждый раз, когда вы хотите сменить базу, вам нужно снова конвертировать весь bignum из исходной базы в новую. Таким образом, вы должны пройти bignum (все конечности) по крайней мере три раза. Или, в качестве альтернативы, дорого выявлять переполнения во всех других операциях ... помните, теперь вам нужно выполнять операции по модулю, чтобы работать, если вы переполнены, тогда как до того, как процессор делал это для нас.
Я также хотел бы добавить, что, хотя то, что у вас есть, вероятно, быстро для этого случая, имейте в виду, что, как библиотека bignum, gmp выполняет для вас немало работы, например, управление памятью. Если вы используете mpz_, то для начала вы используете абстракцию выше того, что я описал здесь. Наконец, gmp использует сборку, оптимизированную вручную, с развернутыми циклами практически для каждой платформы, о которой вы когда-либо слышали, и даже больше. Есть очень веская причина, по которой он поставляется с Mathematica, Maple et al.
Теперь, просто для справки, некоторые материалы для чтения.
- Современная компьютерная арифметика - это кнутовидная работа для библиотек произвольной точности.
- Дональд Кнут, Полу-численные алгоритмы (Искусство компьютерного программирования, том II).
- Блог Уильяма Харта о реализации алгоритмов для bsdnt , в котором он обсуждает различные алгоритмы деления. Если вы заинтересованы в библиотеках bignum, это отличный ресурс. Я считал себя хорошим программистом до тех пор, пока не начал следить за этим ...
Подводя итог: инструкции по сборке с разделением - это отстой, поэтому люди обычно вычисляют инверсии и вместо этого умножают, как вы делаете при определении деления в модульной арифметике. Существуют различные методы (см. MCA), в основном O (n).
Редактировать: Хорошо, не все методы O (n).Большинство методов, называемых div1 (деление на что-то, не превышающее конечности, это O (n). Когда вы становитесь больше, вы сталкиваетесь со сложностью O (n ^ 2); этого трудно избежать.
ТеперьМогли бы вы реализовать bigints как массив цифр? Ну да, конечно, вы могли бы. Однако рассмотрим идею только при добавлении
/* you wouldn't do this just before add, it's just to
show you the declaration.
*/
uint32_t* x = malloc(num_limbs*sizeof(uint32_t));
uint32_t* y = malloc(num_limbs*sizeof(uint32_t));
uint32_t* a = malloc(num_limbs*sizeof(uint32_t));
uint32_t m;
for ( i = 0; i < num_limbs; i++ )
{
m = 0;
uint64_t t = x[i] + y[i] + m;
/* now we need to work out if that overflowed at all */
if ( (t/somebase) >= 1 ) /* expensive division */
{
m = t % somebase; /* get the overflow */
}
}
/* frees somewhere */
Это грубый набросок того, что вы ищете для добавления черезваша схема. Таким образом, у вас есть для запуска преобразования между базами. Поэтому вам понадобится преобразование в ваше представление для базы, а затем обратно, когда вы закончите, потому чтоэта форма просто очень медленная везде . Мы не говорим здесь о разнице между O (n) и O (n ^ 2), но мы говорим о дорогостоящей инструкции деления законечность или дорогостоящее преобразование каждый раз, когда вы хотите разделить . Посмотрите это .
Далее, как вы расширяете свойделение для общего деления дел?n, если вы хотите разделить эти два числа x и y из приведенного выше кода.Вы не можете, является ответом, не прибегая к средствам на основе bignum, которые дорогиСмотри Кнут.Взятие по модулю числа больше вашего размера не работает.
Позвольте мне объяснить.Попробуйте 21979182173 мод 1099. Давайте для простоты предположим, что поле наибольшего размера, которое мы можем иметь, состоит из трех цифр .Это надуманный пример, но самый большой размер поля, который я знаю, использует 128 бит с использованием расширений gcc.В любом случае, дело в том, что вы:
21 979 182 173
Разделите свой номер на конечности.Затем вы берете по модулю и сумме:
21 1000 1182 1355
Это не работает.Вот где Avi верен, потому что это форма изгнания девяток или их адаптация, но здесь это не работает, потому что наши поля переполнены для начала - вы используете модуль для обеспечения того, чтобы каждое поле оставалось в пределахразмер его конечности / поля.
Так в чем же решение?Разделите ваш номер на серию подходящих по размеру бигнумов?И начать использовать функции bignum для расчета всего, что вам нужно?Это будет намного медленнее, чем любой существующий способ манипулирования полями напрямую.
Теперь, возможно, вы предлагаете этот случай только для деления на конечность, а не на бигнум, и в этом случае он может работать, но деление по Хензелю и предварительно вычисленные обратные значения и т. Д. Делают без требования преобразования .Я понятия не имею, будет ли этот алгоритм быстрее, чем, скажем, деление Хензеля;это было бы интересное сравнение;проблема возникает с общим представлением в библиотеке bignum .Представление, выбранное в существующих библиотеках bignum, объясняется причинами, которые я расширил, - это имеет смысл на уровне сборки, где это было впервые сделано.
В качестве примечания;Вам не нужно использовать uint32_t для представления своих конечностей.Вы в идеале используете размер, равный размеру регистров системы (скажем, uint64_t), чтобы вы могли воспользоваться версиями, оптимизированными для сборки.Таким образом, в 64-битной системе adc rax, rbx устанавливает переполнение (CF), только если результат переполняет 2 ^ 64 бита.
tl; dr версия: проблема не в вашем алгоритмеили идея;это проблема преобразования между базами, так как представление, которое вам нужно для вашего алгоритма, не самый эффективный способ сделать это в add / sub / mul и т. д. Перефразировать кнут: Это показывает разницу между математической элегантностью и вычислительной эффективностью.