para - Multiplicación campesina rusa

metodo egipcio para multiplicar

Question

Aquí está mi breve implementación de la Multiplicación campesina rusa . ¿Cómo puede ser mejorado?

Restricciones : solo funciona cuando a> 0, b> 0

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

Answer 1

¿Esto es para un concurso de ofuscación de código? Creo que lo puedes hacer mejor. Use nombres de variables engañosas en lugar de nombres sin importancia, para empezar.

Answer 2

Creo que es incompleto y muy difícil de leer. ¿Qué tipo específico de comentarios buscabas?

Answer 3

Creo que es terrible Este es exactamente el mismo código desde el punto de vista del compilador, y (con suerte) mucho más claro

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

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

Y ahora lo he escrito, lo entiendo.

Answer 4

No me parece particularmente terrible, ofuscado o ilegible, como otros lo expresan, y no entiendo a todos esos votos abajo. Dicho esto, así es como lo "mejoraré":

// 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 5

Todavía hay una multiplicación en el ciclo. Si quisiera reducir el costo de las multiplicaciones, podría usar esto en su lugar:

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

Answer 6

p no se inicializa

¿Qué pasa si a es cero?

¿Qué pasa si a es negativo?

Actualización: Veo que ha actualizado la pregunta para abordar los problemas anteriores. Mientras que su código ahora parece funcionar como se indica (excepto por el problema de desbordamiento), aún es menos legible de lo que debería ser.

Answer 7

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 8

Hay una manera realmente fácil de mejorar esto:

p = a * b;

Incluso tiene la ventaja de que aob puede ser menor que 0.

Si observas cómo funciona realmente, verás que es solo la multiplicación manual normal realizada en binario. Tu computadora lo hace internamente de esta manera (1), así que la forma más fácil de usar el método campesino ruso es usar la multiplicación incorporada.

(1) Tal vez tiene un algoritmo más sofocado, pero en principio se puede decir que funciona con este algoritmo

Answer 9

Tantos downvotes. ¡No veo ningún daño que haya causado al publicar esto!

PD: para "aprender" [jugando], está bien codificar de esa manera. ¡Pero profesionalmente no esperaría que codificaras así!

Answer 10

Respuesta sin multiplicación o división:

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

Answer 11

Se puede mejorar agregando espacios en blanco, sangría adecuada y un cuerpo de función adecuado:

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

¿Ver? Ahora está claro cómo se usan las tres partes de la declaración for . Recuerde, los programas están escritos principalmente para ojos humanos. El código ilegible siempre es código incorrecto.

Y ahora, para mi diversión personal, una versión recursiva de la cola:

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