View Full Version : Generatore numeri fibonacci
fabio87a
04-02-2006, 16:20
Stamattina durante una pausa dallo studio e mi sono sbizzarrito un pò e ho fatto questo:
#include <stdio.h>
#include <time.h>
#define size 4096
FILE *fibo;
int F[size], F1[size], F2[size];
int n, i, count=2;
void Print();
main()
{
time_t ts, te;
(void) time(&ts);
fibo=fopen("fibonacci.txt","w");
printf("Fibonnacci Numbers' Generator v1.0");
printf("\nBuilt by Fabio Amodei amodei.fabio@tiscali.it");
printf("\n\nStart calculating....");
fprintf(fibo, "Fibonnacci Numbers' Generator v1.0");
fprintf(fibo, "\nBuilt by Fabio Amodei amodei.fabio@tiscali.it");
fprintf(fibo, "\n");
fprintf(fibo, "I primi 1000 numeri di fibonacci sono:\n");
fprintf(fibo, "\ni= 1\tFibonacci= 0");
fprintf(fibo, "\ni= 2\tFibonacci= 1");
F1[0]=1;
F2[0]=0;
for (n=3; n<=10000; n++)
{
for (i=0; i<size; i++) F[i]=F1[i]+F2[i];
for (i=0; i<size; i++)
{
if (F[i]>=10)
{
F[i+1]++;
F[i]-=10;
}
}
for (i=0; i<size; i++) F2[i]=F1[i];
for (i=0; i<size; i++) F1[i]=F[i];
fprintf(fibo, "\ni= %d\tFibonacci= \n", n);
Print();
fprintf(fibo, "\n\n");
}
fclose(fibo);
(void) time(&te);
printf("\a\n\nTime Elapased: %d seconds", te-ts);
printf("\nYou can find the first 10000 numbers in the file fibonacci.txt");
getch();
return 0;
}
void Print()
{
int formatline=0, formatblock=0;
for (i=0; i<size; i++)
{
formatblock++;
formatline++;
fprintf(fibo, "%d", F[size-1-i]);
if ((formatblock/8)==1)
{
fprintf(fibo, " ");
formatblock=0;
}
if ((formatline/64)==1)
{
fprintf(fibo, "\n");
formatline=0;
}
}
return;
}
Che ne pensate? genera un file da 46 mb :eek:
rdefalco
04-02-2006, 23:49
Che ne pensate? genera un file da 46 mb :eek:
Semplice :D implementa l'algoritmo di Huffmann per la compressione di stringhe e riduci il tutto a dimensioni più umane.
fabio87a
05-02-2006, 14:53
che cos'è sto algoritmo di huffman?
bo io intanto avevo gia risolto (adesso salva solo le cifre significative e non gli 0 inziali...
#include <stdio.h>
#include <time.h>
#define size 2112
FILE *fibo;
int F[size], F1[size], F2[size];
int n, i, count=2;
void Print();
main()
{
time_t ts, te;
(void) time(&ts);
fibo=fopen("fibonacci.txt","w");
printf("Fibonnacci Numbers' Generator v1.2");
printf("\nBuilt by Fabio Amodei amodei.fabio@tiscali.it");
printf("\n\nStart calculating....");
fprintf(fibo, "Fibonnacci Numbers' Generator v1.0");
fprintf(fibo, "\nBuilt by Fabio Amodei amodei.fabio@tiscali.it");
fprintf(fibo, "\n");
fprintf(fibo, "I primi 10000 numeri di fibonacci sono:\n");
fprintf(fibo, "\ni= 1\tFibonacci= 0");
fprintf(fibo, "\ni= 2\tFibonacci= 1");
F1[0]=1;
F2[0]=0;
for (n=3; n<=10000; n++)
{
for (i=0; i<size; i++) F[i]=F1[i]+F2[i];
for (i=0; i<size; i++)
{
if (F[i]>=10)
{
F[i+1]++;
F[i]-=10;
}
}
for (i=0; i<size; i++) F2[i]=F1[i];
for (i=0; i<size; i++) F1[i]=F[i];
fprintf(fibo, "\ni= %d\tFibonacci= \n", n);
Print();
fprintf(fibo, "\n\n");
}
fclose(fibo);
(void) time(&te);
printf("\a\n\nTime Elapased: %d seconds", te-ts);
printf("\nYou can find the first 10000 numbers in the file fibonacci.txt");
getch();
return 0;
}
void Print()
{
int formatline=0, formatblock=0;
int if0=0;
for (i=0; i<size; i++)
{
while (if0==0)
{
if (F[size-1-i]!=0) if0=1;
break;
}
if (if0==1)
{
formatblock++;
formatline++;
fprintf(fibo, "%d", F[size-1-i]);
if ((formatblock/8)==1)
{
fprintf(fibo, " ");
formatblock=0;
}
if ((formatline/64)==1)
{
fprintf(fibo, "\n");
formatline=0;
}
}
}
return;
}
Ho modificato solo la funzione print... risultato 12 mb...
ho provato a fargli fare 1 milione (avevo messo 12000 cifre), ma il file era + grasso di 200mb!!! :eek:
rdefalco
05-02-2006, 15:40
Continuo a non capire quale sia la richiesta però... :mbe:
ho provato a mettere 50000 e mi fa un file grosso 74 mega....pero se vado in cima a vedere cosa stampa, stampa i numeri molto random...tipo l ultimo è 5001, poi 4999 poi 4996 poi 4995...strano vero :O ?
Che ne pensate?
abòh, se funziona...
rdefalco
05-02-2006, 17:15
Per calcolare i numeri di Fibonacci usare un array è un suicidio inutile. Bastano due variabili, una per l'ultimo numero calcolato, una per il penultimo.
Poi non ho capito
if (F[i]>=10)
{
F[i+1]++;
F[i]-=10;
}
Forse ti conviene usare una libreria specializzata (tipo NTL (http://shoup.net/ntl/)):
#include <NTL/ZZ.h>
#include <iostream>
#include <fstream>
#include <ctime>
int main()
{
time_t ts, te;
std::ofstream out("fibonacci.txt");
ts = time(NULL);
out << "I primi 10000 numeri di Fibonacci sono:\n";
out << "i = 0\tFibonacci = 0\n";
out << "i = 1\tFibonacci = 1\n";
NTL::ZZ primo, secondo;
primo = 0;
secondo = 1;
for (int i = 2; i <= 10000; ++i) {
primo += secondo;
NTL::swap(primo, secondo);
out << "i = " << i << "\tFibonacci = " << secondo << "\n";
}
te = time(NULL);
std::cout << "Tempo impiegato: " << (te - ts) << std::endl;
}
BTW, non si possono usare i tipi nativi (perlomeno in C/C++) per ovvi motivi:
pippo@house:/tmp$ tail -1 ./fibonacci.txt | fold -w 64
i = 10000 Fibonacci = 336447648764317832666216120051075433
1030214846068006390656476997468008144216666236815559551363373402
5582065332680836159373734790483865268263040892463056431887354544
3695598274916066020998841839338646527313000888302692356736131351
1757929743785441375213052050434770160226475831890652789085515436
6159582987279682987510631200575428783453215515103870818298969791
6131278562650331954871402142875326981879620469360978799003509623
0229102636813149319527563022783762844154036058440257211433496118
0023091208287046088923962328835461505776583271252546093591128203
9252853934346209042452489294039017062338889910858410651831733604
3747073790855263176432573399371287193758774689747992630583706574
2830161637408969178426378624212835258112820516370298089332099905
7079200643674262023897831114700540749984592503606335609338838319
2338678305613643535189213327973290813373264265263398976392272340
7882928177953580570993691049175470808931841056146322338217465637
3212482263830921032977016480547262438423748624114530938122065649
1403275108664339451751216152654536133311131404243685480510676584
3493523836959653428071768775328348234345557366719731392746273629
1082106792807847180353291311767789246590899386354593278945237776
7440619224033763867400402133034329749690202832814593341882681768
3893072003634795623117103101291953169794607632737589253530772552
3759437884345040677155557790564504430166401194625809722167297586
1502696844314695203461493229110597067624326851599283470989128470
6740862008587135016260312071903172086094081298321581077282076353
1866246112782455372085323653057759564300725177443150515396009051
6860322034916322264088524885243315805153484962243484829938090507
0483482449327453732624567755879089187190803662058009594743150052
4025327097469953187707243768259074199396322659841474981936092852
2394503970716544315642132815768890805878318340491743455627052022
3564846495196112460268313970975069382648706613264507665074611512
6775227486215986425307112984411826226610571635150692600298617049
4542504749137811515413994155067125627119713325276363193960690289
5650288268608362241082050562430701794976171121233066073310059947
366875
rdefalco
05-02-2006, 22:59
Forse ti conviene usare una libreria specializzata
Che stupido a non pensarci :doh: Fibonacci ha una complessità esponenziale (2^0.6n se non ricordo male) quindi raggiunge in men che non si dica un numero di bit inimmaginabile. Ovviamente nei tipi di dato standard comporta un riempimento quasi immediato, figuriamoci alla venticinquemilesima iterazione!
^TiGeRShArK^
05-02-2006, 23:35
:eek:
e pensare ke in ruby o python si faceva in 3 o 4 righe di codice (senza la scrittura su file)....
rdefalco
05-02-2006, 23:57
:eek:
e pensare ke in ruby o python si faceva in 3 o 4 righe di codice (senza la scrittura su file)....
Ma anche in C o Java non dovrebbe essere altro che un for di poche righe... il problema resta il tipo di dati da adottare. Java ha la classe BigDecimal che è limitata solo dalla memoria di sistema...
beh in java son 3 righe...per scrivere su file e incaprettare il tutto non penso ci vadano piu di una 15/20 righe...
aLLaNoN81
06-02-2006, 00:38
Ma evitare del tutto gli array (che sprecano pure memoria oltre che tempo d'esecuzione) e scrivere direttamente al volo il calcolo su file faceva così schifo? :mbe:
fabio87a
06-02-2006, 07:58
Per calcolare i numeri di Fibonacci usare un array è un suicidio inutile. Bastano due variabili, una per l'ultimo numero calcolato, una per il penultimo.
Poi non ho capito
if (F[i]>=10)
{
F[i+1]++;
F[i]-=10;
}
sto pezzo qui "riporta" un'unità elemento nel posto successivo dove c'è una caratterializzazione posizionale superiore...
ho provato a cercare qualche libreria, visto che non ne ho travate (e dubito che con qualsiasi libreria si possa arrivare a cifre tipo 1 milione... ho pensato di risolvere il problema con un array)
l'ho modificato per 100000 (dovete pure modificare la dimensione massima "size" però... io ho messo 10000) e i numeri non sono per niente random...
fabio87a
06-02-2006, 08:13
avete parlato di librerie ntl: sapreste dirmi dove trovarle?
grazie
rdefalco
06-02-2006, 08:37
avete parlato di librerie ntl: sapreste dirmi dove trovarle?
grazie
Quando nomina per la prima volta NTL Qu@ker ci ha messo il link. Controlla!
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.