Самый быстрый способ вычисления 128-битного целого по модулю 64-битного целого - PullRequest
Новая
       17

Самый быстрый способ вычисления 128-битного целого по модулю 64-битного целого

53 голосов
/ 02 апреля 2010

У меня 128-разрядное целое число без знака A и 64-разрядное целое число без знака B. Какой самый быстрый способ вычисления A % B - это (64-разрядное) остаток от деления A на B?

Я хочу сделать это на языке C или ассемблере, но мне нужно ориентироваться на 32-битную платформу x86. К сожалению, это означает, что я не могу воспользоваться преимуществами поддержки компилятора для 128-разрядных целых чисел или способности архитектуры x64 выполнять требуемую операцию в одной инструкции.

Edit:

Спасибо за ответы до сих пор. Тем не менее, мне кажется, что предлагаемые алгоритмы будут довольно медленными - разве самый быстрый способ выполнить 128-разрядное 64-разрядное деление состоит в том, чтобы использовать встроенную поддержку процессора для 64-разрядного 32-разрядного деления? Кто-нибудь знает, есть ли способ выполнить большее деление с помощью нескольких меньших делений?

Re: Как часто меняется B?

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

Однако вторая возможная ситуация заключается в том, что B не так часто меняется, как A - их может быть целых 200, чтобы делить на B. Как ваш ответ будет отличаться в этом случае?

Ответы [ 13 ]

1 голос
/ 03 ноября 2016

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

Рассмотрим предложенное решение проблемы переполнения MSN, ограничив ее 1-битным. Мы делаем это путем разбиения задачи на 2, модульного умножения и добавления результатов в конце.

В следующем примере верхний соответствует старшим 64-битным, нижний - младшему 64-битному, а div - делителю. 

unsigned 128_mod(uint64_t upper, uint64_t lower, uint64_t div) {
  uint64_t result = 0;
  uint64_t a = (~0%div)+1;
  upper %= div; // the resulting bit-length determines number of cycles required

  // first we work out modular multiplication of (2^64*upper)%div
  while (upper != 0){
    if(upper&1 == 1){
      result += a;
      if(result >= div){result -= div;}
    }
    a <<= 1;
    if(a >= div){a -= div;}
    upper >>= 1;
  }

  // add up the 2 results and return the modulus
  if(lower>div){lower -= div;}
  return (lower+result)%div;
}

Единственная проблема заключается в том, что если делитель 64-битный, то мы получаем переполнение 1-бит (потеря информации), что дает ошибочный результат.

Меня беспокоит, что я не нашел изящного способа справиться с переполнением.

1 голос
/ 03 апреля 2010

Если у вас последняя машина x86, для SSE2 + есть 128-битные регистры. Я никогда не пытался написать ассемблер для чего-либо, кроме базового x86, но я подозреваю, что есть некоторые руководства.

0 голосов
/ 02 апреля 2010

Поскольку в C нет предопределенного 128-битного целочисленного типа, биты A должны быть представлены в массиве. Хотя B (64-разрядное целое число) может храниться в переменной unsigned long long int , необходимо поместить биты B в другой массив для эффективной работы с A и B.

После этого значение B увеличивается как Bx2, Bx3, Bx4, ... до тех пор, пока оно не станет наибольшим значением B меньше, чем A. И затем (A-B) можно рассчитать, используя некоторое знание вычитания для базы 2.

Это то решение, которое вы ищете?

Страница:
...