A mathematical formula for p mod q

[s0ft]

What would be an expression for the modulo operation based only on basic arithmetic i.e. addition, subtraction, multiplication and division?
For example, if I would like to define 7 mod 3 using only the basic arithmetic operations, how would I write a function for it in a programming language?
Of course p and q are integers.

 

[mfb]

There is no way to write (a mod b) as a general formula with just addition, subtraction, multiplication and division, without any tools like loops (programming) or mathematical logic.

To write a function, consider 7 mod 3, 4 mod 3 and 1 mod 3. Which one is easy to evaluate? Can you transform the others into this?

 

[s0ft]

Thanks. I was suspecting that was the case.

 

[s0ft]

I'd heard some reputed mathematician had made an attempt to "rigorize" mathematics which I think is to be able to do maths without having to use one's conscience or judgement. So the modulo doesn't fall in that category I guess?

 

[Office_Shredder]

No, p mod q is something that can be computed. I think you're confused by what you heard (or the person saying it was confused as to what they were saying)- math has been rigorous for quite a long time now. p mod q is rigorously defined and can be rigorously calculated.

If you wanted to write a program to calculate this you could do so recursively like this:
mod(p,q)
// returns a number between 0 and q-1

if p < 0
return mod(p+q,q)
elseif p>q-1
return mod(p-q,q)
else
return p
end

It's a good exercise to prove that this program is correct (try a couple examples if you're not sure what's going on - what does it do when I plug in mod(10,3)?). You can also do the calculation in one shot if you're willing to work with non-integers

mod(p,q)
remainder = p/q-floor(p/q)
return round(remainder*q)
end

This version really just obfuscates the fact that division is defined by repeatedly subtracting (actually it's probably not done exactly like this in modern processors but the point that division is hard to do still stands)

 

[s0ft]

Thanks for your help but I didn't mean achieving it with a computer program using conditional statements. Of course life would be easy if that was allowed. Conditional judgements are acts of choosing and destroy rigor, don't they?
See, like the floor() function you used, you don't get something like that in pure rigorous mathematics, do you?

 

[Borek]

Floor function is rigorously defined: http://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Definition_and_properties

 

[rcgldr]

The floor function effectively restricts the result of division to be an integer. To get the proper sign for negative numbers you'd have to define integer division to round down towards -∞, so that (+7) / (+3) or (-7) / (-3) = 2 and (+7) / (-3) or (-7) / (+3) = -3, so that the result of p mod q is zero or has the same sign as q.

Using integer division as defined above, then p mod q = p - (p/q)*q.

7 mod 3 = 7 - (7/3)*3 = 7 - 6 = 1
7 mod -3 = 7 - (7/-3)*-3 = 7 - 9 = -2
-7 mod 3 = -7 - (-7/3)*3 = -7 + 9 = 2
-7 mod -3 = -7 - (-7/-3)*-3 = -7 + 6 = -1

 

[Office_Shredder]

Conditional judgements are acts of choosing and destroy rigor, don't they?

What do you think the definition of rigor is?

See, like the floor() function you used, you don't get something like that in pure rigorous mathematics, do you?

You definitely do.

Rigor is just making sure that every statement made is a true. You can define functions however you want - your choice of definition doesn't change whether you are being rigorous or not

 

[s0ft]

Maybe I used the wrong term 'rigor'.
What I wanted to say was : using nothing more than a general universal single rule or function, here, for the modulo operation, exactly as mfb got me.

 

[rcgldr]

Maybe I used the wrong term 'rigor'. What I wanted to say was : using nothing more than a general universal single rule or function, here, for the modulo operation, exactly as mfb got me.

All that is needed is a redefinition of division so that division only produces integers (rounded downwards towards -∞). Note that integer division on most processors rounds towards 0 instead of -∞, so a post division correction step would be needed.

 

[mfb]

(a mod b) is the unique natural number x with $0 \leq x < b$ such that there exists a $k \in \mathbb{Z}$ with (x-a)=kb.

 

[s0ft]

So we can only define it as another function, requiring us to think what 'k' is going to be. There is no escaping from 'thinking' what it is going to be. Alright.
Thank you.

 

[rcgldr]

modulo ... So we can only define it as another function, requiring us to think what 'k' is going to be.

The normal definition for modulo is the remainder after performing integer division, so the only function that needs to be defined is the integer division used for the modulo function.

Wiki article:

http://en.wikipedia.org/wiki/Modulo_operation