Talk:Modulo operation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Remainder algorithms for various moduli[edit]

Such as number modulo 3 := sum of the digits (decimal base)
Example: 62837 mod 3 = 6+2+8+3+7 mod 3 = 26 mod 3 = 2+6 mod 3 = 8 mod 3 = 2

Another: number modulo 7 := number lest the last digit - 2 * last digit (decimal base)
Example: 62837 mod 7 = 6283-14 mod 7 = 6269 mod 7 = 626-18 mod 7 = 608 mod 7 = 60-16 mod 7 = 44 mod 7 = 2

Ïnteresting would be an algorithm for numbers modulo 31; with that you could calculate in your head certain check digits to forge a social security number in situ...


please read this before further action on the article[edit]

This Modulo operation page was created because there was a need to separate the many meanings of the word "modulo" which were all put together in the articles modulo and modular arithmetic with lots of overlap, ambiguity, and incoherence. As result, the modulo page was put (and still is) on the list Wikipedia:Pages needing attention/Mathematics, although ever since it is been significantly improved.

The biggest two mistakes done by the authors contributing to modular arithmetic was to not read the article before modifying it, and not knowing what "modular arithmetic" acually means. As consequence, I am sorry to say this, but the very best version of the page modular arithmetic was the very first.

This page now contains exclusively information about the remainder function in computer science, no more no less. This is according to the belief that separate matters need to be kept in different places in order to avoid confusion.

Care has been taken in this article to refer to the proper place discussing the relationships between the many meanings of modulo.

If by any means you do not agree with creating this article, please express your opinion before attepting to delete this article or to revert it to the form it was before the cleanup. Thank you. Oleg Alexandrov 04:20, 3 Jan 2005 (UTC)

Thank you for separating this out; a separate article for modulo-as-used-in-computing should have existed from the start. As one of the people who upset you by expanding and rephrasing parts of the original article in ways that reflected my ignorance of modular arithmetic, I apologize for upsetting your delicate sensibilities.
However, your implicit insistence that computer programmers (and users of calculators with 'mod' buttons) be well-versed in the nuances of modular arithmetic and the ways in which modulo operators & functions both refine and place arbitrary constraints on the pure mathematical theory is missing the point of Wikipedia, and putting the cart before the horse. I came here as a programmer looking to better understand why "a % b" produced (to me) weird results when one of the operands was negative. You seem to be of the opinion that I should already know the answer, or that it was perfectly clear from the original description of modular arithmetic. It was not (or at least, was predicated on a more thorough understanding of remainder than the average high school graduate is likely to have). - mjb 19:38, 20 Jan 2005 (UTC)
Hi there. I am happy you agree that the articles should have been separated. I see your point above. The original problem is that "modulo" means so many things to so many people, so it is hard to make everybody happy. Some of the answers to your questions should have been on the remainder page, rather than on modular arithmetic. I will put more stuff on that page soon.
We can continue in the discussion I just started on Talk:Modular arithmetic about the future of that page. Oleg Alexandrov | talk 20:30, 20 Jan 2005 (UTC)
Hi there. Again, you have point. Could you take a look at the remainder page and let me know what you think. I am sorry if you thought I am kind of elitist or something. I do think though that the remainder page is a better place to talk about your mod issue. This because modular arithmetic heavily relies on the remainder concept, but is, in itself, much more than just the remainder issue. Looking forward to feedback. Cheers, Oleg Alexandrov | talk 23:22, 20 Jan 2005 (UTC)

Remainders for non-integers[edit]

I've edited both this article (Modulo operation) and remainder in order to make them both more encyclopedic and to explain things in a way that should make it suitable for the audiences likely to be reading the articles (those whose level of understanding is about where mine was before I started researching the articles). Please review the new versions and see if there are any errors.

One major change I made in this article was an attempt to address the fact that it stated that a and n must be integers. Computers actually also allow floating point, and perhaps even complex numbers, to be used. For example, mod(5.5, 1.3) returns 0.3 (actually, 0.29999999999999982 on my Win32 Python build, due to inherent limitations of floating-point number representation in a binary storage system, for which I'm sure there's an article on Wikipedia somewhere). What I did not do was make a similar change to the remainder article. I would prefer someone more knowledgable than me to clarify whether, and how, non-integers can be divided to produce a quotient and remainder outside of the context of computing. If you or someone could tackle that, that would be great. Thanks! - mjb 04:15, 30 Jan 2005 (UTC)

I replied on Talk:Remainder. Again, mathematicians don't use these generalizations. Actually, you know what we should add on remainder? Something must be said about remainder when dividing polynomials. That is indeed an existing concept, and a very important one in math. Oleg Alexandrov | talk 05:14, 30 Jan 2005 (UTC)

On what should be moved and to where[edit]

I recommend moving modular operation to this page near the beginning to first define what the modulo function actually does. I say move it here because modular aritmetic is a far more common thing to be searced for and that page can become a redirect page. The clock arithmetic page should also be made to be a redirect page because clock arithmetic is just another way to say it, and not the correct one I might add. As for what to do with advanced modular arithmetic I think it should be mentioned here and the page made into a redirect as well, because it is just more elaboration on a higher level; nothing truly unique enough to really give it its own page.

Either way I am going to move clock arithmetic here and make it a redirect (if it hasn't already been done) because that really makes the most sense for it as it really is just another, less correct, way of saying modular aritmetic.

Guardian of Light 5 July 2005 14:31 (UTC)

1. modular operation is simply a recently-created redirect to this article; there was never anything else in it, so there is nothing to merge. Is the redirect insufficient?
2. The modulo operation article contains a significant amount of info that is specific to its topic, and it is fairly specialized to the computing field, so it really should remain in a separate article that is merely referenced from the modular arithmetic article. There is nothing to do; nothing needs to be merged. — mjb 5 July 2005 23:54 (UTC)
While the modulo operation does have things in common with modular arithmetic, I would argue that those similarites end at taking the remainder. But even here things are different. Modular arithmetic deals with integers, this article deals mostly with real numbers. I agree with Mjb that this article has a lot of computing specific information which has no place in modular arithmetic. Oleg Alexandrov 6 July 2005 03:21 (UTC)
Yup. I think the modulo operation is also put to use in ways that resemble modular arithmetic, while the operation itself is very remainder-focused. For example, when you have a set of data that is grouped in repeating structures, like an 80×25 grid of character cells in a text display, and you want to know the position (row & column) of the 993rd cell (assume the cells are numbered first by column, then row), the modulo operation is quite useful: row=floor(993÷80) and column=modulo(993÷80) — or column=993 modulo 80. That's a fairly high-level application. A lower-level or more general application would be to find relative offset of a piece of information in any sequential, cyclic data structure, like bits in fixed-width binary values, upon which all primitive datatypes are based. It crops up a lot in binary arithmetic. So you can see (perhaps) how its use quite resembles modular arithmetic in this regard, and the use of the word "modulo" is appropriate as well, but the operation itself is not synonymous with the more general topic of modular arithmetic. — mjb 6 July 2005 05:44 (UTC)
I see your points. Okay, I'm done here then.Guardian of Light 6 July 2005 13:28 (UTC)

Operator Symbols[edit]

In the section Remainder calculation for the modulo operation, a formula for performing the modulo operation uses a symbol which is apparently the floor function. The symbol encloses the fraction and looks like brackets [] minus the top horizontal lines. This is to suggest adding an internal link to the floor function and/or defining the symbol after the formula. --Sablime 03:13, 1 December 2005 (UTC)

Done. By the way, one should write ==Operator symbol==, and not ==Operator Symbols==. That if you allow me to pick at minor things also. :) Oleg Alexandrov (talk) 04:02, 1 December 2005 (UTC)
Thank you for your time and effort. Your edit will help people like me who do not recognize the notation. Also thanks for the capitalization tip. Sablime 04:30, 2 December 2005 (UTC)

ANSI C[edit]

I'm not sure that ANSI/ISO C doesn't define the remainder operator for negative values. The draft on http://www.open-std.org/jtc1/sc22/wg14/www/docs/n843.htm says in 6.6.5 [#6] "When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.76) If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.". In other words a%b = a-(a/b)*b - I fail to see why that is undefined for a<0. Jefischer 16:29, 4 December 2005 (UTC)

Because you quoted the C99 draft which uses round towards 0 for a/b. The C89 standard allowed an implementation to implement a/b as round towards 0 or round towards -Inf. TomJF 05:31, 8 February 2006 (UTC)

Years of discussion on comp.lang.c says that you are right :) http://groups.google.co.in/groups/search?q=modulus+negative+comp.lang.c&qt_s=Search —The preceding unsigned comment was added by 203.200.55.101 (talkcontribs) 10:12, 24 April 2006 (UTC).

fortran 95[edit]

In fortran 95 there are two modulo operations mod and modulo. The latter always returns a positive number. —The preceding unsigned comment was added by 203.200.55.101 (talkcontribs) 10:12, 24 April 2006 (UTC).

Pascal[edit]

The article states "Pascal and Algol68 do not satisfy these for negative divisors". Firstly, It would be helpful to give an example of how Pascal/Algol68 deviate from the definition. Secondly, I've checked this for Delphi Pascal, but Delphi seems to follow C, so I conclude it does satisfy the definition. 80.255.245.177 (talk) 11:08, 7 October 2008 (UTC)

Raymond T. Boute of the University of Nijmengen wrote a seminal paper on this called "The Euclidean definition of the functions div and mod" which is also referenced in the Wikipedia article (https://biblio.ugent.be/input/download?func=downloadFile&fileOId=452146). In section 2.2 of this paper, Boute presents proof that Algol-68 and both ISO Pascals are violating the conditions for Euclidean Division and he classifies them as "wrong". — Preceding unsigned comment added by 37.161.59.93 (talk) 14:36, 20 October 2013 (UTC)

Remainder constraint[edit]

The constraint formula "0 <= |r| < n" is wrong when n<0, i think it shuld be "0 <= |r| < |n|" or something like that. --Martin Rizzo 15:20, 19 May 2006 (UTC)

I think the equation that says "a = q + nr" is incorrect; shouldn't it be "a = nq + r"? --thesoffish 01:00, 10 September 2008 (UTC)

Naming[edit]

"Given two numbers, a and n, a modulo n (abbreviated as a mod n) is the remainder, on division of a by n. "
When referring to 'a' or 'n', a name is helpfull. In the paper of Leijen, Daan (December 3, 2001) (see Notes, reference 2) they are described as

  • 'a' dividend
  • 'n' divisor

--217.140.108.2 10:39, 22 November 2006 (UTC)

Since no protest has arisen, the naming scheme has been adopted.

FMod[edit]

Why does FMod redirect to this page? I dont know of the relevance to this article and FMod is a company and computer game Sound Engine. Mloren 05:37, 26 September 2007 (UTC)

A quick Google search reveals that fmod() is a floating-point (not integer) remainder function found in several(?) programming languages. It would be fine to set up a real FMod page for the company and sound engine; just use a template like this one at the very top of that article, like this:
{{for|the fmod function in computer programming languages|modulo operation}}
It will result in a message like this: For the fmod function in computer programming languages, see modulo operation.mjb 06:15, 26 September 2007 (UTC)
I've changed the redirects as described above. I thought that was more likely to be what was intended, and Google returns FMOD the audio thing earlier. Dhollm (talk) 21:05, 5 April 2009 (UTC)

MS Excel[edit]

Since when is Excel a programming language? It's an application that some naive users might think of as a programming language.

--BigDumbDinosaur

It has the ability to have some code written into it, and perform calculations based on that code, thus it has its own unnamed programming language, so people call it excel, for lack of a better name. Black.jeff (talk) 23:58, 25 April 2009 (UTC)

I have no backing evidence for this, but I would suspect that functionality is provided by VBScript or some Windows link libraries. -Rushyo 217.41.21.125 (talk) 11:09, 2 October 2009 (UTC)
It's actually provided by VBA (Visual Basic for Applications), which is present in several Microsoft Office applications -Cedgin (talk) 20:46, 11 May 2012 (UTC)

Floating-point modulo should be added to table[edit]

Currently the table only does integer modulo operators. (In some languages the floating-point modulo operator is the same as the integer modulo operator; whereas in other languages it is different.) For example, in C, the fmod() function is used to perform floating-point modulo (the % operator won't work); but it is not listed in the table. It is useful to know, not only (1) what the floating-point modulo operators are in these languages, but also (2) whether they follow the sign of the divisor or dividend, in the same way it is listed for the integer modulo operators. I am not sure whether the floating-point versions should be added into the table alongside the integer ones (and maybe have some way to indicate which is which); or to have a separate section or table for floating-point operators altogether. --164.67.154.134 (talk) 21:40, 8 May 2009 (UTC)

Assembly language[edit]

I made a long research to use the Modulo operator in Assembly language and the closest I found was the DIV operator however it's not available on the simple educational Assembler PEP8 [1] (French operators instruction Chapitre 7 in http://www.er.uqam.ca/nobel/k20250/Notes_cours.html).

Is there a simpler way of doing a modulo ? Perhaps doing bitwise operations ? --DynV (talk) 19:02, 12 June 2009 (UTC)

x % 2^n == x & (2^n - 1)[edit]

This formula does not work if x is negative in languages where % uses the sign of the dividend. How can the C compilers use it? Do they use it only when they can prove that x is positive or only in earlier revisions than C99? Jaan Vajakas (talk) 13:44, 13 September 2009 (UTC)

Modulo operation expression[edit]

I contributed (A) and the words 'or equivalent, for environments lacking a mod() function'. Another user edited it to look like (B). Could someone explain to my why is (B) preferred over (A). I thought (A) was the more simplified expression, I'm wrong?

(A) (a/n) - int(a/n)

(B) a - n * int(a/n)

--gary84

Expression (A) is incorrect. Try it with a=12, n=5. (A) gives 0.4 (B) gives 2. -- Schapel (talk) 00:35, 18 January 2010 (UTC)
Oops. I thought I typed n*(a/n-int(a/n)) . Ok (B) wins. -- gary84 —Preceding undated comment added 01:22, 19 January 2010 (UTC).
If that's what you typed, (B) is a simplified version of that expression that will work correctly with floating point arithmetic. -- Schapel (talk) 01:28, 19 January 2010 (UTC)
My first time editing a discussion in wikipedia so sorry I don't know the protocol, but my problem with the given expression:
a - (n * int(a/n))
Is that when your'e using a language that does integer division truncation (java, c, etc) then this won't work. For example, -2 mod 5 should be 3, but if your language does integer truncation, you're left with -2 - (5 * 0), or -2. To fix this, we need to be explicit that we need the floor of the division:
a - (n * floor(a/n))
Which would be -2 - (5 * floor(-0.4)) which is -2 - (5 * -1), which is 3 as we expect. What am I missing? —Preceding unsigned comment added by Rjcarr (talkcontribs) 03:49, 6 November 2010 (UTC)

x mod y with x<y yields x[edit]

should also note that "x mod y" where x<y gives x in Squeek VM (SmallTalk) and other environments —Preceding unsigned comment added by 212.251.127.3 (talk) 14:07, 28 March 2011 (UTC)

Operator Precedence in Equivalencies section[edit]

The distributive equivalence ab mod n assumes that the operator mod has a low priority than the multiplication. Is this defined somewhere? I could not find a reference. In doubt, I would suggest adding parenthesis (ab) mod n. Norbert6842 (talk) 13:55, 22 May 2013 (UTC)

Algol-68 and Pascal DO NOT conform to Euclidean Definition[edit]

The article states that languages that follow the Euclidean definition introduced in Raymond T. Boute's seminal paper (which is referenced in the article) are marked with the qualifier "always positive".

First, this is a problematic way to describe conformance with the Euclidean definition, because not every definition that results in a remainder that is always positive actually follows the Euclidean definition. It would be better to use a different qualifier to express conformance to the Euclidean Definition. In fact it would be beneficial to restructure the table to include a coloumn "Definition" that would then have the qualifiers "T-Definition", "F-Definition", "E-Definition" (as per Boute's paper) and "Other".

Second, there is a factual error in that Algol-68 and both ISO Pascal variants are marked "always positive" which the article says denotes conformance with Boute's E-Definition, but in fact in section 2.2 of Boute's paper he specifically picks out Algol-68 and both ISO Pascals as being "wrong" and he presents a mathematical proof why they are wrong for each of them. Of course it is correct to say that the remainder for Algol-68 and ISO Pascal is "always positive". But it is incorrect to define "always positive" an indicator for conformance with Boute's Euclidean definition.

If the table was modified to have a "Definition" coloumn as I suggested two paragraphs further up, then Algol-68 and both ISO Pascals would be classified "Other" because none of them conform to the E-Definition. The coloumn that indicates the sign of the remainder could still be kept. Even then it should better be "always non-negative" instead of "always positive" in order to avoid an argument over whether or not zero is positive or negative.

I'd be happy to edit the article accordingly, but I do not have the time to investigate for all these languages what definition they conform to. So, if I was to add the additional coloumn to the table, most entries would remain empty until others can fill them in. Also, I am not sure what happens to the formatting of the page if the table gets another coloumn, because it may then be too wide. So, should I wait for feedback from others first, or simply edit the table accordingly and see what happens? — Preceding unsigned comment added by 37.161.59.93 (talk) 14:55, 20 October 2013 (UTC)

sometimes called modulus - really?[edit]

I was wondering who it is that sometimes calls it "modulus" instead of "modulo" (except in error of course)?

As it stands the article seems to be propagating and supporting what seems to be (to me at least) an error. AlexFekken (talk) 06:26, 25 January 2014 (UTC)

Misconception of misconceptions[edit]

The section "Common misconceptions" presents two pretty silly issues. In the second, the expression 3-1 mod 5 neither occurs in the formular above nor is it 2. Nonsense. The first is not very useful either. I can hardly imagine that this unintuitive formular could be a frequent misconception. Removing the whole section. Towopedia (talk) 13:28, 10 April 2014 (UTC)

3-1 mod 5 is the modular inverse of 3 modulo 5, and it _is_ 2. It does occur in the formula (b-1 mod n). I would like to point out that the title of this section is ironic. However I agree that the section was poorly written which warranted removal. — Preceding unsigned comment added by 99.240.216.184 (talk) 00:27, 27 June 2014 (UTC)

Bold statement - Is it someone's opinion or a general conclusion?[edit]

"Despite its widespread use, truncated division is shown to be inferior to the other definitions."

I'm not sure if this is a quote from someone, a summary of their opinion, or a general conclusion. It's a rather bold statement. If we're going to have it around, I'd like to have a better sense of its context.

Mdnahas (talk) 16:13, 29 May 2014 (UTC)


It's a quote from citation 7 (Leijen,) which is summarizing citation 6 (Boute, R.) For more context see citation 7's page 8 (p. 134 of original publication.) It's available from biblio.ugent.be. 99.240.216.184 (talk) 01:37, 25 June 2014 (UTC)