Recent

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

uart

  • New Member
  • *
  • Posts: 40
Re: Do we need a "number theory" compatible version of modulo?
« Reply #15 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.
« Last Edit: February 18, 2020, 03:28:25 pm by uart »

440bx

  • Hero Member
  • *****
  • Posts: 1923
Re: Do we need a "number theory" compatible version of modulo?
« Reply #16 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.
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 639
Re: Do we need a "number theory" compatible version of modulo?
« Reply #17 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;

Thaddy

  • Hero Member
  • *****
  • Posts: 10271
Re: Do we need a "number theory" compatible version of modulo?
« Reply #18 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.
« Last Edit: February 19, 2020, 06:09:38 pm by Thaddy »
I am more like donkey than shrek

uart

  • New Member
  • *
  • Posts: 40
Re: Do we need a "number theory" compatible version of modulo?
« Reply #19 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.
« Last Edit: February 20, 2020, 03:17:30 pm by uart »

Thaddy

  • Hero Member
  • *****
  • Posts: 10271
Re: Do we need a "number theory" compatible version of modulo?
« Reply #20 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.

I am more like donkey than shrek

ASerge

  • Hero Member
  • *****
  • Posts: 1632
Re: Do we need a "number theory" compatible version of modulo?
« Reply #21 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

uart

  • New Member
  • *
  • Posts: 40
Re: Do we need a "number theory" compatible version of modulo?
« Reply #22 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.

Otto

  • Full Member
  • ***
  • Posts: 224
« Last Edit: February 21, 2020, 03:21:36 pm by Otto »
Kind regards.

uart

  • New Member
  • *
  • Posts: 40
Re: Do we need a "number theory" compatible version of modulo?
« Reply #24 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.

440bx

  • Hero Member
  • *****
  • Posts: 1923
Re: Do we need a "number theory" compatible version of modulo?
« Reply #25 on: February 21, 2020, 03:35:21 pm »
@Serge,

Nice benchmark, thank you.

ETA: Never mind.
« Last Edit: February 21, 2020, 03:47:45 pm by 440bx »
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

Otto

  • Full Member
  • ***
  • Posts: 224
Re: Do we need a "number theory" compatible version of modulo?
« Reply #26 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.
« Last Edit: February 21, 2020, 08:27:26 pm by Otto »
Kind regards.

ASerge

  • Hero Member
  • *****
  • Posts: 1632
Re: Do we need a "number theory" compatible version of modulo?
« Reply #27 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.

FPK

  • Jr. Member
  • **
  • Posts: 69
Re: Do we need a "number theory" compatible version of modulo?
« Reply #28 on: February 21, 2020, 07:57:29 pm »
Doesn't {$modeswitch ISOMOD} do what you want?

Otto

  • Full Member
  • ***
  • Posts: 224
Re: Do we need a "number theory" compatible version of modulo?
« Reply #29 on: February 21, 2020, 08:32:35 pm »
@Aserge.

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

I corrected the code.

Otto.
Kind regards.

 

TinyPortal © 2005-2018