Moltiplicazione contadina russa

Question

Ecco la mia breve implementazione di Russian Peasant Multiplication . Come può essere migliorato?

Restrizioni : funziona solo quando a > 0, b > 0

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

Answer 1

Può essere migliorato aggiungendo spazi bianchi, rientro corretto e un corpo di funzione adeguato:

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

Vedi? Ora è chiaro come vengono utilizzate le tre parti della dichiarazione for . Ricorda, i programmi sono scritti principalmente per gli occhi umani. Il codice illeggibile è sempre un codice errato.

E ora, per mio divertimento personale, una versione ricorsiva della coda:

(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

Penso che sia terribile Questo è esattamente lo stesso codice dal punto di vista del compilatore e (si spera) molto più chiaro

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

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

E ora l'ho scritto, lo capisco.

Answer 3

Esiste un modo davvero semplice per migliorare questo:

p = a * b;

Ha persino il vantaggio che aob potrebbe essere inferiore a 0.

Se guardi come funziona davvero, vedrai che è solo la normale moltiplicazione manuale eseguita binaria. Il tuo computer lo fa internamente in questo modo (1), quindi il modo più semplice di usare il metodo contadino russo è usare la moltiplicazione integrata.

(1) Forse ha un algoritmo più sofisticato, ma in linea di principio si può dire che funziona con questo algoritmo

Answer 4

C'è ancora una moltiplicazione nel loop. Se si desidera ridurre il costo delle moltiplicazioni, è possibile utilizzare questo invece:

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

Answer 5

Non lo trovo particolarmente terribile, offuscato o illeggibile, come dicono altri, e non capisco tutti quei voti negativi. Detto questo, ecco come avrei migliorato " esso:

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

Questo è per un concorso di offuscamento del codice? Penso che tu possa fare di meglio. Usa nomi di variabili fuorvianti invece di insignificanti, per cominciare.

Answer 7

p non è inizializzato.

Cosa succede se a è zero?

Cosa succede se a è negativo?

Aggiorna: vedo che hai aggiornato la domanda per risolvere i problemi sopra. Mentre ora il tuo codice sembra funzionare come indicato (ad eccezione del problema di overflow), è ancora meno leggibile di quanto dovrebbe essere.

Answer 8

Penso che sia incompleto e molto difficile da leggere. Quale tipo specifico di feedback stavi cercando?

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

Risposta senza moltiplicazione o divisione:

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