Какой алгоритм следует использовать для высокопроизводительного большого целочисленного деления?

Question

Я кодирую большие целые числа в массив из size_t. У меня уже работают другие операции (добавление, вычитание, умножение); а также деление на одну цифру. Но я хотел бы совместить временную сложность моих алгоритмов умножения, если это возможно (в настоящее время Toom-Cook).

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

Мой вопрос: как я на самом деле это делаю? Какой тип мультипликативного обратного лучше всего на практике? Modulo 64^digitcount? Когда я умножаю мультипликативный обратный на мой делитель, могу ли я уклониться от вычисления части данных, которые будут выбрасываться из-за целостного усечения? Может ли кто-либо предоставить псевдокод C или C++ или дать точное объяснение того, как это должно быть сделано?

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

Редактировать: Я откопал туда, где я получил обратный подход, упомянутый выше. На стр. 312 «Искусство компьютерного программирования, Том 2: Семинумерные алгоритмы», Кнут обеспечивает «Алгоритм R», который является высокоточным обратным. Он говорит, что его временная сложность меньше, чем умножения. Однако нетривиально преобразовать его в C и проверить его, а также неясно, сколько накладных расходов и т. Д. Будет потреблено до тех пор, пока я не закоучу это, что займет некоторое время. Я отправлю его, если никто меня не ударит.

Answer 1

Библиотека GMP обычно является хорошей ссылкой для хороших алгоритмов. Их documented algorithms for division в основном зависят от выбора очень большой базы, так что вы делите 4-значное число на 2-значное число, а затем продолжаете через длинное разделение.

Для длительного разделения потребуется вычислить 2 цифры на 1 цифру; это может быть сделано либо рекурсивно, либо путем предвычисления обратного и оценивания частного, как это было бы с сокращением Барретта.

При делении 2n -разрядных номера с помощью n битового числа, рекурсивных затратами O(M(n) log(n)) версии, где M(n) является стоимостью умножения числа n -разрядных.

Версия, использующая сокращение Барретта, будет стоить O(M(n)), если вы используете алгоритм Ньютона для вычисления обратного, но, согласно документации GMP, скрытая константа намного больше, поэтому этот метод предпочтительнее только для очень больших делений.

---

Более подробно, основной алгоритм позади большинства алгоритмов разделения является «фактор оценивается с уменьшением» расчет, вычисление (q,r) так, что

x = qy + r 

, но без ограничения этим 0 <= r < y.Типичный цикл

• Расчетный фактор q из x/y
• Compute соответствующего снижения r = x - qy
• При необходимости отрегулировать фактор, так что снижение r в некотором желаемом интервале
• Если r является слишком большим, затем повторите с r вместо x.

Фактор x/y будет суммой всех q с производства, а конечное значение r будет истинным остальное.

Учебное пособие с длинным разделом, например, имеет эту форму. например шаг 3 охватывает те случаи, когда цифра, которую вы предположили, была слишком большой или слишком малой, и вы настраиваете ее, чтобы получить правильное значение.

разделяй и властвуй подход оценивает частное x/y вычисляя x'/y' где x' и y' являются первые цифры x и y. Есть много возможностей для оптимизации, регулируя их размеры, но IIRC вы получаете лучшие результаты, если x' в два раза больше цифр y'.

Метод умножения на обратный подход, ИМО, самый простой, если вы придерживаетесь целочисленной арифметики. Основной метод

• Эстимейта инверсия y с m = floor(2^k/y)
• Estimate x/y с q = 2^(i+j-k) floor(floor(x/2^i) m/2^j)

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

Ошибка боль анализировать, но если я помню, как это сделать, вы хотите выбрать i и j так что x ~ 2^(i+j) из-за того, как накапливаются ошибки, и вы хотите выбрать x/2^i ~ m^2, чтобы минимизировать общую работу.

Последовавшее сокращение будет иметь r ~ max(x/m, y), так что дает эмпирическое правило для выбора k: вы хотите, чтобы размер m быть о количестве бит фактора вы вычислить на итерацию — или, что эквивалентно числом бит вы хотите для удаления с x за итерацию.

Answer 2

Я не знаю мультипликативный обратный алгоритм, но это звучит как модификация Montgomery Reduction или Barrett's Reduction.

Я делаю большие подразделения немного по-другому.

См. bignum division. Особенно взгляните на делитель аппроксимации и на 2 ссылки. Один из них - мой разделитель с фиксированной точкой, а другие - быстрые альцики умножения (например, karatsuba, Schönhage-Strassen на NTT) с измерениями и связь с моей очень быстрой реализацией NTT для 32-разрядной базы.

Я не уверен, что обратный мультипликатор является способом.

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

Наиболее распространенным делителем, который я видел в реализации, является деление Ньютона-Рафсона, которое очень похоже на делитель аппроксимации по ссылке выше.

Аппроксимация/итеративные делители обычно используют умножение, определяющее их скорость.

Для достаточно малых чисел, как правило, длинные бинарное деление и 32/64bit код базового деление достаточно быстро, если не быстро: как правило, они имеют небольшие накладные расходы, и пусть n быть максимальное значение обрабатывается

(не число цифр!)

Binary пример деление:

O(log32(n).log2(n)) = O(log^2(n)) Is.
Он проходит через все значимые бит. На каждой итерации вам нужно compare, sub, add, bitshift. Каждая из этих операций может быть выполнена в log32(n), а log2(n) - это количество бит.

Вот пример бинарного деления от одного из моих шаблонов BigInt (C++):

template <DWORD N> void uint<N>::div(uint &c,uint &d,uint a,uint b) 
    { 
    int i,j,sh; 
    sh=0; c=DWORD(0); d=1; 
    sh=a.bits()-b.bits(); 
    if (sh<0) sh=0; else { b<<=sh; d<<=sh; } 
    for (;;) 
     { 
     j=geq(a,b); 
     if (j) 
      { 
      c+=d; 
      sub(a,a,b); 
      if (j==2) break; 
      } 
     if (!sh) break; 
     b>>=1; d>>=1; sh--; 
     } 
    d=a; 
    } 

N этого количество 32-битных DWORD с используемой для хранения BigInt номера.

• c = a/b
• d = a % b
• qeq(a,b) сравнение: a >= b больше или равно (сделано в log32(n)=N)
  возвращает 0 для a < b, 1 для a > b, 2 для a == b
• sub(c,a,b) является c = a - b

Прирост скорости достигается от этого не использует умножение (если не считать бит сдвига)

Если вы используете цифру с большим основанием, таким как 2^32 (блоки ALU), то вы можете переписать целое по полиномиальному стилю с использованием 32-битной сборки в операциях ALU.
Это, как правило, даже быстрее, чем двоичное длинное деление, идея состоит в том, чтобы обрабатывать каждый DWORD в виде одной цифры или рекурсивно делить использованную арифметику на половину, до тех пор, пока не будут задействованы возможности ЦП.
См division by half-bitwidth arithmetics

На вершине всего, что при вычислении с bignums

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

Накладные расходы могут испортиться.

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