Multiplication de paysans russes

Question

Voici ma courte mise en œuvre de la Multiplication de paysans russes . Comment peut-il être amélioré?

Restrictions : fonctionne uniquement lorsqu'un > 0, b > 0

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

Answer 1

Il peut être amélioré en ajoutant des espaces, une indentation appropriée et un corps de fonction approprié:

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

Voir? Nous voyons maintenant comment les trois parties de la déclaration for sont utilisées. Rappelez-vous, les programmes sont écrits principalement pour les yeux humains. Un code illisible est toujours un mauvais code.

Et maintenant, pour mon amusement personnel, une version récursive de la queue:

(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

je pense que c'est terrible C’est exactement le même code du point de vue du compilateur et (espérons-le) beaucoup plus clair

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

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

Et maintenant je l'ai écrit, je le comprends.

Answer 3

Il existe un moyen très simple d'améliorer ceci:

p = a * b;

Il a même l'avantage que a ou b pourrait être inférieur à 0.

Si vous regardez comment cela fonctionne vraiment, vous verrez que ce n’est que la multiplication manuelle normale effectuée en mode binaire. Votre ordinateur le fait en interne de cette façon (1), le moyen le plus simple d’utiliser la méthode paysanne russe est donc d’utiliser la multiplication intégrée.

(1) Peut-être qu'il a un algorithme plus sophastiqué, mais en principe, vous pouvez dire, cela fonctionne avec cet algorithme

Answer 4

Il y a toujours une multiplication dans la boucle. Si vous souhaitez réduire le coût des multiplications, utilisez plutôt ceci:

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

Answer 5

Je ne le trouve pas particulièrement terrible, obscurci ou illisible, comme le disent d’autres, et je ne comprends pas tous ces votes négatifs. Ceci dit, voici comment je pourrais "améliorer" ç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 );

Answer 6

C’est pour un concours d’obfuscation de code? Je pense que tu peux faire mieux. Utilisez des noms de variable trompeurs au lieu de noms sans signification, pour commencer.

Answer 7

p n'est pas initialisé.

Que se passe-t-il si un est zéro?

Que se passe-t-il si un est négatif?

Mise à jour: je constate que vous avez mis à jour la question afin de résoudre les problèmes ci-dessus. Bien que votre code semble maintenant fonctionner comme indiqué (à l'exception du problème de débordement), il est toujours moins lisible qu'il ne devrait l'être.

Answer 8

Je pense que c'est incomplet et très difficile à lire. Quel type spécifique de commentaires recherchiez-vous?

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

Réponse sans multiplication ni division:

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