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.
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