Je fais des problèmes d'Euler du projet et la plupart du temps, les calculs impliquent des nombres importants au-delà de INT, de flotter, de Double, etc.
Premièrement, je sais que je devrais rechercher des moyens de calcul plus efficaces afin d'éviter le problème de nombre élevé. j'ai entendu parler des bibliothèques de Bignum.
6 Réponses :
Voici un module Bignum agréable et simple pour C. Vous pouvez en apprendre des idées. Le code C n'est pas la plus haute qualité, mais l'algorithme est bien implémenté et assez courant.
Pour des trucs plus avancés, recherchez GMP.
Vous devez stocker les gros chiffres dans une base que votre ordinateur peut facilement gérer avec ses types natales, puis stocker les chiffres dans une matrice de longueur variable. Je suggérerais que, pour la simplicité, vous commencez en stockant les chiffres dans la base 10, juste pour faire comprendre comment faire cela. Cela facilitera beaucoup plus facilement le débogage.
Une fois que vous avez une classe pouvant stocker les chiffres dans ce formulaire, il suffit de mettre en œuvre les opérations ajoutez, soustrayez, multipliez, etc. sur cette classe. Chaque opération devra itériter sur des chiffres de ses opérandes et les combiner, faire attention à porter correctement pour que vos chiffres ne soient jamais plus grands que la base. L'ajout et la soustraction sont simples. La multiplication nécessite un peu plus de travail car l'algorithme naïf nécessite des boucles imbriquées. Ensuite, une fois que vous avez travaillé, vous pouvez essayer de mettre en œuvre l'exponciation de manière efficace (par exemple, la querelle répétée).
Si vous envisagez d'écrire un Mise en œuvre de Bignum sérieux , la base 10 ne le coupera pas. C'est un gaspillage de mémoire et ce sera lent. Vous devez choisir une base naturelle pour l'ordinateur, telle que 256 ou la taille de mot (2 ** 32). Cependant, cela rendra des opérations simples plus difficiles car vous obtiendrez des débordements si vous ajoutez naïve deux chiffres. Vous devrez donc vous gérer très soigneusement.
Habituellement, vous choisiriez une base la moitié du plus grand type représentable pour qu'il n'y ait pas de débordements. Par exemple, dans le moderne C, vous choisiriez uint32_t et faire tout le chiffre arithmétique dans uint64_t . Et n'oubliez pas: faire le type de chiffre non signé de sorte qu'il n'y ait pas de surprises.
En fait, la base 10 est totalement adéquate. Tout dépend de vos besoins. Si la vitesse est primordiale, la convolution est un excellent moyen de faire une multiplication, si vous avez un convolver rapide. Et la convolution déborde si vous utilisez une base importante.
C'est la meilleure réponse, car c'est la seule vraie réponse à la question posée.
Un moyen simple est de penser au nombre comme représentation de chaîne dans la base b. Supposons que B = 10, une simple opération arithmétique simple, comme l'ajout sur deux telles chaînes puisse être effectuée à l'aide de la même méthode que nous utilisons lors de l'ajout de chiffres par stylo et papier. Il en va de même pour d'autres opérations simples. Pour de meilleurs résultats, vous pouvez prendre une base plus grande.
Une simple implémentation de Bignum comme celle-là devrait être suffisante pour la plupart des problèmes d'Euler de projet (probablement tous, mais je n'ai pas résolu beaucoup à Euler, il ne peut pas être sûr), mais il existe des moyens d'utiliser beaucoup d'algorithmes beaucoup plus rapides pour les opérations telles que en tant que multiplication et division / mod.
Bien que je recommande de rédiger votre propre Bignum pour la pratique, si vous êtes vraiment bloqué, vous pouvez prendre des idées du code des bibliothèques de Bigint déjà implémentées. Pour une mise en œuvre sérieuse, quelque chose comme GMP est le choix évident. Mais vous pouvez également trouver de petites grossications codées par d'autres personnes lors de la résolution de problèmes de pratique similaires en ligne (par exemple, BIGINT.CPP < / a>).
Si vous voulez une belle version C ++ (je sais, vous avez dit c, mais c'est un code vraiment intéressant), jetez un coup d'œil aux internes de CGAL: http://www.cgal.org/
Si vous essayez des problèmes d'Euler du projet d'élargir votre expérience avec C, c'est parfaitement amende, il suffit de comprendre cette expérience ne s'applique pas nécessairement à des projets de longue durée et réels que vous pouvez travailler. sur.
Pour ce type de problème court, ces langues couramment décrites comme des "langages de script" fonctionneront mieux, plus rapidement (dans le temps de développement) et plus facilement. Essayez Python, il reste près de C à bien des égards, y compris une API C, et sur les différentes "langues de script" populaires est peut-être celle pour laquelle vous trouverez le plus d'utilisation conjointement avec C Projects.
Cela peut devenir une réponse impopulaire, mais ce n'est pas un rant-plus, je n'aime vraiment que c / C ++ souvent - et il y a une réponse explicite ici à votre problème: "N'utilisez pas de C", avec Votre solution de choix définitive en fonction de la variante que vous choisissez. Encore une fois cueillette sur python, les entiers n'ont pas une limite supérieure (note ci-dessous), et j'utilise ceci pour coder naturellement les réponses aux problèmes d'Euler du projet, où dans d'autres langues, je dois utiliser une bibliothèque de numéros alternatifs douloureuse-par-comparaison.
( les entiers python: Il existe deux types entier en 2.x, 'int' et "long" (qui ont été complètement unifiés en 3.x). La conversion entre eux est pratiquement transparente et "long" permet des valeurs arbitrairement importantes, au lieu de simplement être un type "INT" plus important que c est long.)
Je ne suis pas en désaccord avec ce que vous avez à dire, mais l'OP veut apprendre à mettre en œuvre des grossications.
Et je ne dis pas qu'il ne devrait pas apprendre (à un moment donné) comment ils sont mis en œuvre soit (plus d'autres réponses couvrent que pour lui, aucun sens ne le répète). Mais, dans le contexte de la question, la rédaction de sa propre bibliothèque de Bigint n'est même pas une solution appropriée, beaucoup moins un candidat pour un bon.
Ceci est un peu ancien, mais il mérite A -1. C'est comme répondre à la question "Je possède un vélo et je veux ajouter un clignoteur, pouvez-vous aider?" Avec "un vélo?!? Savez-vous à quel point une voiture est une voiture plus efficace! Il a même construit son support en flasher. Évidemment, vous ne comprenez pas le transport." Parfois, il vaut juste la peine de répondre à une question spécifique avec une réponse qui convient à cette question.
Cela ne devrait pas être la première réponse, cela ne répond pas du tout à la question.
Moins 1 pour ne pas répondre à la question mais partager simplement l'opinion d'une personne.
Une bibliothèque de Bignum populaire pour C / C ++ est le bibliothèque Bignum GNU MP . Je l'ai utilisé pour plusieurs problèmes d'Euler de projet, mais il reste que C n'est pas une langue très appropriée pour les problèmes d'Euler. Si la performance était plus importante, C aurait davantage à donner, mais vous êtes maintenant beaucoup mieux à utiliser une langue construite dans le soutien de Bignum, telle que Ruby (il y a beaucoup d'autres).
Ce qui est important dans le projet Euler est ce que vous choisissez de faire important. J'ai fait un tas de problèmes lorsque j'apprendais C ++ et mon objectif n'était pas de résoudre chacun chacun en 2 minutes, mais de résoudre tous ceux que j'avais fait dans 2 minutes au total ;-)
Écrire une bibliothèque de gros numéros va être extrêmement difficile et orientée
Je vous suggère d'utiliser un existant.
Écrire une bibliothèque de Bignum simple qui inclut les opérations de base n'est pas du tout difficile. C'est une chose différente si vous souhaitez une efficacité maximale ou que vous souhaitez inclure des opérations complexes, mais cela ne semble pas être ce que cette question est à propos.
Dupliqué possible de Stocker et travailler avec de gros chiffres en C