Эффективность времени алгоритма умножения русского крестьянина

Question

С точки зрения эффективности времени, имеет ли значение, умножим ли мы n на m или m на n по алгоритму русского крестьянского умножения ?

Например, при вычислении 26 * 47,похожа ли эффективность времени на вычисления 47 * 26?

Answer 1

unsigned int russianPeasant(unsigned int a, unsigned int b) { 
    int res = 0;  // initialize result 
    // While second number doesn't become 1 
    while (b > 0) 
    { 
         // If second number becomes odd, add the first number to result 
         if (b & 1) 
             res = res + a; 
         // Double the first number and halve the second number 
         a = a << 1; 
         b = b >> 1; 
     } 
     return res; 
}

Алгоритм выходит из цикла while, когда b становится 0. Число выполнений цикла составляет [log2 (b)] + 1 раз.

И сдвиг почти занимает постоянное время (1 ЦПцикл)

Имеет смысл звонить с меньшим значением как b.

Бонус: сравнение скорости

Я написал приведенный выше код и побежал кте же числа 47 и 26 в цикле 10 ** 8 раз.

При a = 26, b = 47 это заняло в среднем 1336852,2 микросекунды.

При a = 47,b = 26, это заняло в среднем 1094454,4 микросекунды.

Интересное примечание:

Хотя, как упоминал @Dillon Davis, должно пройти то же количество итераций, еслиих журналы одинаковы, я обнаружил, что это занимает меньше времени с меньшим числом, как b.

(время в микросекундах)
a = 46, b = 36 - 1204240,6
a = 36, b = 46 - 1295766,8

a = 44, b = 36- 1204266.2
a = 36, b = 44 - 1253821.17.

TLDR: Запуск с меньшим вторым номером (тот, что в цикле while)

Исходный код из: https://www.geeksforgeeks.org/russian-peasant-multiply-two-numbers-using-bitwise-operators/

Answer 2

Зависит от того, как вы реализуете свой русский крестьянский алгоритм.Это может быть:

• a*b быстрее
• b*a быстрее
• без разницы

Я выбираю без разницы , потому что математическое умножение для действительных чисел коммутативно: a*b=b*a и потому, что конечный пользователь при вызове вашей функции не захочет беспокоиться о порядке аргументов

Чтобы это произошло, вынеобходимо настроить ваш код следующим образом:

Let the two given numbers be 'a' and 'b'.
1) If 'b' is greater than 'a' - swap 'a' with 'b'
2) Initialize result 'res' as 0.
3) Do following while 'b' is greater than 0
   a) If 'b' is odd, add 'a' to 'res'
   b) Double 'a' and halve 'b'
4) Return 'res'.

Этот код будет иметь сложность

O (log₂ (min (a, b)))

Answer 3

Поскольку алгоритм выполняет floor(log2(k)) итераций для множителя (первого числа) k, время выполнения определенно зависит от порядка.Если n и m лежат между одними и теми же двумя последовательными степенями двух, им потребуется одинаковое количество итераций для завершения.В противном случае всегда ставьте меньшее число первым, чтобы минимизировать время выполнения.