Остаток от деления без % в C#. Анализ алгоритмов.

Итак, на собеседовании по C# время от времени попадается задача нахождения остатка от деления (число R) целочисленных положительных чисел M и N без применения оператора %;

Алгоритмы

Первое, что приходит в голову, это следующая формула:

    R = M-M/N*N

Второе, что приходит в голову, это стандартная функция в лоб:

i = 0;
do {
i++;
r = m-n*i;

} while (r>=n)
return n;

Третье. предыдущий алгоритм можно ускорить, путем удвоения удвоения. Назовем это интеллектуальным алгоритмом. Мы удваиваем i, и если остаток будет отрицательный, то мы возвращаемся к предыдущему шагу, но с учетом достигнутого результата. И начинаем все заново.

i = 1;
k = 0;


while (true)
{ r = m - (k + i) * n;

if (r >= 0 && r < n)
{
return r;
}

if (r > 0)
{
i *= 2;
}
else
{
k += (i / 2);
i = 1;
}
}

Исходные коды методов для "стандартного" и "интеллектуального" алгоритмов:

Стандартный

        static int StdReminder(int m, int n)
        {
            if (m < n)
            {
                return m;
            }

            var i = 0;
            var r = 0;
            do 
            {
                i++;
                r = m - i * n;
            } while (r >= n)
            return r;
        }

Интеллектуальный

        static int IntelReminder(int m, int n)
        {

            if (m < n)
            {
                return m;
            }

            var i = 1;
            var k = 0;


            while (true)
            {
                var r = m - (k + i) * n;

                if (r >= 0 && r < n)
                {
                    return r;
                }

                if (r > 0)
                {
                    i *= 2;
                }
                else
                {
                    k += (i / 2);
                    i = 1;
                }
            }

       }

Код для тестирования времени выполнения:

        static void Main(string[] args)
        {
            var rnd = new Random();

            var m = rnd.Next(3, 100000000);
            var n = rnd.Next(1,  19);

            var sw = Stopwatch.StartNew();
            var r = m % n;
            sw.Stop();
            Console.Write("Operator M % N:     ");
            Console.WriteLine(m + " % " + n + " = " + r + "; Time: " + sw.Elapsed.ToString());

            sw = Stopwatch.StartNew();
            r = m - m/n*n;
            sw.Stop();
            Console.Write("Operator M - M/N*N: ");
            Console.WriteLine(m + " % " + n + " = " + r + "; Time: " + sw.Elapsed.ToString());


            sw = Stopwatch.StartNew();
            r = StdReminder(m, n);
            sw.Stop();
            Console.Write("Standard Func:      ");
            Console.WriteLine(m + " % " + n + " = " + r + "; Time: " + sw.Elapsed.ToString());


            sw = Stopwatch.StartNew();
            r = IntelReminder(m, n);
            sw.Stop();
            Console.Write("Intellectual Func:  ");
            Console.WriteLine(m + " % " + n + " = " + r + "; Time: " + sw.Elapsed.ToString());

            Console.ReadKey();
        }

Анализ результатов

Вот, что у меня получилось в консоли

Operator M % N: 17485844 % 13 = 12; Time: 00:00:00.0000009
Operator M - M/N*N: 17485844 % 13 = 12; Time: 00:00:00.0000003
Standard Func: 17485844 % 13 = 12; Time: 00:00:00.0037792
Intellectual Func: 17485844 % 13 = 12; Time: 00:00:00.0001679

Выводы:

- Самым быстрым оказался алгоритм M-M/N*N. Он работает в три раза быстрее, чем стандартный оператор %;
- Самый худший - это "стандартный" алгоритм, он дает существенно большее время, чем все прочие.
- "Интеллектуальный" алгоритм работает примерно в 22 раза быстрее, чем "стандартный" и в 560 раз медленнее, чем формула M - M/N*N.