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

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;
}