Recent

Author Topic: Do we need a "number theory" compatible version of modulo?  (Read 5674 times)

uart

  • Jr. Member
  • **
  • Posts: 58
Do we need a "number theory" compatible version of modulo?
« on: February 18, 2020, 05:14:06 am »
Just wondering if anyone has touted the idea of adding the (other common) alternative definition of modulo, which is generally a lot more number theory friendly. Specifically the definition which always gives a non-negative result to "n mod d" whenever d is positive, regardless of whether n is positive or negative.

Obviously I'm not suggesting that mod be redefined, that would break too much code, but maybe a separate operator, for example called "modulo", be added.

Don't misunderstand me and think I'm just making some kind of "Pascal is Wrong" jibe. Actually I like the way Pascal's div works (truncating towards zero rather than the alternative of "flooring" towards negative infinity). And of course once you have defined how div works there is no real choice for how mod should work, if the two are to be self consistent.

And by self consistent, I mean the most important property of divide with remainder. Namely, that with
Q = n div d and R = n mod d, that :
n = Q*d + R

So if I like the way div works, and mod is self consistent, then you may well  ask what am I complaining about? Well basically it's the following property of modulo that is important in number theory, but is not satisfied by the Pascal definition of mod.

In number theory, modulo forms an equivalence class. So for example in modulo base 12 (think for example the hour hand on a clock) then the following are all equivalent :
{ .... -32, -20, -8, 4, 16, 28, 40, ... }
And the normal number theory definition of the modulo operator returns the least positive (or zero) member of that equivalence class, namely 4 in this case.

This leads to a really important property of modulo, that :
n modulo d = (n + k*d) modulo d, for any integer k (positive or negative).

In words this simply means that we can add or subtract any multiple of our modulo base (any multiple of 12 to our hour hand in the above example) and the final result is unchanged.

Unfortunately, Pascal's mod does not satisfy the above property.
For example: 16 mod 12 = 4
however: (16 - 3*12) mod 12 = -8

Anyway, just wondering what people's opinions are on having the alternate modulo available (as a separate key word such as "modulo")?
I'm getting a bit sick of typing  (((n mod d) + d) mod d) just to achieve (n mod d) when I don't know the polarity of n:)




« Last Edit: February 18, 2020, 06:04:53 am by uart »

440bx

  • Hero Member
  • *****
  • Posts: 3944
Re: Do we need a "number theory" compatible version of modulo?
« Reply #1 on: February 18, 2020, 05:44:10 am »
Anyway, just wondering what people's opinions are on having the alternate modulo available (as a separate key word such as "modulo")?
Personally, I like the suggestion and I particularly like how  well you showed that there are good reasons for it (only one example was needed... well exposed. :) )
(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

uart

  • Jr. Member
  • **
  • Posts: 58
Re: Do we need a "number theory" compatible version of modulo?
« Reply #2 on: February 18, 2020, 06:13:29 am »
Thanks 440bx. :)

I'm also looking for input about the best work around for this. I'm looking specifically at the case where "d" is positive but I don't know the sign of "n".

One work around is to use ((n mod d) + d) mod d in place of n mod d. It's a bit unwieldy, but it does always give the desired (lowest non-negative) result.

I was also wondering if a conditional statement might be more efficient?

Something like:

tmp := n mod d;
if tmp < 0 then tmp := tmp + d;


Any ideas on the most efficient work around?


440bx

  • Hero Member
  • *****
  • Posts: 3944
Re: Do we need a "number theory" compatible version of modulo?
« Reply #3 on: February 18, 2020, 06:34:03 am »
Thanks 440bx. :)

Any ideas on the most efficient work around?
You're welcome.  One thing that comes to mind is to code it like this "(n + abs(expression)) mod d", that way the mod is always used with positive numbers ensuring the result will be consistent.

Using the example you provided, gives "(16 + abs(-3 *12)) mod 12 = 4" as desired.
(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

uart

  • Jr. Member
  • **
  • Posts: 58
Re: Do we need a "number theory" compatible version of modulo?
« Reply #4 on: February 18, 2020, 06:54:13 am »
Yeah it's easy when you have fixed (known) numbers.

Let me explain my situation a bit more. The integers "n" come from a complicated series of calculations and inputs, and on any given run I don't know whether that result will be positive or negative.

Integer "d" is somewhat more fixed (on any given run) and is always positive.

The problem is comparing "n1 mod d" with other similar terms like "n2 mod d" to see if they are the same.  They could be the same, but a simple "mod d" comparison might not reveal it (like in the base 12 example where one mod returns 4 and the other returns -8, but they are really the same thing).

Or just think in terms of finding a way to always get the lowest non-negative member of the equivalence class.


440bx

  • Hero Member
  • *****
  • Posts: 3944
Re: Do we need a "number theory" compatible version of modulo?
« Reply #5 on: February 18, 2020, 07:12:16 am »
The problem is comparing "n1 mod d" with other similar terms like "n2 mod d" to see if they are the same.  They could be the same, but a simple "mod d" comparison might not reveal it (like in the base 12 example where one mod returns 4 and the other returns -8, but they are really the same thing).

Or just think in terms of finding a way to always get the lowest non-negative member of the equivalence class.
wouldn't evaluating "abs(n1) mod d" and "abs(n2) mod d" allow you to determine the expressions are equal for any n1 = x * d and n2 = y * d for the same d regardless of whether x, y or both are negative ?  What I'm saying is, I don't see the case where taking the absolute value of the expression wouldn't give you results that you can use to determine the two expressions are equivalent.

Maybe I'm just not "seeing" the problem.
(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: Do we need a "number theory" compatible version of modulo?
« Reply #6 on: February 18, 2020, 08:26:55 am »
Isn't (x mod y)*Sign sufficient to obtain number theory compliant mod? Maybe faster than ABS().
Note almost all programming languages allow for negative modulo.
Alas you can not overload the operator.
« Last Edit: February 18, 2020, 08:41:08 am by Thaddy »
Specialize a type, not a var.

Zvoni

  • Hero Member
  • *****
  • Posts: 2315
Re: Do we need a "number theory" compatible version of modulo?
« Reply #7 on: February 18, 2020, 08:40:57 am »
One work around is to use ((n mod d) + d) mod d in place of n mod d. It's a bit unwieldy, but it does always give the desired (lowest non-negative) result.
If this one always has your desired result, why not write your own operator "modulo"?
Maybe checking if "inlining" is possible for optimization?

EDIT: Thaddy beat me to it.....  :D

EDIT2: Or not....  :P
« Last Edit: February 18, 2020, 08:44:24 am by Zvoni »
One System to rule them all, One Code to find them,
One IDE to bring them all, and to the Framework bind them,
in the Land of Redmond, where the Windows lie
---------------------------------------------------------------------
Code is like a joke: If you have to explain it, it's bad

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: Do we need a "number theory" compatible version of modulo?
« Reply #8 on: February 18, 2020, 08:44:50 am »
Yeah, I just tried. must be a function modulo(const x,y:integer):integer;
Specialize a type, not a var.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11382
  • FPC developer.
Re: Do we need a "number theory" compatible version of modulo?
« Reply #9 on: February 18, 2020, 09:20:48 am »
Why must it be another operator and thus a language extension? We don't want to end up like Perl

Just define a function for the rare cases you need it.

uart

  • Jr. Member
  • **
  • Posts: 58
Re: Do we need a "number theory" compatible version of modulo?
« Reply #10 on: February 18, 2020, 01:28:30 pm »
wouldn't evaluating "abs(n1) mod d" and "abs(n2) mod d" allow you to determine the expressions are equal?

Isn't (x mod y)*Sign sufficient to obtain number theory compliant mod? Maybe faster than ABS()..

There is some misunderstanding about the exact nature of the problem here. It is not simply a matter of the result being the wrong sign, it is also (in general) the wrong magnitude.

Take for example n1=16 and n2=-8, which are both equivalent in modulo base 12. However (n1 mod 12) evaluates to 4 whereas (n2 mod 12) evaluates to -8.  So taking absolute values (or changing the sign) doesn't work. You still end up with one result of 4 and the another of 8, when they should be equal to each other.

The issue is not that (n1 mod 12) and (n2 mod 12) are opposite signs (n1,n2 as per the above example). The issue is that they differ by 12, but in general (if you don't know the signs of n1 and n2) you don't know if the two modulo results (which should be equal) will differ by 0 or will differ by d.

Let me explain the work around I've been using in a bit more detail, it should make the problem clearer. For "d" positive, if "n" is positive then (n mod d) will be +ive and gives me the result that I want. If however "n" is negative then (n mod d)+d gives me the result I want. That is, you may need to add "d" sometimes, but other times not. That's why I need either the second application of mod, or a conditional add.

So mod_value := ((n mod) + d) mod d works properly for both positive and negative "n".

Or alternatively, the two line replacement below also works,
mod_value := n mod d;
if mod_value<0 then mod_value := mod_value + d;


I'm thinking that the conditional add is probably the most efficient?
« Last Edit: February 18, 2020, 01:32:11 pm by uart »

uart

  • Jr. Member
  • **
  • Posts: 58
Re: Do we need a "number theory" compatible version of modulo?
« Reply #11 on: February 18, 2020, 01:51:00 pm »
Why must it be another operator and thus a language extension? We don't want to end up like Perl

Good point Marco, nobody really likes bloat. :) And if we had a second modulo then we'd probably need to have a second divide to partner with it.

Also, just thinking about the way integer division works at the asm level (at least on the x86 and x64 platforms), the native asm instruction IDIV produces quotients and remainders that are exactly consistent with the way Pascal does div and mod.

So even if the alternate (number theory) version was to be implemented as a new operator, there would still be additional overhead in calculating it. So probably no real performance penalty in doing it inline with the conditional add method mentioned above.
« Last Edit: February 18, 2020, 01:53:29 pm by uart »

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11382
  • FPC developer.
Re: Do we need a "number theory" compatible version of modulo?
« Reply #12 on: February 18, 2020, 02:18:16 pm »
Also, just thinking about the way integer division works at the asm level (at least on the x86 and x64 platforms), the native asm instruction IDIV produces quotients and remainders that are exactly consistent with the way Pascal does div and mod.

Use Math.DivMod.

uart

  • Jr. Member
  • **
  • Posts: 58
Re: Do we need a "number theory" compatible version of modulo?
« Reply #13 on: February 18, 2020, 02:48:30 pm »
Use Math.DivMod.

I know that's a convenient way to get them both, but no, in my current code I only need mod.

I was just pointing out that at the hardware level the asm IDIV instruction produces a remainder that is exactly in line with what Pascal's mod returns. So it should be efficient. In that I mean the alternative form of modulo would need to carry extra computational overheads anyway (even if implemented as an inbuilt operator).
« Last Edit: February 18, 2020, 02:57:33 pm by uart »

440bx

  • Hero Member
  • *****
  • Posts: 3944
Re: Do we need a "number theory" compatible version of modulo?
« Reply #14 on: February 18, 2020, 03:17:17 pm »
<snip> Take for example n1=16 and n2=-8

I'm thinking that the conditional add is probably the most efficient?
I understand what you're saying, what I'm saying is, do (abs(n1) mod 12) and (abs(n2) mod 12).  IOW, apply the absolute to the expression whose sign isn't predictable.   I believe that should do it and, I believe that using "abs" is likely to be the "cheapest" way of solving the problem.
(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

 

TinyPortal © 2005-2018