Русское Крестьянское Умножение

Question

Вот моя короткая реализация Русское Крестьянское Умножение . Как это можно улучшить?

Ограничения : работает только при a> 0, b> 0

for(p=0;p+=(a&1)*b,a!=1;a>>=1,b<<=1);

Answer 1

Его можно улучшить, добавив пробел, правильный отступ и правильное тело функции:

int peasant_mult (int a, int b) {
  for (p = 0;
       p += (a & 1) * b, a != 1;
       a /= 2, b *= 2);
  return p;}

См? Теперь понятно, как используются три части декларации for. Помните, программы написаны в основном для человеческих глаз. Нечитаемый код всегда плохой код.

А теперь, для моего личного удовольствия, хвостовая рекурсивная версия:

(defun peasant-mult (a b &optional (sum 0))
  "returns the product of a and b,
   achieved by peasant multiplication."
  (if (= a 1)
      (+ b sum)
      (peasant-mult (floor (/ a 2))
                    (* b 2)
                    (+ sum (* b (logand a 1))))))

Answer 2

Я думаю, что это ужасно Это точно такой же код с точки зрения компилятора, и (надеюсь) намного понятнее

int sum = 0;
while(1)
{
    sum += (a & 1) * b;
    if(a == 1)
       break;

    a = a / 2;
    b = b * 2;
}

А теперь я это написал, я понимаю.

Answer 3

Существует действительно простой способ улучшить это:

p = a * b;

Он даже имеет преимущество в том, что a или b могут быть меньше 0.

Если вы посмотрите, как это действительно работает, вы увидите, что это просто обычное ручное умножение, выполняемое двоично. Ваш компьютер делает это внутренне таким образом (1), поэтому самый простой способ использовать метод русского крестьянина - использовать встроенное умножение.

(1) Возможно, у него более сложный алгоритм, но в принципе можно сказать, что он работает с этим алгоритмом

Answer 4

В цикле все еще есть умножение. Если вы хотите уменьшить стоимость умножения, вы можете использовать это вместо:

for(p=0;p+=(-(a&1))&b,a!=1;a>>=1,b<<=1);

Answer 5

Я не нахожу это особенно ужасным, запутанным или нечитаемым, как говорят другие, и я не понимаю всех этих отрицательных голосов Тем не менее, вот как я бы «улучшить» это:

// Russian Peasant Multiplication ( p <- a*b, only works when a>0, b>0 )
// See http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication
for( p=0; p+=(a&1)*b, a!=1; a>>=1,b<<=1 );

Answer 6

Это для конкурса обфускации кода? Я думаю, что вы можете сделать лучше. Для начала используйте вводящие в заблуждение имена переменных вместо бессмысленных.

Answer 7

p не инициализировано.

Что произойдет, если a равно нулю?

Что будет, если a отрицательно?

Обновление: Я вижу, что вы обновили вопрос для решения вышеуказанных проблем. Хотя ваш код теперь работает как указано (за исключением проблемы переполнения), он все равно менее читабелен, чем должен быть.

Answer 8

Я думаю, что это неполно, и очень трудно читать. Какую конкретную обратную связь вы искали?

Answer 9

int RussianPeasant(int a, int b)
{
    // sum = a * b
    int sum = 0;
    while (a != 0)
    {
        if ((a & 1) != 0)
            sum += b;
        b <<= 1;
        a >>= 1;
    }
    return sum;
}

Answer 10

Ответ без умножения или деления:

function RPM(int a, int b){
    int rtn;
    for(rtn=0;rtn+=(a&1)*b,a!=1;a>>=1,b<<=1);
    return rtn;
}