Можно ли получить исходное значение числа после нескольких умножений ** с переполнением **?

Question

Резюме: Есть ли способ сделать это?Вот что я имею в виду: предположим, у меня есть число без знака int .Затем я умножаю его несколько раз (и есть переполнение, , которое ожидается ).Тогда можно ли «вернуть» исходное значение обратно?

---

В деталях:

Это все о Рашин-Карп, хеш-роллинг .Что мне нужно сделать, так это: у меня есть хеш длинной строки, например: «abcd».Тогда у меня есть хеш для более короткой подстроки - например, "CD".Как вычислить хэш «ab» с помощью O (1), используя два заданных хеша?

Что у меня сейчас есть в качестве алгоритма:

• вычесть хеш «cd» изХеш "abcd" (удалите последние элементы из полинома)
• делит хеш "abcd" на p ^ len( "cd" ), где p - это основание (простое число).

Итак, это:

a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 - abcd

c * p ^ 1 + d * p ^ 0 - cd

ab получает:

( 
  ( a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 ) -
  ( c * p ^ 1 + d * p ^ 0 ) 
)
/ ( p ^ 2 )
= a * p ^ 1 + b * p ^ 0

И это работает, если у меня нет переполнения (если p - небольшое число).Но если это не так - это не работает.

Есть какой-то трюк или что-то?

PS Тег c++ из-за переполнения числа, поскольку он специфичен (и отличается от python, схема или sth)

Answer 1

Не знаю о части переполнения, но есть способ вернуть исходное значение.

Китайская теорема об остатках очень помогает.Давайте назовем h = abcd - cd.G - это значение h без переполнений G = h + k*2^32, при условии, что переполнение просто равно %2^32.И, таким образом, ab = G / p^2.

G = h (mod 2^32)
G = 0 (mod p^2)

Если p ^ 2 и 2 ^ 32 взаимно просты.На этой странице Китайская теорема об остатках дает нам

G = h * b * p^2 (mod 2^32 * p^2)

Где b является модульной мультипликативной инверсией р ^ 2 по модулю 2 ^ 32, b * p^2 = 1 (mod 2^32)После того, как вы вычислили G, просто разделите на p^2, чтобы найти ab.

Надеюсь, я не допустил ошибок ...

Answer 2

Расширенный евклидов алгоритм является хорошим решением для этого, но он слишком сложен и труден для реализации.Есть лучший.

---

И есть еще один способ сделать это (спасибо моему другу (:)

В wikipedia есть хорошая статья - модульный мультипликативный обратный с использованием теоремы Эйлера в случае, когда m и a взаимно просты:

, где φ(m) равно Функция Эйлера .

В моем случае m (по модулю) - это размер типа хэша - 2^32, 2^64 и т. Д. (В моем случае - 64 бита).
Ну, это означает, что мы должны найти только значение φ(m). Но подумайте об этом - m == 2 ^ 64, так что это дает нам гарантию, что m будет взаимно простым со всеми нечетнымичисла и НЕ будут взаимно простыми для любого четного числа . Итак, нам нужно получить число всех значений и разделить их на 2.

Кроме того, мы знаем, что m будет без знака, так как в противном случае у нас возникнут некоторые проблемы. Чем это даст нам возможность сделать это:

hash_t x = -1;
x /= 2;
hash_t a_reverse = fast_pow( a, x );

Ну, насчет 64-битных чисел, x - это действительно большое число (19 цифр: 9 223 372 036 854 775 807), но fast_pow действительно быстрое, и мы можем кэшировать обратное число, если нам нужно более одного запроса.

fast_pow - это хорошо известный алгоритм:

hash_t fast_pow( hash_t source, hash_t pow )
{
    if( 0 == pow )
    {
        return 1;
    }

    if( 0 != pow % 2 )
    {
        return source * fast_pow( source, pow - 1 );
    }
    else
    {
        return fast_pow( source * source, pow / 2  );    
    }

}

---

Добавление: например:

    hash_t base = 2305843009213693951;  // 9th mersenne prime
    hash_t x = 1234567890987654321;

    x *= fast_pow( base, 123456789 );   // x * ( base ^ 123456789 )

    hash_t y = -1;
    y /= 2;
    hash_t base_reverse = fast_pow( base, y );

    x *= fast_pow( base_reverse, 123456789 );   // x * ( base_reverse ^ 123456789 )
    assert( x == 1234567890987654321 ) ;

работает отлично и очень быстро.

Answer 3

У вас есть * b = c мод 2 ^ 32 (или мод что-то еще, в зависимости от того, как вы делаете свой хэш).Если бы вы могли найти d таким, что b * d = 1 mod 2 ^ 32 (или mod любым другим), то вы могли бы вычислить a * b * d = a и получить a.Если gcd (b, mod 2 ^ 32) = 1, то вы можете использовать http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm, чтобы найти x и y, такие что b * x + 2 ^ 32 * y = 1, или b * x = 1 - y* 2 ^ 32, или b * x = 1 mod 2 ^ 32, поэтому x - это число, на которое вы хотите умножить.

Answer 4

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

Но обратите внимание, что это будет иметь отдельное представление для -0 и +0, и что вам, вероятно, придется вручную кодировать арифметические операции в процессе.

Некоторые инструкции процессораАгностика целочисленного представления, но не всех.

Answer 5

Вы должны использовать целые числа без знака для получения определенного поведения переполнения (по модулю 2 ^ N).Целочисленное переполнение со знаком не определено.

Кроме того, вместо деления следует умножить на обратное мультипликативное значение p по модулю соответствующее значение.Например, если p = 3 и ваши значения хеш-функции равны 8 битам, умножьте их на 171, потому что 171 * 3 = 513 = 2 * 256 + 1.Мультипликативное обратное существует, если p и значение по модулю относительно простые.

Answer 6

Таким образом, переполнение на самом деле просто для вашего компилятора;стандарт C / ++ фактически предполагает, что переполнение является неопределенным поведением.Поэтому, когда вы переполнены, на самом деле вы ничего не можете сделать, потому что ваша программа перестает быть детерминированной.

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