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;  
   
  }
       
  return total;
  
 }
 
 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(); 
  mod = ModuloMathAdditive(number, div); 
  sw.Stop();
  
  Console.WriteLine("ModuloMathAddative mod="+mod);
  Console.WriteLine(sw.ElapsedTicks+" ticks");
  
  
  
 }
}

No comments:

Post a Comment