## Thursday, June 18, 2020

### C# .Net - Fast Modulo solutions, including bit-wise and additive

Expanding on my last post, these are fast possible alternative implementations of modulo in C# .Net.

I added the simple additive modulo operation that adds a variable in a loop until it exceeds the amount. The bit-wise shifting Russian Peasant implementation of modulo is also here.
In C language, Russian Peasant does beat the native mod operand, especially the inline  assembly code version.

However, in C# you be hard pressed to beat the native implementation.

```using System;
using System.Diagnostics;

public class Program
{
public static int ModuloBitShiftRussianPeasant(int i, int j)
{
if (i <= j) //trivial modulo
return (i == j) ? 0 : i;
else if (j==0)
return i;

int x = j;
int halfi = i >> 1;
while (x < halfi)
{
x <<= 1;
}
while (i >= j)
{
if (i >= x)
i -= x;
else
x >>= 1;
}
return i;
}

public static int ModuloDecimalMath(int i, int j)
{
if (i <= j) //trivial modulo
return (i == j) ? 0 : i;
else if (j==0)
return i;

decimal decresult = i/(decimal)j;
//Console.WriteLine("decresult="+decresult.ToString());
//Console.WriteLine("denominator="+(decresult - (int)decresult ).ToString());
//Console.WriteLine("modulo="+((decresult - (int)decresult)*j).ToString());
//modulo=3.999999999999999999999999997 issue!

//decimal modulo = (decresult - (int)decresult)*j;

return (int)(((decresult - (int)decresult)*j)+0.000000000000000000000000003M); //add correction
}

public static int ModuloMathString(int i, int j)
{
if (i <= j) //trivial modulo
return (i == j) ? 0 : i;
else if (j==0)
return i;

string decresult = (i/(decimal)j).ToString();
int idxperiod = decresult.IndexOf('.');
if (idxperiod > -1 )
{
string denominator = decresult.Substring(idxperiod);
//Console.WriteLine("denominator="+Convert.ToDecimal(denominator).ToString());
i = (int)(j*(Convert.ToDecimal(denominator)+0.000000000000000000000000003M));
}
else
i = Convert.ToInt32(decresult);

return i;
}

public static int ModuloMathAdditive(int i, int j)
{
if (i <= j) //trivial modulo
return (i == j) ? 0 : i;
else if (j==0)
return i;

int total = 0;
int y = 0;

for (int x = 0; x < i; x++)
{
//Console.WriteLine("y {0} > {1} ",y,  (j - 1));
if (y > (j - 1))
{
total += y;
y = 0;
//Console.WriteLine("x={0} total={1}",y, total);
}
y += 1;

if ((total + y) >= i) return y;

}

}

public static void Main()
{
int number = 123;
int div = 7;
int mod = 0;
Stopwatch sw = new Stopwatch();
sw.Start();
mod = number % div;
sw.Stop();

Console.WriteLine("{0} % {1} mod={2}",number,div,mod);
Console.WriteLine(sw.ElapsedTicks+" ticks");

sw.Reset();
sw.Start();
mod = ModuloBitShiftRussianPeasant(number, div);
sw.Stop();

Console.WriteLine("ModuloBitShiftRussianPeasant mod="+mod);
Console.WriteLine(sw.ElapsedTicks+" ticks");

sw.Reset();
sw.Start();
mod = ModuloDecimalMath(number, div);
sw.Stop();

Console.WriteLine("ModuloDecimalMath mod="+mod);
Console.WriteLine(sw.ElapsedTicks+" ticks");

sw.Reset();
sw.Start();
mod = ModuloMathString(number, div);
sw.Stop();

Console.WriteLine("ModuloMathString mod="+mod);
Console.WriteLine(sw.ElapsedTicks+" ticks");

sw.Reset();
sw.Start();
sw.Stop();

Console.WriteLine(sw.ElapsedTicks+" ticks");

}
}
```