Question of the Week: How can computers calculate exponential math without overflow errors?

July 30, 2012 by . 5 comments

This weeks question of the week comes from Kit-Ho who poses:

Studying some RSA encrypt/decrypt methods, I found this article: An Example of the RSA Algorithm It requires this to decrpyt this message enter image description here The total result of enter image description here is so big, for a 64-bit/32-bit machine, I don’t believe it can hold such a big value in one register. How does the computer do it without an overflow?

 

For those of you that may not know what this “Overflow” that Kit mentioned, he’s talking about a term Stack Overflow.   Here’s the official “Wiki” definition:

 

In software, a stack overflow occurs when too much memory is used on the call stack. The call stack contains a limited amount of memory, often determined at the start of the program. The size of the call stack depends on many factors, including the programming language, machine architecture, multi-threading, and amount of available memory. When a program attempts to use more space than is available on the call stack (that is, when it attempts to access memory beyond the call stack’s bounds, which is essentially a buffer overflow), the stack is said to overflow, typically resulting in a program crash.  This class of software bug is usually caused by one of two types of programming errors.    

 

As pointed out by Dennis (thanks!) I completely got this wrong.  Stack overflow isn’t the issue, but rather integer overflow:

In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is too large to be represented within the available storage space. For instance, adding 1 to the largest value that can be represented constitutes an integer overflow. The most common result in these cases is for the least significant representable bits of the result to be stored (the result is said to wrap). On some processors like GPUs and DSPs, the resultsaturates; that is, once the maximum value is reached, attempts to make it larger simply return the maximum result.  

For example, a mechanical odometer, has a rollover (or reset) after a certain amount of miles:

This is the same as computer integer overflow, where the size of the numbers needed are greater than the object type can hold.  Kit-Ho’s example RSA link exceedes the C#’s max value of 18,446,744,073,709,551,615 of the long type.

Dietrich Epp came up with a great answer as to how computers can calculate these large numerical calculations:

Because the integer modulus operation is a ring homomorphism (Wikipedia),
(X * Y) mod N = (X mod N) * (Y mod N) mod N 
You can verify this yourself with a little bit of simple algebra. Computers use this trick to calculate exponentials in modular rings without having to compute a large number of digits. enter image description here In algorithmic form,
 
-- compute X^I mod N  
function expmod(X, I, N)  
    if I is zero 
        return 1 
    elif I is odd 
        return (expmod(X, I-1, N) * X) mod N 
    else Y <- expmod(X, I/2, N) 
        return (Y*Y) mod N 
    end if 
end function 
You can use this to compute (855^2753) mod 3233 with only 16-bit registers, if you like. However, the values of X and N in RSA are much larger, too large to fit in a register. A modulus is typically 1024-4096 bits long! So you can have a computer do the multiplication the “long” way, the same way we do multiplication by hand. Only instead of using digits 0-9, the computer will use “words” 0-216-1 or something like that. (Using only 16 bits means we can multiply two 16 bit numbers and get the full 32 bit result without resorting to assembly language. In assembly language, it is usually very easy to get the full 64 bit result, or for a 64-bit computer, the full 128-bit result.)

-- Multiply two bigints by each other 
function mul(uint16 X[N], uint16 Y[N]): 
    Z <- new array uint16[N*2] 
    for I in 1..N 
        -- C is the "carry" 
        C <- 0 
        -- Add Y[1..N] * X[I] to Z 
        for J in 1..N 
            T <- X[I] * Y[J] + C + Z[I + J - 1] 
            Z[I + J - 1] <- T & 0xffff 
            C <- T >> 16 
        end 
        -- Keep adding the "carry" 
        for J in (I+N)..(N*2) 
            T <- C + Z[J] 
            Z[J] <- T & 0xffff 
            C <- T >> 16 
        end 
    end 
    return Z 
end 
-- footnote: I wrote this off the top of my head 
-- so, who knows what kind of errors it might have 
This will multiply X by Y in an amount of time roughly equal to the number of words in X multiplied by the number of words in Y. This is called O(N2) time. If you look at the algorithm above and pick it apart, it’s the same “long multiplication” that they teach in school. You don’t have times tables memorized out to 10 digits, but you can still multiply 1,926,348 x 8,192,004 if you sit down and work it out. Long multiplication:
 
    1,234 
  x 5,678 
 --------- 
    9,872 
   86,38 
  740,4 
6,170 
--------- 
7,006,652 
There are actually some faster algorithms around for multiplying (Wikipedia), such as Strassen’s fast Fourier method, and some simpler methods which do extra addition and subtraction but less multiplication, and so end up faster overall. Numerical libraries like GMP are capable of selecting different algorithms based on how big the numbers are: the Fourier transform is only the fastest for the largest numbers, smaller numbers use simpler algorithms.

 

5 Comments

Subscribe to comments with RSS.

  • Torleif says:

    For the beginning of this post, isn’t ‘stack overflow’ something else than the ‘overflow’ mentioned here? As far as I know, ‘Stack overflow’ is when there have been too many method calls (infinite call loop for example), while a regular overflow in this context is when you have a number which is too big for a 32/64-bit integer and it overflows, either by ‘looping around’ or failing or whatever.

  • sblair says:

    I don’t think this has anything to do with a stack overflow. It is simply that the numerical range of 64-bit IEEE 754 floating point numbers isn’t large enough to contain 855^2753. The possible range is approximately −10^308 to +10^308.

  • Dennis says:

    @sblair is correct: This has nothing to do with Stack Overflow.

    The concern here is integer overflow, since the maximum representable value of a 64-bit register is 2 ^ 64 – 1 = 18,446,744,073,709,551,615.

    In contrast, the result of 855 ^ 2753 would need 23,814 bits to be represented.

  • Fox says:

    The calculations are handled by software (sometimes native data types) that can deal with numbers of arbitrary length. These are commonly referred to as “BigDecimal” or “BigInteger” (though I wouldn’t be surprised if some large but bounded systems used these names as well).

  • Fox says:

    Whoops. I see this was answered in greater depth in the second half of the OP.

  • Leave a comment

    Log in
    with Stack Exchange
    or