PDA

View Full Version : Math Question: modulo arithmetic

tofu
2007-Oct-31, 05:26 PM
What is the solution to: -1 mod 10

My java compiler, a javascript program, and the command line linux calculator give me one answer, but Excel, OpenOffice Calc, and google calculator give me a different answer.

2007-Oct-31, 05:33 PM
Mathematica gives 9.

Also according to Wikipedia (http://en.wikipedia.org/wiki/Modular_arithmetic#The_congruence_relation) it is 9.

Moose
2007-Oct-31, 05:36 PM
Hmm. Good question. I guess it depends on the formal definition of modulo function. If there's an absolute value component in the formula (which I think there isn't), then the answer is 1. If not (as I think is true), then the answer should be 9.

The command line linux calculator (bc or a derivative?) should be based on the GNU math.sl library, a very mature library from back when the Venn diagram of mathematicians and programmers overlapped quite a bit more than it does today. I would trust that library long before I trusted spreadsheet software or a Google adware product.

tofu
2007-Oct-31, 06:11 PM
Here are two more:
-------
A c program:
int main(void) {int i = -1 % 10; printf("%d",i);}
compiled with gcc. The output is -1
-------
coldfusion:
writeOutput( -1 mod 10 );
output is -1
-------

So the count so far:
-1 mod 10 = -1
gcc, actionscript, java, javascript, coldfusion, command-line calculator

-1 mod 10 = 9

Moose
2007-Oct-31, 06:13 PM
Wait, what? Hold on. You linked to the math.sl library on linux?

tofu
2007-Oct-31, 06:47 PM
The only thing I linked to was stdio, as far as I know.

Moose
2007-Oct-31, 06:50 PM
*snaps fingers* Right, that's an operator, not a function. And you're using the gcc. I am disappointed and dismayed, but that's good to know for future reference. If I have to modulo a negative number, I'll have to set up a function to do it right.

orionjim
2007-Oct-31, 06:57 PM
Great question tufo!

http://mathforum.org/library/drmath/view/52343.html

A quick summary from his site is:
There are different ways of thinking about remainders when you deal
with negative numbers...
The mod function is defined as the amount by which a number exceeds the
largest integer multiple of the divisor that is not greater than that
number.

With that said and being a programmer I'm concerned with what you are seeing in 'C', Java, Javascript and the others. Of course if you are programming you probably know what you want.

The thing I learned is to make sure you know what the language is giving you.

Like I said "Great Question"!

Jim

01101001
2007-Oct-31, 07:18 PM
With that said and being a programmer I'm concerned with what you are seeing in 'C', Java, Javascript and the others.

Wikipedia: Modulo operation (http://en.wikipedia.org/wiki/Modulo_operation) has a table of result signs for a long list of languages.

There are various ways of defining a remainder, and computers and calculators have various ways of storing and representing numbers, so what exactly constitutes the result of a modulo operation depends on the programming language and/or the underlying hardware. [...] The choice between the two possible remainders depends on the signs of a and n and the programming language being used. [...] See the table for details.

tofu
2007-Oct-31, 07:36 PM
Good info. Thanks guys. I can always count on this forum to teach me something.

tdvance
2007-Nov-01, 12:35 AM
being a mathematician, "modulo" represents an entire class of numbers.

So, what is -1 modulo 10? It is the entire class of numbers consisting of:

..., -21, -11, -1, 9, 19, 29, ...

the question is, which of these is the "canonical" result? In C (at least, I THINK this is standard and not compiler-dependent) -1 mod 10 should give -1.

My personal philosophy for "a mod b" is:

if b>0, choose the smallest positive result congruent to a mod b.

If b<0, choose the largest negative result congruent to a mod b.

If b=0, well, you're dividing by zero--don't do that.

I have no problem with b not being an integer (or a for that matter)--

a mod b is the number c such that for some integer n, a + c*n = b, c has the same sign as b (unless c=0), and of all numbers satisfying these two properties, c has the smallest absolute value.

Thus, 7.5 modulo 3.4 is 0.7.

But--I don't think this is generally agreed on, by mathematicians or programming languages.

Ilya
2007-Nov-01, 01:07 AM
Keep in mind that in modulo 10, -1=9