Euclidean Integer Modulo

[Scaremonger]

Hi,
The BlitzmaxNG modulus expression didn't work as I expected when I converted some code from Python last night.

PYTHON:

Code Select Expand

print( -1 % 20 )
19

BLITZMAXNG:

Code Select Expand

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 Expand

Function emodulo:Int( x:Int, n:Int )
Return (x Mod n + n) Mod n
End 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 Expand

/* 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 Expand

Import "eucmod.c"
Extern
Function eucmod:Int( dividend:Int, divisor:Int )
EndExtern

Print( (-1 ) Mod 20 )
Print( eucmod( -1, 20 ) )


Hope this helps someone else.

[Henri]

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) Select Expand


Function emodulo:Int( x:Int, n:Int )
If x < 0 Then
Return (x Mod n + n) Mod n
Else
Return x Mod n
EndIf
End Function


-Henri

[Scaremonger]

Hi,
I used this to test them and added your variation (using an else):

Code Select Expand

SuperStrict
'Modulo Test

Import "eucmod.c"
Extern
Function eucmod:Int( dividend:Int, divisor:Int )
EndExtern

Const LISTLEN:Int = 5
Const REPETITION:Int = 1000000

Global start:Int, finish:Int

speedtest( "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 Function

Function xmodn:Int( x:Int, n:Int )
Return (x Mod n )
End Function

Function emodulo:Int( x:Int, n:Int )
Return (x Mod n + n) Mod n
End Function

Function emodulo2:Int( x:Int, n:Int )
If x>=0 Return x Mod n
Return (x Mod n + n) Mod n
End Function

Function emodulo3:Int( x:Int, n:Int ) ' @Henri
If x < 0 Then
Return (x Mod n + n) Mod n
Else
Return x Mod n
EndIf
End 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 Expand

Function emod:Int( dividend:Int, divisor:Int )
If dividend>=0 Return dividend Mod divisor
Return ( dividend Mod divisor + divisor ) Mod divisor
End Function

Si...

[TomToad]

Seen this discussed before.
https://mojolabs.nz/posts.php?topic=98276