### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: Do we need a "number theory" compatible version of modulo?  (Read 1500 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: 1581
##### 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.
using 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;

• Hero Member
• Posts: 9809
##### 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 »

• Hero Member
• Posts: 9809
##### 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: 1496
##### 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);
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: 178
##### Re: Do we need a "number theory" compatible version of modulo?
« Reply #23 on: February 21, 2020, 03:19:45 pm »
« 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: 1581
##### 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 »
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

#### Otto

• Full Member
• Posts: 178
##### 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: 1496
##### 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: 178
##### 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.