1. Accueil
  2. C / C++ / C++.NET
  3. Sources C / C++ / C++.NET
  4. Sources Maths & Algorithmes
  5. Fibo, calcule de la suite de fibonacci avec suport des grand nombres (+de 200 000 chiffres) (portable)

Fibo, calcule de la suite de fibonacci avec suport des grand nombres (+de 200 000 chiffres) (portable)

0/5 (9 avis)

Vue 9 310 fois - Téléchargée 207 fois

Télécharger le projet
Commenter

Description

j'ai vu sur ce site quelqu'un qui avais fait sa donc j'ai eu envie de tester.
je trouve l'optimisation pas mal :p
pour le compiler avec gcc utilisiser gcc fibo.c -o fibo... -O3
pour le lancer, c'est en console si vous l'executer sans parametre vous aurez l'aide

tout est dit dans la capture

Source / Exemple : 


//###################################################################
//#																	#
//# fichier	: fibo.c							version : V1.1		#
//# projet	: fibo 								date :	04/07/2004	#
//# par		: aerith et Thaeron										#
//#																	#
//# calcule de grand nombre avec la suite de fibonaci				#
//#																	#
//###################################################################

#include	<stdio.h>
#include	<time.h>		//clock()
#include	<stdlib.h>		//malloc()

long   atol(const char *nbr)
{
    unsigned long    total = 0;
    while (*nbr)
        total = 10 * total + (*nbr++ - '0');
    return total;
}

int main(int argc, char* argv[])
{
	FILE			*Fichier;
	unsigned long	Iteration, Taille, i = 1, Pos, Somme, Retenue = 0;
	unsigned long	*Nombre1, *Nombre2, *Cur1, *Cur2;
	char			*Data;
	clock_t			Temp = clock();

	if(argc >= 2)
	{
		Iteration = atol(argv[1]);
		Taille = atol(argv[2]);
	}
	else
	{
		printf("\nCalcul de la suite de fibonacci avec support des grands nombres\n");
		printf("Par aerith et Thaeron\tVersion 1.1\n\n");
		printf("Syntax : fibo <Iteration> <Buffer>\n");
		printf("  <Iteration>\t : Nombre d'iteration dans la suite\n");
		printf("  <Buffer>\t : Taille du buffer stockant le nombre\n\n");
		printf("Cree un fichier fibo.txt\n");
		return 0;
	}

	Nombre1 = malloc(Taille * 8);
	Nombre2 = malloc(Taille * 8);
	
	Fichier = fopen("fibo.txt", "w");

	for(Pos = 0; Pos < Taille; Nombre1[Pos] = Nombre2[Pos++] = 0);


    	
  • Nombre2 = 1;


	// iteration dans la suite
	do
	{
		// addition de grand nombre
		Pos = 0; 
		Cur1 = Nombre1;
		Cur2 = Nombre2;
		do
		{
 		    Pos++;
			// addition de nombres a 9 chiffre
			Somme = Retenue + *Cur1 + *Cur2;


    			
  • Cur1++ = *Cur2;

			Retenue = 0;
			if(Somme >= 1000000000)		// si resulatat a 10 chiffre
			{
				Somme -= 1000000000;	// on retire le 10eme et pose la retenue
				Retenue = 1;
			}


    			
  • Cur2 = Somme;

		}
		while((Pos < Taille) && *(Cur2++));

		// procedure de verification de debordement buffer
		if((Pos == Taille) && Retenue)
		{
			printf("Buffer overflow, iteration %i\nExecuter en %i ms \n", i, clock() - Temp);
			return -1;
		}
	}
	while(++i < Iteration);

	fprintf(Fichier,"Nombre case : %i\n", Pos);
  	printf(			"Nombre case : %i\n", Pos);

	// sauvegarde le dernier nombre dans un fichier
	Data = malloc(Pos*10+1)+(Pos*10+1);


    	
  • Data-- = 0;

  	do
	{


    		
  • Data-- = ' ';

  		// conversion de unsigned long en char, ecrit de droite a gauche
		for(i = 0; i < 9; i++)
		{


    			
  • Data-- = (char)((*Nombre2 % 10) + '0');

    • 			
  • Nombre2 /= 10;

		}
		Nombre2++;
	}
	while(--Pos > 0);
	
	fprintf(Fichier,"Iteration : %i\n%s\nExecuter en %i ms\n", Iteration, Data, clock() - Temp);
  	printf(			"Iteration : %i\n%s\nExecuter en %i ms\n", Iteration, Data, clock() - Temp);

  	free(Data);
  	free(Nombre1);
  	free(Nombre2);
  	fclose(Fichier);
	return 1;
}

Conclusion :


Thaeron ma orienter vers les pointeur pour l'additionneur =)
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire Commentaires
CrazyNowan
Messages postés
1
Date d'inscription
mardi 8 juin 2010
Statut
Membre
Dernière intervention
14 juin 2010
14 juin 2010 à 04:43
En considérent la suite comme une ELRH, on résout le n-ième terme à l'aide de cette formule :
http://upload.wikimedia.org/math/3/d/0/3d0e62d6f0eb21015186116cf3fe0b24.png

Evidemment, on risque une légère erreur de précision due aux calculs en virgule flottante...
cs_aerith
Messages postés
54
Date d'inscription
lundi 17 mars 2003
Statut
Membre
Dernière intervention
12 mars 2006
3 juil. 2004 à 18:51
a ouai, y a donc un bug, je taff la dessus
Hylvenir
Messages postés
364
Date d'inscription
mercredi 11 février 2004
Statut
Membre
Dernière intervention
5 octobre 2006
 2
27 juin 2004 à 02:05
J'ai l'impression qu'il y a un pb avec ton source mais je n'arrive pas à trouver quoi...

as-tu valider tes résultats pour 499 (500 pour toi) par exemple ?

http://sources.wikipedia.org/wiki/Fibonacci_Numbers

Mon programme ne calcule pas la même chose pour 99999 (100000 pour toi) alors je trouve le bon résultat pour 499 (500 pour toi)
Si tu es intéressé je peux toujours te la passer pour comparer.
Hylvenir
Messages postés
364
Date d'inscription
mercredi 11 février 2004
Statut
Membre
Dernière intervention
5 octobre 2006
 2
26 juin 2004 à 21:21
Salut,
tu as un exemple de ton programme pour des valeurs triviales ?
Je n'arrive pas à trouver fibonacci dans totut ce qui est affiché ou dans le fichier.

ex: fibo 5 10

Iteration : 5

Executer en 0 ms
Nombre case : 1, Taille nombre : 9
BruNews
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
 26
26 juin 2004 à 19:05
Salut,

fais donc un upgrade de ta source avec FIBONACCI ecrit comme il se doit. Dans l'etat actuel, elle ne sortira jamais si qlqun fait une recherche sur ce theme.

BruNews, Admin CS, MVP Visual C++
Afficher les 9 commentaires
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_aerith)