Je me demandais quel type de méthode a été utilisé pour multiplier les numéros en C ++. Est-ce la multiplication longue de l'école scolaire traditionnelle? algorithme de Fürer ? toom-cuire ?
Je me demandais parce que je vais avoir besoin de multiplier des nombres extrêmement volumineux et de nécessiter un haut degré d'efficacité. Par conséquent, le parcours scolaire traditionnel long multiplication Donc, quel type de multiplication est-il utile C ++? O (n ^ 2) peut être trop inefficace et j'aurais besoin de recourir à une autre méthode de multiplication.
8 Réponses :
Tout dépend de la bibliothèque et du compilateur utilisé.
en multiplication entier C ++ est géré par la puce. Il n'y a pas d'équivalent de Bignum de Perl dans la langue standard, bien que je sois certaines de telles bibliothèques existent.
À Nitpick: Pas nécessairement. Il est parfaitement possible pour les implémentations d'inclure des types numériques (même int , bien que que devrait être plutôt rare) que l'architecture ciblée ne prend pas en charge et applique plutôt des opérations arithmétiques sur elles comme appelle une bibliothèque d'exécution. Considérons des entiers de 128 bits, ou éventuellement des entiers de 64 bits sur des systèmes 32 bits. En outre, il y avait beaucoup de puces sans unité de point flottante (FPU).
@Delnan: rare, mais pas inexistant: le processeur 8502 8 bits n'a aucune instruction arithmétique 16 bits, le compilateur CC65 C doit donc mettre en œuvre int arithmétique via des séquences d'instructions 8 bits et d'appels de bibliothèque .
Que voulez-vous dire par "nombres extrêmement volumineux"?
C ++, comme la plupart des autres langages de programmation, utilise le matériel de multiplication intégré dans le processeur. Exactement comment cela fonctionne n'est pas spécifié par la langue C ++. Mais pour les entiers normaux et les nombres de points flottants, vous ne pourrez pas écrire quelque chose plus rapidement dans les logiciels.
Les plus gros chiffres pouvant être représentés par les différents types de données peuvent varier selon différentes implémentations, mais certaines valeurs typiques sont 2147483647 pour
Vous semblez manquer plusieurs choses cruciales ici:
Pour obtenir des arithmétiques de Bignum (précision arbitraire), vous devez la mettre en œuvre vous-même ou utiliser une bibliothèque. (tels que GMP ), contrairement à Java, et C # (entre autres), C ++ n'a pas de bibliothèque d'arithmétique de précision arbitraire.
Tous ces algorithmes de fantaisie:
O (n ^ 1.585)
- toom-cuire:
- basé sur FFT:
~ o (n journal (n))
ne s'applique qu'aux arithmétiques de Bignum qui sont implémentés dans les bibliothèques de Bignum. Ce que le processeur utilise pour ses opérations arithmétiques indigènes est quelque peu pertinente car il est
Temps habituellement constant.
Dans tous les cas, je ne vous recommande pas d'essayer de mettre en œuvre une bibliothèque Bignum. Je l'ai déjà fait et c'est assez exigeant (surtout les mathématiques). Donc, vous feriez mieux d'utiliser une bibliothèque.
Jusqu'à ce que vous arriviez à très gros chiffres, la méthode que vous avez apprise en classe supérieure fonctionnera mieux dans la pratique. Bien sûr, vous utilisez une base plus grande que 10. :-) En fonction de vos besoins, 2 ^ 32, 2 ^ 64, ou 10 ^ 9 Faire des bases pratiques (une puissance de 10 est utile d'analyser / imprimer vos numéros dans la base 10 est important d'optimiser et 10 ^ 9 est la plus grande puissance qui convient à 32 bits).
Il est effectué dans du matériel. Pour la même raison, des nombres énormes ne fonctionneront pas. Le plus grand nombre C ++ peut représenter dans du matériel 64 bits est de 18446744073709551616. Si vous avez besoin de numéros plus importants, vous avez besoin d'une bibliothèque de précision arbitraire.
Qu'en est-il des doubles? En outre, la taille exacte de la plupart des types de données est au compilateur. Je crois aussi que certains compilateurs proposent des types d'entier 128 bits.
plaine C ++ utilise des instructions multiples CPU (ou multiplication de l'écolier à l'aide des bitShifts et des ajouts si votre CPU n'a pas une telle instruction.)
Si vous avez besoin de multiplication rapide pour les grands nombres, je vous suggère de regarder GMP ( http://gmplib.org ) et utilisez l'interface C ++ à partir de gmpxx.h
Si vous travaillez avec des nombres volumineux, la multiplication entière standard en C ++ ne fonctionnera plus et vous devez utiliser une bibliothèque fournissant une multiplication de précision arbitraire, comme GMP http://gmplib.org/
En outre, vous ne devriez pas vous inquiéter des performances avant d'écrire votre application (= optimisation prématurée). Ces multiplications seront rapides et très probablement de nombreux autres composants de votre logiciel entraîneront beaucoup plus de ralentissement.
Quelle est la taille de ces chiffres? Même des langues comme Python peuvent faire Écrivez ce que vous voulez réaliser en premier et optimiser ultérieurement si nécessaire. 1e100 * 1e100 avec des entiers de précision arbitraires sur 3 millions de fois une seconde sur un processeur standard. C'est la multiplication à 100 endroits importants en prenant moins d'un millionième de seconde. Pour mettre cela en contexte, il n'y a que 10 ^ 80 atomes dans l'univers observable.
Quelle que soit la puce, ça fait.
Le titre m'a fait penser aux entiers reproduisant :)
@harold d'abord, ils doivent faire quelque chose appelé "Rencontre".