在这种情况下，溢出意味着什么? [英] What does overflowing mean in this case?

问题描述

我发现了一种乘模运算的算法.下一个伪代码摘自Wikipedia，页面Modular exponention，从右到左二进制方法部分.

I have found an algorithm to multiply in modoulus. The next pseudocode is taken from wikipedia, page Modular exponention, section Right-to-left binary method.

完整的伪代码是

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 ::(模数-1)*(模数-1)不会溢出基数；这条线是什么意思，如何用C ++进行最佳编程?

I don't understand what this line of pseudocode means Assert :: (modulus - 1) * (modulus - 1) does not overflow base; what does this line mean and how would it be best programmed in C++?

推荐答案

Assert (大致而言)是一种检查前提条件的方法；这必须是正确的，才能继续".在C ++中，您将使用 assert 宏或您自己的手动声明系统.

Assert is (roughly speaking) a way to check preconditions; "this must be true to proceed". In C++ you'll code it using the assert macro, or your own hand-rolled assertion system.

不溢出"表示该语句不应太大而不能容纳 base 的任何整数类型；这是一个乘法，所以很有可能.C ++中的整数溢出是未定义的行为，因此，谨防它是明智的！有很多资源可以解释整数溢出，例如这篇关于Wikipedia的文章

'does not overflow' means that the statement shouldn't be too large to fit into whatever integer type base is; it's a multiplication so it's quite possible. Integer overflow in C++ is undefined behaviour, so it's wise to guard against it! There are plenty of resources out there to explain integer overflow, such as this article on Wikipedia

要在C ++中进行检查，一种很好的简单方法是将中间结果存储在较大的整数类型中，并检查其是否足够小以适合目标类型.例如，如果 base 是 int32_t ，请使用 int64_t 并检查其是否低于 static_cast< int64_t>(std :: numeric_limits< int32_t> :: max()):

To do the check in C++, a nice simple approach is to store the intermediate result in a larger integer type and check that it's small enough to fit in the destination type. For example, if base is int32_t use int64_t and check that it's lower than 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()));

这篇关于在这种情况下，溢出意味着什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！