Producing MOD(x,y) with Arithmetic Operations
Date: 03/04/98 at 16:49:33 From: Steve Lundberg Subject: can the MOD(x,y) function be re-created using basic math? Is there any way to produce the "MOD(dividend,divisor)" spreadsheet function using basic math (i.e., +,-,*,/)? Unlike division ... 200/7 = 28.571428571 ... MOD(x,y) gives the remainder after division: MOD(200,7) = 4 Is there anyway to produce the value 4, given the other numbers, using only basic math? I've gotten this far ... (200/7 - INT(200/7)) * 7 ... but I'm still relying on the INT(n) spreadsheet function, which is the TRUNC(n) function in some spreadsheets. Background: It's in a course on computer spreadsheets that this question came up. I was stumped! Thanks for your help.
Date: 03/05/98 at 18:16:58 From: Doctor Daniel Subject: Re: can the MOD(x,y) function be re-created using basic math? Hi there, You asked about modulo arithmetic, specifically if there is any way to produce the "MOD(dividend,divisor)" spreadsheet function using basic arithmetic operations (i.e., +,-,*,/). The short answer: No. The longer answer: No, because it's actually impossible to do even MOD(n,2) with just these operations. That is, suppose that I want a function that returns 0 on all even numbers and 1 on all odd numbers. Suppose I give you an even easier problem: give me a function that returns 0 on all even numbers and I don't care what on all odd numbers (so long as it's not always zero). Here's a proof that you can't do it with just +-*/. First, hopefully you'll agree that any such function is equivalent to a function of the form f(x) = A(x)/B(x), where A(x) and B(x) are both polynomials in x, that is, something like a + bx + cx^2 + ... + zx^k. So, for example, something like 2x^5 + 4x^4 + 3x^2 + 1 f(x) = ---------------------- x^6 - x^4 + 2x + 41 That's because if it's anything else, say the sum of two fractions, or whatever, you can combine terms using least common denominator, or by multiplying out products. Next, it's clear that the denominator of the function doesn't matter. Why? Well, if it's ever zero on an even number, then we have major problems of the divide-by-zero type, and if it's not, then the numerator is always zero on evens and we-don't-care-what on odd numbers as well. So just let f(x) equal a polynomial (in other words, we can get it with just +-*/). But we know that a polynomial with highest exponent k which is not always zero evaluates to zero on at most k values. That means that, for example, x^2 - 4 is zero on at most 2 values, while x^66 - 54x^32 + 41x^5 - 1 is zero on at most 66 (possibly fewer, but at most 66). This is called the Fundamental Theorem of Algebra, and is not trivial to prove, but it's true. But our polynomial is supposed to be not always zero, but zero on an infinite number of values -- all even numbers! Therefore, there exists no finite-degree polynomial which can be not always zero but zero on all evens. Hence, we can't compute MOD(n,2) with a finite polynomial, since it's even more complicated! Incidentally, if that seemed silly, computer scientists who are concerned with proving what certain models of computers can and can't compute were very excited with a much more complicated version of this sort of argument about 15 years ago, when someone used it to prove something which looked for a while like an approach to the P vs NP problem that is very critical in our area. So it's not as silly as you might think. Thanks for your question ... enjoy! Doctor Daniel, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum