Comment calculer (a fois b) divisée par c en utilisant uniquement les types entier de 32 bits, même si un temps b ne tiendrait pas un tel type
https://stackoverflow.com/questions/4144232
-
30-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Considérez ce qui suit comme une implémentation de référence:
/* 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;
}
Je suis intéressé par une mise en œuvre (en C ou pseudo-code) qui ne nécessite pas un type entier 64 bits.
J'ai commencé à esquisser une mise en œuvre qui décrit comme ceci:
/* 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);
}
Mais la difficulté est de choisir des valeurs pour d1 et d2 qui parviennent à éviter le débordement ((a / d1) * (b / d2) <= UINT32_MAX) et minimiser l'erreur du calcul entier.
Toutes les pensées?
La solution
Je l'ai adapté l'algorithme publié par si-entier--bit types-même-Paul pour ints non signés (en omettant les parties qui traitent des signes). L'algorithme est fondamentalement multiplication Égypte ancienne de a avec la fraction floor(b/c) + (b%c)/c (avec la barre oblique indiquant la division réelle ici).
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;
}
Cet algorithme donnera la réponse exacte tant que cela correspond à 32 bits. Vous pouvez aussi le cas échéant revenir r reste.
Autres conseils
La façon la plus simple serait convertir le résultat Intermediar à 64 bits, mais, selon la valeur de c, vous pouvez utiliser une autre approche:
((a/c)*b + (a%c)*(b/c) + ((a%c)*(b%c))/c
Le seul problème est que le dernier terme pourrait encore déborder pour les grandes valeurs de c. pense toujours à ce sujet ..
Recherche sur www.google.com/codesearch se présente un certain nombre de mises en œuvre, y compris ce wonderfuly évident une. Je aime particulièrement les nombreux commentaires et les noms de variables bien choisis
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;
}
Vous pouvez d'abord diviser un par c et aussi obtenir le rappel de la division, et multiplier le rappel avec b avant de diviser par c. De cette façon, vous pouvez uniquement des données lose dans la dernière division, et vous obtenez le même résultat que de faire la division 64 bits.
Vous pouvez réécrire la formule comme celui-ci (où \ est entier division):
a * b / c =
(a / c) * b =
(a \ c + (a % c) / c) * b =
(a \ c) * b + ((a % c) * b) / c
En faisant en sorte que> = b, vous pouvez utiliser des valeurs plus grandes avant qu'elles débordent:
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;
}
Une autre approche serait de plus en boucle et soustraction au lieu de multiplier et diviser, mais qui est bien sûr beaucoup plus de travail:
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;
}
Si b et c sont les deux constantes, vous pouvez calculer le résultat très simplement en utilisant des fractions égyptiennes.
Par exemple. y = a * 4/99 peut être écrit comme
y = a / 25 + a / 2475
On peut exprimer une fraction en tant que somme des fractions d'Egypte, comme expliqué dans les réponses aux fraction égyptienne en C .
Avoir b et c fixé à l'avance peut sembler un peu d'une restriction, mais cette méthode est beaucoup plus simple que le cas général a répondu par d'autres.
Si b = 3000000000 => Qn = 3000000000, * 2 qn sera débordait. Donc je modifier le code de 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;
}
Je suppose qu'il ya des raisons pour lesquelles vous ne pouvez pas faire
x = a/c;
x = x*b;
sont là? Et peut-être ajouter
y = b/c;
y = y*a;
if ( x != y )
return ERROR_VALUE;
Notez que, puisque vous utilisez entier division, a*b/c et a/c*b pourrait conduire à des valeurs différentes si c est plus grand que a ou b. En outre, si deux a et b sont plus petits que c il ne fonctionnera pas.
