C impression de la première million de nombres de Fibonacci
Je suis en train d'écrire du code C qui permet d'imprimer le premier de 1 million nombres de Fibonacci.
Le réel problème est que je veux aller le lats 10 chiffres de F(1 000 000) de
Je comprends comment la séquence fonctionne et comment écrire le code pour réaliser que cependant que F(1,000,000)
est très grande, j'ai du mal à trouver un moyen de le représenter.
C'est du code, je suis en utilisant:
#include<stdio.h>
int main()
{
unsigned long long n, first = 0, second = 1, next, c;
printf("Enter the number of terms\n");
scanf("%d",&n);
printf("First %d terms of Fibonacci series are :-\n",n);
for ( c = 0 ; c < n ; c++ )
{
if ( c <= 1 )
next = c;
else
{
next = first + second;
first = second;
second = next;
}
printf("%d\n",next);
}
return 0;
}
Je suis en utilisant long long
pour essayer et assurez-vous que il ya assez de bits pour stocker le nombre.
C'est la sortie pour la première 100
numéros:
First 100 terms of Fibonacci series are :-
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
-298632863
-1109825406
-1408458269
...
Tronquée de la sortie, mais vous pouvez voir le problème, je crois que la taille du nombre généré est à l'origine de la valeur de dépassement de capacité négatif. Je ne comprends pas comment l'arrêter en toute honnêteté.
Quelqu'un peut-il m'indiquer la bonne direction à la façon de gérer les numéros de cette taille?
Je n'ai pas essayé d'imprimer le premier million, car si elle échoue sur l'impression F(100)
il n'y a pas beaucoup d'espoir de l'impression F(1,000,000)
.
Un long ne sera pas près d'être suffisant!
Un
long long
devrait aller au-dessus 1836311903
au moinsJe pense que vous êtes inutilement sévère. Un début un étudiant pourrait ne pas avoir assez d'expérience avec l'arithmétique modulaire à réaliser que la totalité de calcul peut être effectué mod 10^10. Les choses qui sont évidentes pour un programmeur n'est pas toujours évident pour un étudiant.
Utiliser le
%lld
spécificateur de format au lieu de %d
, mais vous obtenez seulement un peu plus loin. Mais de toute façon les réponses ci-dessous sont assez complets.OriginalL'auteur Chris Edwards | 2015-11-16
Vous devez vous connecter pour publier un commentaire.
Vous voulez les 10 derniers chiffres de la Fib(1000000). Lire beaucoup plus sur Nombres de Fibonacci (et lire deux fois).
Sans beaucoup de réflexion, vous pouvez utiliser quelques bignum bibliothèque comme GMPlib. Vous boucle pour calculer Fib(1000000) à l'aide d'un quelques
mpz_t
bigint variables (vous n'avez certainement pas besoin d'un tableau d'un million dempz_t
, mais moinsmpz_t
les variables que vous avez des doigts de votre main). Bien sûr, vous n'aurez pas l'impression de tous les nombres de fibonacci, seule la dernière 1000000ème (aussi un ordinateur portable pas cher, aujourd'hui, dispose d'assez de mémoire, et crache ce nombre en moins d'une heure). Comme John Coleman répondu il a environ 200K chiffres (c'est à dire 2500 lignes de 80 chiffres chacun).(BTW, quand on pense à un programme de production de certains grands de sortie, vous pouvez le deviner-estimation de la taille typique de cette sortie et le temps typique pour l'obtenir; si elle ne rentre pas dans votre bureau, chambre ou votre ordinateur de bureau, vous avez un problème, peut-être un économique: vous avez besoin d'acheter plus de ressources informatiques)
Avis que l'efficacité bignum l'arithmétique est un objet dur. Algorithmes intelligents existent pour bignum arithmétique qui sont beaucoup plus efficaces que les naïfs celui que vous imaginez.
Fait, vous n'avez pas besoin de tout bigints. Lire de maths manuel sur l'arithmétique modulaire. Le module d'une somme (ou d'un produit) est congru à la somme (resp. le produit) du module. Utiliser cette propriété. 10 chiffres entiers s'inscrit dans un environnement 64 bits
int64_t
donc, avec un peu de réflexion vous n'avez pas besoin de tout bignum bibliothèque.(je suppose qu'avec un peu plus de la pensée, vous n'avez pas besoin de tout ordinateur ou de tout programme en C pour calculer la. Un bon calculateur, d'un crayon et d'un papier devrait être suffisant, et probablement la calculatrice n'est pas du tout nécessaire.)
La leçon à apprendre, lors de la programmation (ou lors de la résolution d'exercices en mathématiques) est à penser le problème et essayez de reformuler la question avant de commencer à coder. J. Pitrat (une Intelligence Artificielle, pionnier en France, aujourd'hui à la retraite, mais continue de travailler sur son ordinateur) a plusieurs intéressante blog entrées liées à: Est-il possible de définir un problème?, Lorsque Donald et Gerald rencontrer Robert, etc.
La compréhension et la réflexion sur le problème (et des sous-problèmes de trop!) est une partie intéressante de développement de logiciels. Si vous travaillez sur un logiciel de conception, il vous sera d'abord demandé de résoudre des problèmes du monde réel (par exemple, faire une vente de site web, ou autonome, l'aspirateur) et vous aurez besoin de penser à transformer ce problème en quelque chose qui est codable sur un ordinateur. Soyez patient, vous aurez besoin dix ans pour apprendre la programmation.
+1 Esp. le bit sur la résolution de problèmes. La programmation des ordinateurs pour faire quelque chose de facile... décidant ce pour programme de faire est la partie la plus difficile!
+1 pour encourager l'OP sur le droit de pistes. Jacques Pitrat de retraite est une je peux comprendre: il n'est pas sur le point de cesser ses incursions dans le domaine de l'IA. La lecture au sujet de sa position sur les pas de Michel Berry a été très amusant! Les deux exceptionnelle des esprits, mais de telles différences de style. La programmation est comme le bon vin: il faut 10 ans, en effet, pour devenir un programmeur compétent, mais pas tout le monde le fait, et le meilleur de continuer à apprendre pendant toute leur vie, sans relâche la recherche de l'élégance, de simplicité et de justesse.
OriginalL'auteur Basile Starynkevitch
À "obtenir les 10 derniers chiffres de F(1 000 000) de", il suffit d'appliquer la fonction de reste
%
lors du calcul denext
et d'utiliser la bonne spécificateur de format:"%llu"
.Il n'est pas nécessaire à la somme des chiffres plus significatifs que les 10 moins de chiffres significatifs.
Ma sortie (x ed les 5 derniers chiffres de ne pas donner la réponse finale)
Coleman Convenu. Un peu de mystère garde intéressant.
Généralement
0
est considéré comme le 0e valeur de Fibonacci,1
est la première, etc. Donc, techniquement,66843xxxxx
serait le 999999th chiffres, et82425xxxxx
serait le 1000000th.Vrai à propos de Fibonacci et de ses variations de ce qui est généralement le premier élément. Le concept de "première", C souvent un hors-en-1 résultat. Le premier élément d'un C tableau est indexé avec
0
. IAC, OP pouvez parcourir autant de fois que nécessaire. C'est peut-être un qui? dilemme?OriginalL'auteur chux
Par La Formule de Binet le n-ième Nombre de Fibonacci est environ le nombre d'or (environ 1.618) élevé à la puissance n, puis divisé par la racine carrée de 5. Une utilisation simple des logarithmes montre que le millionième nombre de Fibonacci a donc plus de 200 000 chiffres. La durée moyenne d'un des premiers millions de nombres de Fibonacci est donc plus de 100 000 = 10^5. Vous êtes donc en train d'imprimer 10^11 = 100 milliards de chiffres. Je pense que vous aurez besoin de plus qu'un gros int bibliothèque pour le faire.
D'autre part, si vous souhaitez simplement calculer le millionième numéro, vous pouvez le faire, même s'il serait préférable d'utiliser une méthode qui permet de ne pas calculer tous les intermédiaires numéros (comme tout simplement le calcul plutôt que de les imprimer tous serait encore impossible pour assez grand n). Il est bien connu (voir cette) que le n-ième nombre de Fibonacci est l'une des 4 entrées de la puissance n de la matrice
[[1,1],[1,0]]
. Si vous utilisez l'exponentiation par la quadrature (qui travaille pour le bien de la matrice des pouvoirs puisque la matrice de la multiplication est associative) avec un bon gros int bibliothèque -- il devient parfaitement possible de calculer la millionième nombre de Fibonacci.[Sur la Poursuite de l'Edit]: Voici un programme en Python pour calculer les très grands nombres de Fibonacci, modifié à maintenant accepter une option de module. Sous le capot, c'est à l'aide d'un bon C bignum de la bibliothèque.
De sortie (avec l'ajout des espaces):
Notez que ce que vous appelez la millionième nombre de Fibonacci, je l'appelle le 999,999 th -- car il est plus standard pour commencer avec 1 comme le premier nombre de Fibonacci (et appelez le 0 de la 0e si vous voulez compter comme un nombre de Fibonacci). Le premier numéro de sortie confirme qu'il y a plus de 200 000 des chiffres dans le nombre et la seconde donne les 10 derniers chiffres (qui n'est plus un mystère). Le nombre final est le 100 derniers chiffres de l'googolth nombre de Fibonacci -- calculée en une fraction de seconde. Je n'ai pas été capable de faire un googolplex encore 🙂
Peut-être que l'OP ne se soucient pas de tous les chiffres dans la sortie...
ensuite, vous pourriez faire quelques calculs (calcul de modulo 10^10) en premier, mais vous devriez avoir déclaré que dans votre question, qui devient très: "comment calculer les 10 derniers chiffres de F(1000000)?'
La simple approche itérative fonctionne jusqu'à un certain point. Je l'ai juste essayé pour 1 000 000 et il a fallu environ 8 secondes sur ma machine (par opposition à moins d'une seconde avec la matrice de base de l'approche, qui pourrait être encore plus efficace). Pour 10 000 000 de ma démarche prend moins de 10 secondes. J'ai eu l'approche itérative bouillonnant de plus de 5 minutes pour 10 000 000 de et suis susceptible de tuer le processus quand je suis fait avec ce commentaire. Mon intuition est que je serais frappé le mur avant d'un million, mais vous avez raison, un million de lui-même n'est pas déraisonnable. Merci pour cette remarque.
En cas de doute, essayez de la force brute... Ou mieux: essayez d'Abord de la force brute 😉
OriginalL'auteur John Coleman
Cette question vient sans doute d'un peu de programmation de la concurrence, et vous devez lire ces questions avec soin.
Le 1 millionième nombre de Fibonacci est ÉNORME. Probablement environ 200 000 chiffres. L'impression de la première de 1 000 000 nombre de Fibonacci va tuer toute une forêt d'arbres. Mais à lire attentivement: Personne ne vous demande de le 1 millionième nombre de Fibonacci. Vous êtes invité à les dix derniers chiffres de ce nombre.
Donc, si vous avez les 10 derniers chiffres de Fib(n-2) et de Fib(n-1), comment pouvez-vous trouver les 10 derniers chiffres de Fib(n)? Comment calculez-vous les dix derniers chiffres d'un nombre de Fibonacci sans calculer le nombre lui-même?
PS. Vous ne pouvez pas imprimer de longues numéros avec %d. Utiliser %lld.
OriginalL'auteur gnasher729
Votre algorithme est en fait correcte. Depuis que vous utilisez
unsigned long long
, vous avez assez de chiffres pour capturer le dernier 10 des chiffres et de la nature des unsigned dépassement de fonctions comme l'arithmétique modulo, de sorte que vous allez obtenir des résultats corrects pour au moins les 10 derniers chiffres.Le problème est dans le spécificateur de format que vous utilisez pour la sortie:
La
%d
spécificateur de format s'attend à uneint
, mais vous êtes de passage ununsigned long long
. L'utilisation de la mauvaise spécificateur de format appelle un comportement indéfini.Ce qui est le plus probable qui se passe dans ce cas particulier, c'est que
printf
est de ramasser le faible-de l'ordre de 4 octets denext
(en tant que votre système semble être en little endian) et de les interpréter comme une signéint
. Il finit par afficher les valeurs correctes pour environ les 60 premiers numéros, mais incorrecte, après que.Utiliser le bon spécificateur de format, et vous obtiendrez des résultats corrects:
Vous devez également faire la même chose lors de la lecture /impression
n
:Voici la sortie de numéros de 45-60:
OriginalL'auteur dbush