Comment faire pour éviter tout débordement dans l’expr. A * B - C * D

Question

J’ai besoin de calculer une expression qui ressemble à : , où sont leurs types : chaque nombre peut être très gros (ne pas déborder son type). Tandis que pourrait faire déborder, à la même expression de temps peut être vraiment petit. Comment puis-je calculer il correctement ?

Par exemple : , où et n - un nombre naturel.

Answer 1

Cela semble trop trivial, que je suppose. Mais `` est celui qui pourrait déborder.

Vous pourriez faire ce qui suit, sans perte de précision

Cette décomposition peut être fait plus loin.
Comme l’a souligné @Gian, soins pourraient devoir être pris pendant l’opération de soustraction si le type n’est pas signé long.

---

Par exemple, avec le cas que vous avez dans la question, il faut juste une itération,

Answer 2

La plus simple et la plus générale de la solution est d'utiliser une représentation qui ne peut pas de dépassement, soit en utilisant un entier long bibliothèque (par ex. http://gmplib.org/) ou représentant à l'aide d'une structure ou un tableau et de mettre en œuvre une sorte de longue multiplication (c'est à dire en séparant chaque nombre à deux 32bit moitiés et en effectuant la multiplication comme ci-dessous:

(R1 + R2 * 2^32 + R3 * 2^64 + R4 * 2^96) = R = A*B = (A1 + A2 * 2^32) * (B1 + B2 * 2^32) 
R1 = (A1*B1) % 2^32
R2 = ((A1*B1) / 2^32 + (A1*B2) % 2^32 + (A2*B1) % 2^32) % 2^32
R3 = (((A1*B1) / 2^32 + (A1*B2) % 2^32 + (A2*B1) % 2^32) / 2^32 + (A1*B2) / 2^32 + (A2*B1) / 2^32 + (A2*B2) % 2^32) %2^32
R4 = ((((A1*B1) / 2^32 + (A1*B2) % 2^32 + (A2*B1) % 2^32) / 2^32 + (A1*B2) / 2^32 + (A2*B1) / 2^32 + (A2*B2) % 2^32) / 2^32) + (A2*B2) / 2^32

En supposant que le résultat final correspond en 64 bits, vous avez réellement n'avez pas vraiment besoin de plus de bits de R3 et aucun de R4

Answer 3

Notez que ce n'est pas la norme, car il s'appuie sur wrap-around signé de dépassement de capacité. (GCC a les drapeaux de compilation qui permettent à ce sujet).

Mais si vous venez de faire tous les calculs en long long, le résultat de l'application de la formule directement:
(A * B - C * D) seront exacts tant que le bon résultat s'inscrit dans un long long.

---

Voici un travail qui ne repose que sur la mise en œuvre définies par le comportement de casting entier non signé entier signé. Mais ce peut être prévu pour fonctionner sur presque tous les systèmes d'aujourd'hui.

(long long)((unsigned long long)A * B - (unsigned long long)C * D)

Ce qui jette les entrées unsigned long long où le dépassement de comportement est garanti pour être wrap-around par la norme. Casting de retour d'un entier signé à la fin est la mise en œuvre définies par le cadre, mais les travaux sur presque tous les environnements d'aujourd'hui.

---

Si vous avez besoin de plus pédant solution, je pense que vous devez utiliser le "long de l'arithmétique"

Answer 4

Cela devrait fonctionner (je pense) :

Voici mon calcul :

Answer 5

Vous pourriez envisager de calcul d'un plus grand facteur commun pour toutes vos valeurs, puis en les divisant par le facteur avant de faire vos opérations arithmétiques, puis en multipliant à nouveau. Cela suppose qu'un tel élément existe, cependant (par exemple, si A, B, C et D se trouvent être relativement premier, ils n'ont pas un facteur commun).

De même, vous pourriez envisager de travailler sur le journal des échelles, mais cela va être un peu effrayant, sous réserve de la précision numérique.