January 16, 2021, 09:25:11 PM

Author Topic: Euclidean Integer Modulo  (Read 203 times)

Offline Scaremonger

  • Full Member
  • ***
  • Posts: 111
    • ITSpeedway - Ramblings of a geek!
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 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]
/* 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 )
EndExtern

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

Hope this helps someone else.

Follow me at ITSpeedway.net.

Offline 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

Offline Scaremonger

  • Full Member
  • ***
  • Posts: 111
    • ITSpeedway - Ramblings of a geek!
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 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]
Function emod:Int( dividend:Int, divisor:Int )
If dividend>=0 Return dividend Mod divisor
Return ( dividend Mod divisor + divisor ) Mod divisor
End Function

Si...
Follow me at ITSpeedway.net.

Offline TomToad

  • Hero Member
  • *****
  • Posts: 521
Re: Euclidean Integer Modulo
« Reply #3 on: December 19, 2020, 08:32:33 PM »
------------------------------------------------
8 rabbits equals 1 rabbyte.

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal