Lazarus

Programming => General => Topic started by: uart on February 18, 2020, 05:14:06 am

Title: Do we need a "number theory" compatible version of modulo?
Post by: uart 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.  :)




Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: 440bx 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. :) )
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart 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?

Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: 440bx 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.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart 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.

Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: 440bx 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.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: Thaddy 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.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: Zvoni 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
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: Thaddy on February 18, 2020, 08:44:50 am
Yeah, I just tried. must be a function modulo(const x,y:integer):integer;
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: marcov 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 (https://www.ozonehouse.com/mark/periodic/)

Just define a function for the rare cases you need it.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart 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?
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart 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 (https://www.ozonehouse.com/mark/periodic/)

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.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: marcov 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.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart 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).
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: 440bx 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.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart on February 18, 2020, 03:26:41 pm
I understand what you're saying, what I'm saying is, do (abs(n1) mod 12) and (abs(n2) mod 12).

No, abs definitely doesn't do what I need here. I need for example (-20 mod 12) to be positive 4. The reason the desired result is positive 4 is because that is the smallest positive integer that differs from -20 by only multiples of 12.

If you apply abs then all you get is (abs(-20) mod 12) = (20 mod 12) = 8.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: 440bx on February 18, 2020, 03:43:02 pm
I understand what you're saying, what I'm saying is, do (abs(n1) mod 12) and (abs(n2) mod 12).

No, abs definitely doesn't do what I need here. I need for example (-20 mod 12) to be positive 4. The reason the desired result is positive 4 is because that is the smallest positive integer that differs from -20 by only multiples of 12.

If you apply abs then all you get is (abs(-20) mod 12) = (20 mod 12) = 8.
I missed the point until now. I finally see what you're looking for.  Makes sense.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: SymbolicFrank on February 19, 2020, 03:42:21 pm
Code: Pascal  [Select][+][-]
  1. function ModuloEx(x, y: Integer): Integer;
  2. begin
  3.   Result := abs(x) mod abs(y);
  4.   if abs(x) <> x then Result := abs(y) - Result;
  5. end;
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: Thaddy on February 19, 2020, 04:41:09 pm
That fails tests for arithmetic modulo per wikipedia entries.
It also is branched, I suspect it can be solved without branching. (expand, add and shift left the modulo parameter, NOT tested)
Mod is slow enough as it is....

https://en.wikipedia.org/wiki/Modular_arithmetic see mod 5 examples.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart on February 20, 2020, 02:50:13 pm
Code: Pascal  [Select][+][-]
  1. function ModuloEx(x, y: Integer): Integer;
  2. begin
  3.   Result := abs(x) mod abs(y);
  4.   if abs(x) <> x then Result := abs(y) - Result;
  5. end;

Thanks Frank.
You algorithm nearly works, but it does fail for some cases where the result should be zero. I have fixed that below.

For my current application I'm not really interested in negative values of the second parameter.
However I can confirm that your modulo function (after fixing the one bug) does work correctly and is equivalent to doing modulo(x,abs(y))  for either of my two proposed algorithms. (Those being either the double modulo or the conditional add methods that I outlined previously).

The following three all give the same results for all valid range of parameters.
Code: Pascal  [Select][+][-]
  1. function modulo1(a,b : integer) : integer;    // Frank's algorithm (fixed).
  2. begin
  3.   Result := abs(a) mod abs(b);
  4.   if (a < 0) and (Result<>0) then Result := abs(b) - Result;
  5. end;
  6.  
Code: Pascal  [Select][+][-]
  1. function modulo2(a,b : integer) : integer;    // Conditional add algorithm.
  2. begin
  3.   b:=abs(b);
  4.   Result := a mod b;
  5.   if a<0 then Result := Result + b;
  6. end;
  7.  
Code: Pascal  [Select][+][-]
  1. function modulo3(a,b : integer) : integer;    // Double modulo algorithm.
  2. begin
  3.   b:=abs(b);
  4.   Result := ((a mod b) + b) mod b;
  5. end;
  6.  

Notes.

- As well as the fix, I also modified your code to compare a<0 rather than abs(a)<>a. It's the same thing but I think the first one is a bit more transparent.

- At present my algorithms (modulo2 and modulo3) don't really include the line b:=abs(b) (because I'm not using any negatives in the second parameter), but I just included them here to make it a fair comparison to your algorithm.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: Thaddy on February 21, 2020, 09:18:53 am
Your modulo3 would be my choice since it is branchless. I would write it slightly different, though:
Code: Pascal  [Select][+][-]
  1. {$mode delphi}{$H+}{$I-}
  2. function modulo3(const a,b : integer) : integer;inline;    // Double modulo algorithm.
  3. begin
  4.   Result:=abs(b);
  5.   Result := ((a mod result) + result) mod result;
  6. end;
  7.  
  8. begin
  9.  writeln(Modulo3(-20,12));
  10. end.

Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: ASerge on February 21, 2020, 01:42:30 pm
The following three all give the same results for all valid range of parameters.
Code: Pascal  [Select][+][-]
  1. {$APPTYPE CONSOLE}
  2. {$MODE OBJFPC}
  3.  
  4. uses SysUtils, Math;
  5.  
  6. type
  7.   TModuloFunc = function (const A, B: Integer): Integer;
  8.  
  9. procedure Measure(const Desc: string; Func: TModuloFunc;
  10.   const DataA, DataB: TBoundArray);
  11. const
  12.   CRepeatCount = 10000;
  13. var
  14.   iData, iRep: SizeInt;
  15.   Start, Elapsed: QWord;
  16. begin
  17.   Start := GetTickCount64;
  18.   for iRep := 1 to CRepeatCount do
  19.     for iData := 0 to High(DataA) do
  20.       Func(DataA[iData], DataB[iData]);
  21.   Elapsed := GetTickCount64 - Start;
  22.   Writeln(Desc, ':', Elapsed);
  23. end;
  24.  
  25. function MakeRandomArray: TBoundArray;
  26. const
  27.   CSize = 1000;
  28. var
  29.   i: SizeInt;
  30. begin
  31.   SetLength(Result, CSize);
  32.   for i := 0 to CSize - 1 do
  33.   begin
  34.     Result[i] := RandomRange(-100, 100);
  35.     if Result[i] = 0 then
  36.       Inc(Result[i]);
  37.   end;
  38. end;
  39.  
  40. function Modulo1(const A, B: Integer): Integer;    // Frank's algorithm (fixed).
  41. var
  42.   AbsB: Integer;
  43. begin
  44.   AbsB := Abs(B);
  45.   Result := Abs(A) mod AbsB;
  46.   if A < 0 then
  47.     Result := AbsB - Result;
  48. end;
  49.  
  50. function Modulo2(const A, B: Integer): Integer;    // Conditional add algorithm.
  51. var
  52.   AbsB: Integer;
  53. begin
  54.   AbsB := Abs(B);
  55.   Result := A mod AbsB;
  56.   if A < 0 then
  57.     Inc(Result, AbsB);
  58. end;
  59.  
  60. function Modulo3(const A, B: Integer): Integer;    // Double modulo algorithm.
  61. var
  62.   AbsB: Integer;
  63. begin
  64.   AbsB := Abs(B);
  65.   Result := ((A mod AbsB) + AbsB) mod AbsB;
  66. end;
  67.  
  68. var
  69.   A, B: TBoundArray;
  70. begin
  71.   Randomize;
  72.   A := MakeRandomArray;
  73.   B := MakeRandomArray;
  74.   Measure('1', @Modulo1, A, B);
  75.   Measure('2', @Modulo2, A, B);
  76.   Measure('3', @Modulo3, A, B);
  77.   Readln;
  78. end.
Quote
1:156
2:125
3:218
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart on February 21, 2020, 03:10:45 pm
1:156
2:125
3:218

Thanks ASerge. So if I'm following your code correctly, that means the conditional add version (number 2) is the fastest. Well at least on your particular platform.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: Otto on February 21, 2020, 03:19:45 pm
Maybe these links could help:

https://crypto.stanford.edu/pbc/notes/numbertheory/arith.html
https://en.wikipedia.org/wiki/Modulus_(algebraic_number_theory)
https://en.wikipedia.org/wiki/Modular_arithmetic
https://en.wikipedia.org/wiki/Modulo_operation

Otto.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart on February 21, 2020, 03:21:41 pm
Your modulo3 would be my choice since it is branchless. I would write it slightly different, though:
Code: Pascal  [Select][+][-]
  1. {$mode delphi}{$H+}{$I-}
  2. function modulo3(const a,b : integer) : integer;inline;    // Double modulo algorithm.
  3. begin
  4.   Result:=abs(b);
  5.   Result := ((a mod result) + result) mod result;
  6. end;
  7.  
  8. begin
  9.  writeln(Modulo3(-20,12));
  10. end.

Yes I thought branchless might have been faster too Thaddy, but integer divide can be very a high latency instruction which might turn the tables. No doubt the latency will depend on the exact CPU you're using, but I think in general IDIV is pretty slow.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: 440bx on February 21, 2020, 03:35:21 pm
@Serge,

Nice benchmark, thank you.

ETA: Never mind.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: Otto on February 21, 2020, 04:18:39 pm
In the CPU I have, this inplementation seems slightly faster:

Code: Pascal  [Select][+][-]
  1. function Modulo4(const A, B: Integer): Integer;
  2. var
  3.   AbsB: Integer;
  4. begin  
  5.   if B < 0 then
  6.     AbsB := -B
  7.   else
  8.     AbsB := B;  
  9.   Result := A mod AbsB;
  10.   if A < 0 then
  11.     Inc(Result, AbsB);
  12. end;          
  13.  


Otto.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: ASerge on February 21, 2020, 05:30:59 pm
In the CPU I have, this inplementation seems slightly faster:
But this is a non-working version. For B < 0, the Result is not defined at all.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: FPK on February 21, 2020, 07:57:29 pm
Doesn't {$modeswitch ISOMOD} do what you want?
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: Otto on February 21, 2020, 08:32:35 pm
@Aserge.

You're right Aserge, I made a copy&paste error.

I corrected the code.

Otto.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: uart on February 22, 2020, 03:38:13 am
Doesn't {$modeswitch ISOMOD} do what you want?

Thanks FPK. I wasn't aware of that compiler directive, but you are correct it does force it to do a "number theory compatible" version of mod, albeit for only positive values of the second argument (and a runtime error for negative values of the second argument).

Actually that answers another thing that I was wondering. While researching this earlier I noticed a few people were saying that ISO Pascal's DIV and MOD were broken, with DIV not even being self consistent with MOD.  As in: N <> (N div D) + (N mod D)

I knew that this was not the case with any of the versions of Pascal I've used (mainly Turbo Pascal, Delphi and Free Pascal), with DIV and MOD always working correctly together.  But it appears that in the original ISO Pascal specs this was not the case. They had DIV the same as it currently is, but then they had a number theory compatible MOD that didn't properly mesh with DIV.

So it seems that they messed this up initially, and probably should have had a separate REM (for remainder) operator to do what the current version of MOD does, and kept the original MOD operator as the number theory compatible definition.

Still at this stage, I think I'd rather inline my own version of number theory modulo than to risk breaking other code by redefining the meaning of the existing mod with that directive. Still, thanks for pointing it out to me, it's historically very interesting. :)
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: munair on February 22, 2020, 09:37:37 am
What is addressed here I think is the difference between a modulo operation and a remainder operation:
Code: Pascal  [Select][+][-]
  1. function remx(const a, b: integer): integer;
  2. // remainder
  3. begin
  4.   result := a - b * trunc(a / b);
  5. end;
  6.  
  7. function modx(const a, b: integer): integer;
  8. // modulo
  9. begin
  10.   result := a - b * floor(a / b);
  11. end;

If both a and b are positive then modulo and remainder give the same result. If a and b have different signs then the result is different. Here modx(-8, 12) returns 4, whereas remx(-8, 12) returns -8.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: Thaddy on February 22, 2020, 10:06:15 am
Those involve float operations and will slow down even further. modulo operations are quite expensive. (Also note I introduced a fmod  like mod operator already in 3.2.0 I have to look if that satisfies the rules suggested too. It is in math )
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: munair on February 22, 2020, 11:15:33 am
Those involve float operations and will slow down even further. modulo operations are quite expensive. (Also note I introduced a fmod  like mod operator already in 3.2.0 I have to look if that satisfies the rules suggested too. It is in math )
The purpose of my example is to demonstrate the difference from a mathematical point of view in the clearest manner (trunc vs floor). It is not meant to provide the fastest solution.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: MarkMLl on April 10, 2020, 10:00:50 pm
Doesn't {$modeswitch ISOMOD} do what you want?

What version of FPC implements this?

MarkMLl
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: PascalDragon on April 11, 2020, 02:23:47 pm
Doesn't {$modeswitch ISOMOD} do what you want?

What version of FPC implements this?

3.2 and newer.
Title: Re: Do we need a "number theory" compatible version of modulo?
Post by: MarkMLl on April 11, 2020, 04:13:12 pm
Doesn't {$modeswitch ISOMOD} do what you want?

What version of FPC implements this?

3.2 and newer.

Thanks for that, I was using 3.0.4 and ended up overloading the >< operator so that it behaved the same way as was expected by a Python example I was transcribing... which is probably the first time I've been polite about Python.

MarkMLl
TinyPortal © 2005-2018