Остаток от деления на 2^p-1

Revision ru1, by dmkz, 2019-03-09 13:27:03

Всем привет! Сегодня обнаружил, что старая статья про остатки от деления на 2p - 1 недоступна больше по этому адресу, ее нет ни в кэше яндекса, ни в кэше гугла. В ней описывались и доказывались интересные факты о вычислении остатков от делений на числа вида 2p - 1, а также было указано как и где они применялись. Если эта статья доступна на каком-то другом ресурсе, или вы знаете аналогичную статью, то прошу поделиться в комментариях. Ниже я кратко перескажу то, что помню, чтобы информация не потерялась, вдруг никто не найдет.

Для начала рассмотрим систему счисления по основанию 10 и остатки от деления на 9. Известен признак делимости на 9: число делится на 9, если сумма его цифр делится на 9. Например, число 936 делится на 9, так как сумма его цифр 9 + 3 + 6 = 18 делится на 9. Действительно, 936 = 104·9. Этот признак делимости следует из представления числа в десятичной системе счисления:

В общем случае, если число представлено в системе счисления по основанию b, то для взятия остатка от деления на b - 1 можно взять остаток от суммы его цифр, так как для любого p верно: .

Так как в компьютерах используется двоичная система счисления, то мы можем только при помощи битовых операций брать остатки от деления на числа вида 2p - 1, представляя числа в системе счисления по основанию 2p. Это применяется, например, в вычислении полиномиального хеша от строк по модулям 231 - 1 и 261 - 1 — простым числам Мерсенна.

Стоит заметить, что если осуществлять только переход от числа к сумме его цифр, то мы будем получать смещенный остаток, то есть число из диапазона [1, 2p - 1]? Чтобы этого избежать, необходимо на какой-либо итерации прибавить 1, а в конце из результата вычесть 1, чтобы сместить весь диапазон получаемых остатков от деления из [1, 2p - 1] в [0, 2p - 2].

Примеры

Интересный вопрос: сколько раз нужно перейти от числа к его сумме для вычисления остатка от деления? Если мы представим число n в системе счисления по основанию b, то после взятия суммы его цифр, мы получим число, порядка , то есть, чисто интуитивно, таких редукций нужно сделать немного.

К счастью, нам не нужно считать это для каких-то абстрактных чисел n и b, посчитаем лучше, сколько нужно редукций, чтобы взять остаток от деления 64-битного числа по модулю 231 - 1. Для этого нужно представить число в системе счисления по основанию 231, получим: a + 231·b + 262·c. Знаем, что a + b <  = 2·(231 - 1), c <  = 3, получаем a + b + c <  = 232 + 1 <  = 231·2 + 1. Нам точно понадобится еще одна редукция, и тогда худшим случаем будет, когда сумма цифр данной суммы снова превысит 231 - 1, и нам нужно будет сделать последнюю редукцию, получаем, что 3 — достаточно.

В качестве дополнения, ниже приведены реализации операций сложения, вычитания и умножения по модулю 261 - 1, использующиеся в полиномиальном хеше.

Операции в поле по модулю 2^61-1
Tags целочисленная арифметика, битовые операции, остатки от деления, хеши

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian dmkz 2019-03-09 15:56:13 496 Мелкая правка: '[user:r3t], что догадался поискать там, [запрос](' -> '[user:r3t]. [запрос]('
ru1 Russian dmkz 2019-03-09 13:27:03 5168 Первая редакция (опубликовано)