Newsgroup: it.comp.lang.c
Titolo: EFFICIENZA

Salve ragazzi, volevo sapere se effettuare la moltiplicazione tra due
numeri con shift e add è più efficiente di quella a*b.
Se invece è più efficiente solo in alcuni casi, quali sono?
Ho letto da qualche parte che se vogliamo moltiplicare due numeri a e
b, inoltre a è un intero abbastanza piccolo, allora la moltiplicazione
con shift e add è più efficiente. E' corretto? perchè?
Inoltre io dovrei implementare questa cosa in C, come posso fare? su
internet trovo implementazioni in assembly... Qualcuno conosce o può
inviarmi l'implementazione in C?
Grazie
Davide

 Inoltre io dovrei implementare questa cosa in C, come posso fare?
L'algoritmo non è difficile.
Luca
-- 
Home: 
http://kronoz.cjb.net
Al termine di un pranzo di nozze mi hanno dato un
amaro alle erbe cosi' schifoso che perfino sull'etichetta
c'era un frate che vomitava.

Se invece è più efficiente solo in alcuni casi, quali sono?
Non si può dire: dipende dall'architettura.

 ha scritto nel messaggio
news:efue23$cqq$1...@dreamland.darkstar.lan...

Il numero delle somme da fare cresce troppo con il valore di 'b'.
Questo algoritmo si migliora facilmente iterando lo stesso
procedimento che hai fatto per calcolare la prima volta 'p'
a tutti i successivi resti 'd'.
Infatti hai posto:
b = 2^p + d          (con d < 2^p naturalmente!)
e
a * b = a * (2^p + d)
cioè
a * (2^p) + a * (d)
a * (2^p) viene fatto con lo shift.
a * d   lo   ottieni facendo d-1 somme, troppe (è in fondo il problema
iniziale!)
Basta applicare iterativamente:
a * d = a * (2^q + x)  e  sommare al precedente con
lo stesso criterio (a << q).
Si passa da un numero di somme sostanzialmente lineare con 'b'
ad un numero logaritmico in 'b'.
Anzi il valore è dato dal numero di bit a '1' di b.
In media ancora il 50% più veloce di log2(b) step.
In sostanza il costo di questo algoritmo è di O(log2(b)) somme/shift
contro O(b) del precedente.
Nota: per velocizzare il calcolo di 'p', che poi è la
posizione del bit più significativo di b, sarebbe opportuno
utilizzare una look-up table.
Cioè si crea una tabella di valori precalcolati ottenendo:
p = look_up_table[b];
Sto assumendo che il valore massimo
per b non sia enorme. Oppure bisogna usare una ricombinazione
di 2 look_up_table per gestire valori grandi.
Naturalmente che tutto questo sia più veloce di un semplice (a * b)
è tutto da dimostrare.
Dipende appunto dall'architettura e anche dal tipo di a,b.
L'algoritmo magari funziona meglio per gli unsigned int
piuttosto che per gli unsigned long.
Probabilmente per convenire davvero penso che alla fine bisogna fare
tutto in assembler e utilizare valori piccoli di b.
--
Giorgio Silvestri
DSP/Embedded/Real Time OS   Software Engineer

 tutto in assembler e utilizare valori piccoli di b.
...su x86 BSR ci casca a fagiolo ;)
Luca
-- 
Home: 
http://kronoz.cjb.net
"Ci sono le balle, le megaballe e le statistiche".
 Mark Twain

 eccessivo.
Infatti lo avevo già detto io!
"Sto assumendo che il valore massimo
per b non sia enorme. Oppure bisogna usare una ricombinazione
di 2 look_up_table per gestire valori grandi."
Le due look_up_table sono ovviamente piccole, sono fatte
apposta :-)



[questo passaggio invece non l'ho capito...
Lo so che sono una bestia :-) ma proprio non ho capito come funziona...
Potresti farmi un esempio?
Questo sistema non è lo stesso usato nei circuiti moltiplicatori?
Grazie mille
Franco 

 Questo sistema non è lo stesso usato nei circuiti moltiplicatori?
Poniamo b = 21
a * b = a * 21
ma 21 = 10101 in binario
il valore di 'p' è dato dalla posizione dell'1 MSB di b
cioè p = 4.
quindi a * b = a * (2^4 + d) = a * 2^4 + a * d     [XXX]
ma sappiamo che a * 2^4 si può fare efficientemente con
lo shift:
a * 2^4 = a << 4
Ora poniamo di aver accumulato in X la somma corrente
che parte da 0.
Attualmente X = a << 4    (cioè X = a * 16)
ma sappiamo da prima [XXX] che a * b = a * 2^p + a * d
e   a * 2^p lo abbiamo già calcolato (è X)
Quindi ci riduciamo a calcolare a * d (manca questo per la somma finale)
d = (10101 - 10000) = 5 = 101 binario (qui 'p' vale 2, cioè il bit a 1 più
significativo)
Ora seguendo lo stesso ragionamento fatto prima
si ha d = 5 = 2^2 + 1.
a * d = a * (2^2+1) = a * 2^2 + a * 1
ma a * 2^2 si fa efficientemente con lo shift ...
cioè a << 2
questo valore lo sommiamo a X
cioè X += a << 2.
Rimane ancora
a * 1 = a * 2^0
quindi a * 1 = a << 0
e sommando a X   si ottiene X  = (a << 4) + (a << 2) + (a << 0) = a * 10101
Cioè itero fino ad avere b = 0
sommando tutti i parziali.
Alla fine in X ho il valore prodotto fatto solo con shift e somme.
Se ti può essere di aiuto, osserva il metodo per calcolare il generico p.
#include <stdio.h>
#include <stdlib.h>
#define BIT_IN_INT 32
/*
 * poniamo a titolo di esempio gli unsigned int a 32 bit effettivi (value
bit, no padding)
 */
static unsigned int fast_mul(unsigned int a,unsigned int b)
{
        unsigned int somma; /* sarebbe la nostra X */
        unsigned int start_mask; /* serve a trovare p in modo efficiente */
        int p;
        somma = 0;
        p = BIT_IN_INT-1;
        start_mask = 1u << p;
        while (b) {
                if (b & start_mask) { /* vedo se il p corrente è corretto
per b*/
                        somma += a << p;
                        b &= ~start_mask;       /* azzero il bit di posto p,
è il resto 'd' */
                }
                --p;
                start_mask >>= 1;
        }
        return somma;
}
int main(void)
{
        printf("%u\n",fast_mul(300,11));
        return 0;
}
Si dovrebbe poter ancora migliorare non iterando per forza su tutti i 32 bit
ma calcolando meglio il p successivo con un metodo look-up-table
che permetterebbe di evitare i bit a 0, questo può essere uno spunto per una
ulteriore ottimizzazione. Credo se ne possono fare altre.


Grazie mille, ho capito ora :-)
L'ho provato e funziona e l'ho anche insegnato alla mia sorellina :-)
Franco 

 > 'a' potrebbe essere una qualche maschera binaria.
A questo si ovvia facilmente aggiungendo un commento ("moltiplicazione per
64") sulla stessa riga dell'istruzione. I commenti servono apposta per
questo.
Se una istruzione č piů efficiente di un'altra, la si puň usare e se non č
chiaro che cosa fa si mette il commento.

 chiaro che cosa fa si mette il commento.
comunque di solito il compilatore riconosce le moltiplicazioni per
potenze di due e ottimizza da solo se pensa se sia il caso.
per esempio un gcc che ho sottomano usa lo shift
al posto della moltiplicazione anche se
gli chiedo di non ottimizzare.
se moltiplico per 1152 (ovvero 2^10+2^7) gia' la versione non
ottimizzata sostituisce la moltiplicazione con 2 shift (uno da 3 e uno da 7)
mentre la versione ottimizzata, fa un solo shift da 7 piu' altre operazioni,
in tutto 3 istruzioni.
Il mio suggerimento, e' che e' inutile cercare di ottimizzare
le singole operazioni (a meno che uno non sia un mago dell'assembler)
perche' di solito il compilatore puo' fare ottimizzazioni
al di la' dell'umano medio, anche perche' non cerchera' di ottimizzare
la singola operazione, ma vedra' le cose da un punto di vista
piu' ad alto livello,(considerando magari l'allocazione dei registri
e l'ordine in cui mettere le operazioni) oltre al fatto
che puo' usare istruzioni di macchina che non hanno un corrispettivo
diretto in C, quindi puo' fare cose apparentemente esoteriche.
L'umano e' meglio se ci concentra sull'algoritmo che sta usando
per risolvere il problema.
ciao,
g.