CODEWITHSUNDEEP
c++pseudocodeassertion
codiac
codiac

Reputation: 1991

What does overflowing mean in this case?

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.

The full pseudocode is

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

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++?

Upvotes: 4

Views: 258

Answers (2)

Ben Hymers
Ben Hymers

Reputation: 26546

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.

'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

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()));

Upvotes: 1

Tim B
Tim B

Reputation: 41208

In most computer programming languages numbers can only be stored with a limited precision or over a certain range.

For example a C++ integer will often be a 32 bit signed int, capable of storing at most 2^31 as a value.

If you try and multiply together two numbers and the result would be greater than 2^31 you do not get the result you were expecting, it has overflowed.

Upvotes: 2

Related Questions