Что означает переполнение в этом случае?

Question

Я нашел алгоритм для умножения в modoulus. Следующий псевдокод взят из википедии, стр. Модульная экспоненция, раздел «Двойственный метод справа налево».

Полный псевдокод

function modular_pow(base, exponent, modulus) 
    Assert :: (modulus - 1) * (modulus - 1) does not overflow base 
    result := 1 
    base := base mod modulus 
    while exponent > 0 
     if (exponent mod 2 == 1): 
      result := (result * base) mod modulus 
     exponent := exponent >> 1 
     base := (base * base) mod modulus 
    return result 

Я не понимаю, что эта линия псевдокода означает Assert :: (modulus - 1) * (modulus - 1) does not overflow base; что означает эта линия и как ее лучше всего запрограммировать на C++?

Answer 1

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

Например, целое число C++ часто будет 32-битным подписанным int, способным хранить не более 2^31 в качестве значения.

Если вы попытаетесь размножить два числа, и результат будет больше 2^31, вы не получите ожидаемого результата, он переполнится.

Answer 2

Assert (грубо говоря) способ проверки предварительных условий; «это должно быть правдой». В C++ вы будете кодировать его, используя assert macro, или свою собственную ручную систему утверждения.

«не переполняет» означает, что инструкция не должна быть слишком большой, чтобы вписаться в любой целочисленный тип base; это умножение, так что это вполне возможно. Целочисленное переполнение в C++ - это неопределенное поведение, поэтому разумно защищать его! Существует множество ресурсов для объяснения целочисленного переполнения, например, this article on Wikipedia

Чтобы сделать проверку на C++, простой простой подход состоит в том, чтобы сохранить промежуточный результат в более крупном целочисленном типе и проверить, что он достаточно мал, чтобы вписаться в тип назначения. Например, если base является int32_t использование int64_t и убедитесь, что это ниже, чем static_cast<int64_t>(std::numeric_limits<int32_t>::max()):

const int64_t intermediate = (static_cast<int64_t>(modulus) - 1) * (static_cast<int64_t>(modulus) - 1); 
assert(intermediate < static_cast<int64_t>(std::numeric_limits<int32_t>::max()));