俄罗斯农民增殖

这是我对俄罗斯农民增殖的简短实施.怎么改进？

限制:仅在> 0,b> 0时有效

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

Svante.. 55

它可以通过添加空格,适当的缩进和适当的函数体来改进:

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

我喜欢你如何缩进C代码Lisp风格:) (5认同)

---

Airsource Lt.. 20

我认为这很糟糕这与编译器的观点完全相同,并且(希望)更加清晰

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

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

现在我把它写出来了,我明白了.

1> Svante..：

---

它可以通过添加空格,适当的缩进和适当的函数体来改进:

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

---

我喜欢你如何缩进C代码Lisp风格:)

2> Airsource Lt..：

---

我认为这很糟糕这与编译器的观点完全相同,并且(希望)更加清晰

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

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

现在我把它写出来了,我明白了.

---

弗拉德 - 我也可以读英文,但这并不意味着我更喜欢英文.

---

我希望我永远不必与你一起编写代码.我不明白为什么有人会采取类似上述的东西并产生你所拥有的东西,除非他们在混淆的C竞赛项目中进行了半场尝试.:|

---

比特移位比乘法或除法快得多但是,如果可能的话,任何体面的编译器都会将常数乘法优化为一组位移.我遇到的唯一编译器不是IAR H8编译器.我怀疑这不是目标平台.

3> flolo..：

---

有一种非常简单的方法可以改善这种情况:

p = a * b;

它甚至具有a或b可以小于0的优点.

如果你看它是如何工作的,你会发现,它只是正常的手动乘法执行二进制.你的计算机以这种方式进行内核(1),因此使用俄罗斯农民方法的最简单方法是使用内置乘法.

(1)也许它有一个更复杂的算法,但原则上你可以说,它适用于这个算法

4> Markus Jarde..：

---

循环中仍然存在乘法.如果您想降低乘法的成本,可以改用:

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

5> Federico A. ..：

---

我没有发现它特别可怕,混淆或不可读,正如其他人所说的那样,而且我不理解所有那些事.这就是说,这就是我如何"改进"它:

// 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 );