Wikipedia:Reference desk/Archives/Computing/2017 January 15

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 15

Modular arithmetic with limited integer range

Let's say I'm using a programming language where integers range from $-x$ to $x-1$ (inclusive) (for example, -2^31 to 2^31 - 1), and $x+1=-x$, $x+2=-x+1$, etc. What algorithm can I use to compute $(a+b)$ modulo $m$, where $1\leq a,b,m\leq x-1$? Obviously the result will be expressible within the range of integers. Assume I don't have access to any larger integer type and values can't be promoted to a larger type at any point of the algorithm. 24.255.17.182 (talk) 21:06, 15 January 2017 (UTC)

Why do you have 1 as a lower limit instead of 0? Anyway (a mod m)+(b mod m) mod m will do the job. Or for 2^31-1 as the upper limit one could use unsigned arithmetic with a range 0..2^32-1 for the add and modulo in (a+b) mod m. Dmcq (talk) 00:07, 16 January 2017 (UTC)

(a mod m)+(b mod m) could still be larger than 2^32-1. 24.255.17.182 (talk) 01:11, 16 January 2017 (UTC)

I assume that when you say "etc." you mean that if a calculation overflows then $2x$ is added or subtracted to/from the result, the common behavior on 2's complement computers. In that case, if (a mod m)+(b mod m) cannot be represented, it will come out as a negative number. So just test if it is negative, and in that case, subtract m. This will underflow and you'll get the correct positive numebr. --69.159.60.210 (talk) 07:52, 16 January 2017 (UTC)

This is fine in, say, Java or machine language, but it won't work in C or C++, where signed addition is not defined to wrap around (and often won't, even on two's-complement machines, because of optimizations). -- BenRG (talk) 20:23, 17 January 2017 (UTC)

If a and b are positive and less than 2³¹ then their sum is less than 2³², so unsigned(a mod m) + unsigned(b mod m) won't overflow. Even unsigned(a)+unsigned(b) won't overflow. -- BenRG (talk) 20:23, 17 January 2017 (UTC)

Quote from Zeller's congruence: "The formulas rely on the mathematician's definition of modulo division, which means that −2 mod 7 is equal to positive 5. Unfortunately, the way most computer languages implement the remainder function, −2 mod 7 returns a result of −2". I once had to field-service 10,000 time lapse video recorders because the programmer used the wrong Modulo, causing them all to crash hard on a particular date. --Guy Macon (talk) 15:24, 16 January 2017 (UTC)

However, since we were told we were being given positive numbers, that won't be an issue this time. --69.159.60.210 (talk) 19:13, 16 January 2017 (UTC)

Not an expert, but I'm thinking you can arithmetic shift right each number, saving the first remainder R1, then saving R2 = that AND the second, then replacing R1 = R1 XOR with the second. (Hmmm, need to be very careful about that operation with negative numbers; not sure if this was right for them) Add the shifted numbers, getting 0.5a + 0.5b. If m is even, take (0.5a + 0.5b) mod 0.5m. Now do a arithmetic shift left to double this and put R1 back into the result. Add R2. You should not get an overflow, which only happens if you're taking FFFF + FFFF mod FFFF I think, and that's odd. For odd... well, that's the sticky part, isn't it? Maybe take (0.5a + 0.5b) mod (0.5m+0.5), which is 0.5 too low per m, plus (0.5a + 0.5b) div m, then do comparisons to bring it up or down by a single 0.5m unit, suitably adjusting the remainder? I'd have to write the program to find the bugs in that though! Wnt (talk) 15:09, 17 January 2017 (UTC)