January 16, 2021, 09:25:11 PM

### Author Topic: Euclidean Integer Modulo  (Read 203 times)

#### Scaremonger

• Full Member
• Posts: 111
##### Euclidean Integer Modulo
« on: December 17, 2020, 08:03:21 AM »
Hi,
The BlitzmaxNG modulus expression didn't work as I expected when I converted some code from Python last night.

PYTHON:
Code: [Select]
`print( -1 % 20 )19`
BLITZMAXNG:
Code: [Select]
`Print( -1 Mod 20 )-1`
In Python (and a few other languages I tested); the modulus/modulo operation returns a sequence regardless of the number being positive or negative, but in Javascript, C, BlitzmaxNG etc the function is simply a remainder and returns the sign of the first argument. I didn't test legacy Blitzmax.

In order to reproduce the Euclidean Modulo, I first tried this:
Code: [Select]
`Function emodulo:Int( x:Int, n:Int ) Return (x Mod n + n) Mod nEnd Function`
Although it wasn't too slow; I thought it would be better in c and my first implementation was a little faster. Eventually I did some research and found a nice thread on StackOverflow: This in turn provided me with the following which is about twice as fast:

eucmod.c
Code: [Select]
`/* Euclidean Integer Modulo * https://stackoverflow.com/questions/11714555/euclidean-integer-modulo-in-c */int eucmod(const int a, const int b){    return (a < 0 ? (((a % b) + b) % b) : (a % b));}`
BlitzmaxNG
Code: [Select]
`Import "eucmod.c"Extern Function eucmod:Int( dividend:Int, divisor:Int )EndExternPrint( (-1 ) Mod 20 )Print( eucmod( -1, 20 ) )`
Hope this helps someone else.

#### Henri

• Sr. Member
• Posts: 288
##### Re: Euclidean Integer Modulo
« Reply #1 on: December 17, 2020, 11:56:35 AM »
Hi Scaremonger,

I believe that the speed benefit comes from adding the compare clause before doing the calculation.

Does it have any speed difference if you do that in Bmax only ?

Like:
Code: BlitzMax
1. Function emodulo:Int( x:Int, n:Int )
2.         If x < 0 Then
3.                 Return (x Mod n + n) Mod n
4.         Else
5.                 Return x Mod n
6.         EndIf
7. End Function
8.

-Henri
- Got 01100011 problems, but the bit ain't 00000001

#### Scaremonger

• Full Member
• Posts: 111
##### Re: Euclidean Integer Modulo
« Reply #2 on: December 17, 2020, 03:01:32 PM »
Hi,
I used this to test them and added your variation (using an else):
Code: [Select]
`SuperStrict'Modulo TestImport "eucmod.c"Extern Function eucmod:Int( dividend:Int, divisor:Int )EndExternConst LISTLEN:Int = 5Const REPETITION:Int = 1000000Global start:Int, finish:Intspeedtest( "x mod n ", xmodn,   LISTLEN, REPETITION )speedtest( "emodulo ", emodulo,  LISTLEN, REPETITION )speedtest( "emodulo2", emodulo2, LISTLEN, REPETITION )speedtest( "emodulo3", emodulo2, LISTLEN, REPETITION )speedtest( "eucmod  ", eucmod,   LISTLEN, REPETITION )Function speedtest( descr:String, fn:Int( x:Int, y:Int ), length:Int, qty:Int ) start = MilliSecs() For Local n:Int = -qty To qty Local result:Int = fn( n, length ) Next finish = MilliSecs() Print( descr+": "+(finish-start) )End FunctionFunction xmodn:Int( x:Int, n:Int ) Return (x Mod n )End FunctionFunction emodulo:Int( x:Int, n:Int ) Return (x Mod n + n) Mod nEnd FunctionFunction emodulo2:Int( x:Int, n:Int ) If x>=0 Return x Mod n Return (x Mod n + n) Mod nEnd FunctionFunction emodulo3:Int( x:Int, n:Int ) ' @Henri If x < 0 Then Return (x Mod n + n) Mod n Else Return x Mod n EndIfEnd Function`
The results were high in debug mode, but in release mode the C code was actually slower, so this appears to be the best solution:
Code: [Select]
`Function emod:Int( dividend:Int, divisor:Int ) If dividend>=0 Return dividend Mod divisor Return ( dividend Mod divisor + divisor ) Mod divisorEnd Function`
Si...