come calcolare (a volte b) diviso per c utilizzando solo 32 bit integer tipi anche se una volte b non corrispondesse ad un tale tipo

Question

Si consideri il seguente come implementazione di riferimento:

/* calculates (a * b) / c */
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
    uint64_t x = a;
    x = x * b;
    x = x / c;
    return x;
}

Sono interessato a un'implementazione (in C o pseudo) che non richiede un tipo integer a 64 bit.

Ho iniziato a disegnare un'implementazione che delinea in questo modo:

/* calculates (a * b) / c */
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
    uint32_t d1, d2, d1d2;
    d1 = (1 << 10);
    d2 = (1 << 10);
    d1d2 = (1 << 20); /* d1 * d2 */
    return ((a / d1) * (b /d2)) / (c / d1d2);
}

Ma la difficoltà è scegliere valori per d1 e d2 che riescono a evitare il trabocco ((a / d1) * (b / d2) <= UINT32_MAX) e minimizzare l'errore di tutta calcolo.

Qualche idea?

Answer 1

ho adattato l'algoritmo pubblicato da Paul per unsigned int (omettendo le parti che si occupano di segni). L'algoritmo è fondamentalmente antico moltiplicazione egiziano a con il floor(b/c) + (b%c)/c frazione (con la barra denota divisione reale qui).

uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
    uint32_t q = 0;              // the quotient
    uint32_t r = 0;              // the remainder
    uint32_t qn = b / c;
    uint32_t rn = b % c;
    while(a)
    {
        if (a & 1)
        {
            q += qn;
            r += rn;
            if (r >= c)
            {
                q++;
                r -= c;
            }
        }
        a  >>= 1;
        qn <<= 1;
        rn <<= 1;
        if (rn >= c)
        {
            qn++; 
            rn -= c;
        }
    }
    return q;
}

Questo algoritmo produrrà la risposta esatta finchè si inserisce in 32 bit. Si può opzionalmente anche restituire il r resto.

Answer 2

Il modo più semplice sarebbe convertire il risultato intermediar a 64 bit, ma, a seconda del valore di c, è possibile utilizzare un altro approccio:

((a/c)*b  +  (a%c)*(b/c) + ((a%c)*(b%c))/c

L'unico problema è che l'ultimo termine potrebbe ancora traboccare per grandi valori di c. ancora pensando ..

Answer 3

www.google.com/codesearch gira su un certo numero di implementazioni, tra cui questo wonderfuly ovvio uno. Mi piace soprattutto le osservazioni e nomi di variabili ben scelti

INT32 muldiv(INT32 a, INT32 b, INT32 c)
{ INT32 q=0, r=0, qn, rn;
  int qneg=0, rneg=0;
  if (c==0) c=1;
  if (a<0) { qneg=!qneg; rneg=!rneg; a = -a; }
  if (b<0) { qneg=!qneg; rneg=!rneg; b = -b; }
  if (c<0) { qneg=!qneg;             c = -c; }

  qn = b / c;
  rn = b % c;

  while(a)
  { if (a&1) { q += qn;
               r += rn;
               if(r>=c) { q++; r -= c; }
             }
    a  >>= 1;
    qn <<= 1;
    rn <<= 1;
    if (rn>=c) {qn++; rn -= c; }
  }
  result2 = rneg ? -r : r;
  return qneg ? -q : q;
}

http://www.google.com/codesearch/p?hl=en#HTrPUplLEaU/users/mr/MCPL/mcpl.tgz|gIE-sNMlwIs/MCPL/ mintcode / sysc / mintsys.c & q = MulDiv% 20lang: c

Answer 4

È possibile dividere un primo da c e anche ottenere il promemoria della divisione, e moltiplicare il promemoria con B prima dividendolo per c. In questo modo si perdono solo i dati nella ultima divisione, e si ottiene lo stesso risultato di rendere la divisione a 64 bit.

È possibile riscrivere la formula come questo (dove \ è integer divisione):

a * b / c =
(a / c) * b =
(a \ c + (a % c) / c) * b =
(a \ c) * b + ((a % c) * b) / c

Per fare in modo che a> = b, è possibile utilizzare valori più grandi prima che traboccano:

uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c) {
  uint32_t hi = a > b ? a : b;
  uint32_t lo = a > b ? b : a;
  return (hi / c) * lo + (hi % c) * lo / c;
}

Un altro approccio sarebbe quello di loop di addizione e sottrazione, invece di moltiplicare e dividere, ma che è, naturalmente, un molto più lavoro:

uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c) {
  uint32_t hi = a > b ? a : b;
  uint32_t lo = a > b ? b : a;
  uint32_t sum = 0;
  uint32_t cnt = 0;
  for (uint32_t i = 0; i < hi; i++) {
    sum += lo;
    while (sum >= c) {
      sum -= c;
      cnt++;
    }
  }
  return cnt;
}

Answer 5

Se B e C sono entrambi costanti, è possibile calcolare il risultato in modo molto semplice usando le frazioni egiziane.

Ad esempio. y = a * 4/99 può essere scritta come

y = a / 25 + a / 2475

Si può esprimere qualsiasi frazione come somma di frazioni egiziane, come spiegato nella risposta alle frazione egizia in C .

b Avere ec fissato in anticipo potrebbe sembrare un po 'di una restrizione, ma questo metodo è molto più semplice rispetto al caso generale risposta da altri.

Answer 6

Se b = 3000000000 => Qn = 3000000000, sarà traboccato Qn * 2. Così ho modificare il codice di Sven Marnach.

uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
uint32_t q = 0;              // the quotient
uint32_t r = 0;              // the remainder
uint32_t qn = b / c;
uint32_t rn = b % c;
while (a)
{
    if (a & 1)
    {
        q += qn;
        if (qn >= UINT32_MAX) {
            cout << "CO CO" << endl;
        }
        r += rn;
        if (r >= c)
        {
            q++;
            r -= c;
        }
    }
    a >>= 1;
    qn <<= 1;
    int temp = rn;
    if (rn > INT32_MAX) {
        // rn times 2: overflow
        rn = UINT32_MAX;// rn 
        temp = (temp - INT32_MAX) * 2; // find the compensator mean: rn * 2  = UINT32_MAX + temp
        qn++;
        rn = rn - c + temp;
    }
    else {
        rn <<= 1;
        if (rn >= c)
        {
            qn++;
            rn -= c;
        }
    }


}

//return r;
return q;

}

Answer 7

Suppongo che ci siano motivi non si può fare

x = a/c;
x = x*b;

ci sono? E magari aggiungere

y = b/c;
y = y*a;

if ( x != y )
    return ERROR_VALUE;

Si noti che, dal momento che si sta utilizzando integer divisione, a*b/c e a/c*b potrebbe portare a valori diversi se c è più grande di a o b. Inoltre, se sia e a b sono più piccoli di c non funzionerà.