Fibonacci problem - da vas vidim matematičari

Ovaj zadatak je moguče riješiti i s pomoč programskih jezika, a meni VB radi strašne nevolje, double vrijednost ne ide više od 1E300 u VB.

Fibonnacijeva sequenca izgleda ovako :

F[0]=0
F[1]=1
za sve x>1,
F[x]=F[x-1]+F[x-2]

Evo sequence 0,1,1,2,3,5,8,13,21,...

Problem:

nađi najmanji x>0 tako da je F[x] mod 2^32 =0

Programski mi ovaj problem ne uspjeva zbog gornjeg razloga, probao sam i sa matematikom sa dedukcijom i traženjem sledečeg para u sequenciji, sledeči (x+1) par (F(x+1)) može se skalkulirati kao floor( (x+1+sqrt(5*x^2))/2 ), no tu sam opet pri istom problemu kod VB - infinity problem.

Sledeča mogučnost je reprezentacija sequence u BINARNOM smislu, a i tu sam na istom.

Dal mi može tko reči koje je riješenje ovoga ili me bar uputiti za uspješan kraj ovog zadataka

Več unaprijed hvala


Boris

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

koliko sam shvatila,tebi je potreban algoritam za izracunavanje tog fibonacijevog broja?
ne znam hoce li ti ovo sta pomoci,nadam se da ces dobiti naku ideju za taj algoritam
u matematici se za izracunavanje n-og fibonacijevog broja koristi metod za resavanje dif. jednacina.stavljajuci f(n)=r^n(r<>0) u rekurzivnu formulu(koju si gore napisao),dobijamo
f(n+2)-f(n+1)-f(n)=r^n(r^2-r-1)=0,pa resavajuci kvadratnu jednacinu dobijamo r=(1+-sqrt(5))/2,pa se uvrstavanjem,za neke konstante A i B dobija
f(n)=A*((1-sqrt(5))/2)^n+B*((1+sqrt(5))/2)^n(ove konstante su potekle od resenja dif. jednacine drugog reda,kojoj polazna rekurzija odgovara)
sada,posto f(n) zadovoljava rekurziju i uzimajuci za n=1 i n=2 dobijamo sistem od dve linearne jednacine po A i B,pa nalazimo da je A=1/sqrt(5) i B=-1/sqrt(5)
zatim imamo
f(n)=(1/sqrt(5))*[((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]
kako je drugi clan u zagradi,kad se podeli sa sqrt(5) po aps. vrednosti manji od 1/2,sledi da je f(n) jednak prirodnom broju koji je najblizi prvom clanu u zagradi,kad se podeli sa sqrt(5)
osim toga,vazi tvrdjenje da su za fiksirano k>=3 fibonacijevi brojevi f(m*k)(m=1,2...) deljivi brojem f(k),tj. ostatak je 0,kako se tebi u zadatku trazi
na osnovu ovoga mozes da napravis neki algoritam koji ce ti izracunati broj koji trazis
nesto slicno sam radila u paskalu,pa mislim da nece biti problema
poz

Potpis

beeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeezi

hm !!

ne znam kako je f(n)=(1/sqrt(5))*[((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]

kako je drugi clan u zagradi,kad se podeli sa sqrt(5) po aps. vrednosti manji od 1/2,sledi da je f(n) jednak prirodnom broju koji je najblizi prvom clanu u zagradi,kad se podeli sa sqrt(5)

Sve dobro, ali ja ne dobivam iste rezultate za skalkulirani f(n) i rezultat po toj formuli int (1/sqrt(5))*[((1+sqrt(5))/2)^n/sqrt(5))
n f(n) formula
0 0 1
1 1 2
2 1 3
3 2 6
4 3 9
5 5 16
6 8 25
7 13 42
8 21 67
9 34 110

Gdje je greška ?

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

((1+sqrt(5))/2)^n
ovo je prvi clan zagrade,njega podeli sa sqrt(5),samo pazi na zagrade i redosled izvrsavanja operacija
dakle
[((1+sqrt(5))/2)^n]/sqrt(5)
kako kvadratna jednacina,u ovom slucaju,ima 2 realna i razlicita resenja,to se f(n),po metodi resavanja dif. jednacina,pise kao zbir ta 2 resenja,koja su,svako ponaosob,pomnozena nekom realnom konstantom
poz

Potpis

beeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeezi

n f(n) I(n)
0 0 0
1 1 0
2 2 1
3 4 1
4 8 3
5 16 4
6 32 8
7 64 12
8 128 21
9 256 33
10 512 55
11 1024 88
12 2048 144
13 4096 232
14 8192 377
15 16384 609
16 32768 987

pri tome je I(n)==INT((((1+SQRT(5))/2)^n)/SQRT(5))

I(n)<>f(n). ne znam kako bi to moglo biti.
Ipak hvala za upute

Neznam, kako bih riješio ovaj primjer, no mislim, da je najbolje da napišem koji program, koji zna da kalkulira i preko 1E300 ili kakvo koju vrstu dedukcije.

On Maple it took half day to get to f(1000000000)
On 16-bit asm it took 1min 42sec to find an answer
On 32-bit asm it toom 28sec to get the answer
On Delphi also 28 sec - checked with disassembler - the code matched with my assembly code.

probat ču sa mod 2^16 i ostalima da vidim dali ima koje veze.

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

n f(n) mod 32 mod 31 mod 30 mod 29 mod 28 mod 27 mod 26 mod 25
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
3 2 2 2 2 2 2 2 2 2
4 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 5 5
6 8 8 8 8 8 8 8 8 8
7 13 13 13 13 13 13 13 13 13
8 21 21 21 21 21 21 21 21 21
9 34 34 34 34 34 34 34 34 34
10 55 55 55 55 55 55 55 55 55
11 89 89 89 89 89 89 89 89 89
12 144 144 144 144 144 144 144 144 144
13 233 233 233 233 233 233 233 233 233
14 377 377 377 377 377 377 377 377 377
15 610 610 610 610 610 610 610 610 610
16 987 987 987 987 987 987 987 987 987
17 1597 1597 1597 1597 1597 1597 1597 1597 1597
18 2584 2584 2584 2584 2584 2584 2584 2584 2584
19 4181 4181 4181 4181 4181 4181 4181 4181 4181
20 6765 6765 6765 6765 6765 6765 6765 6765 6765
21 10946 10946 10946 10946 10946 10946 10946 10946 10946
22 17711 17711 17711 17711 17711 17711 17711 17711 17711
23 28657 28657 28657 28657 28657 28657 28657 28657 28657
24 46368 46368 46368 46368 46368 46368 46368 46368 46368
25 75025 75025 75025 75025 75025 75025 75025 75025 75025
26 121393 121393 121393 121393 121393 121393 121393 121393 121393
27 196418 196418 196418 196418 196418 196418 196418 196418 196418
28 317811 317811 317811 317811 317811 317811 317811 317811 317811
29 514229 514229 514229 514229 514229 514229 514229 514229 514229
30 832040 832040 832040 832040 832040 832040 832040 832040 832040
31 1346269 1346269 1346269 1346269 1346269 1346269 1346269 1346269 1346269
32 2178309 2178309 2178309 2178309 2178309 2178309 2178309 2178309 2178309
33 3524578 3524578 3524578 3524578 3524578 3524578 3524578 3524578 3524578
34 5702887 5702887 5702887 5702887 5702887 5702887 5702887 5702887 5702887
35 9227465 9227465 9227465 9227465 9227465 9227465 9227465 9227465 9227465
36 14930352 14930352 14930352 14930352 14930352 14930352 14930352 14930352 14930352
37 24157817 24157817 24157817 24157817 24157817 24157817 24157817 24157817 24157817
38 39088169 39088169 39088169 39088169 39088169 39088169 39088169 39088169 5533737
39 63245986 63245986 63245986 63245986 63245986 63245986 63245986 63245986 29691554
40 102334155 102334155 102334155 102334155 102334155 102334155 102334155 35225291 1670859
41 165580141 165580141 165580141 165580141 165580141 165580141 31362413 31362413 31362413
42 267914296 267914296 267914296 267914296 267914296 267914296 133696568 66587704 33033272
43 433494437 433494437 433494437 433494437 433494437 165058981 30841253 30841253 30841253
44 701408733 701408733 701408733 701408733 164537821 164537821 30320093 30320093 30320093
45 1134903170 1134903170 1134903170 61161346 61161346 61161346 61161346 61161346 27606914
46 1836311903 1836311903 1836311903 762570079 225699167 225699167 91481439 24372575 24372575
47 2971215073 2971215073 823731425 823731425 286860513 18425057 18425057 18425057 18425057
48 4807526976 512559680 512559680 512559680 512559680 244124224 109906496 42797632 9243200
49 7778742049 3483774753 1336291105 262549281 262549281 262549281 128331553 61222689 27668257
50 12586269025 3996334433 1848850785 775108961 238238049 238238049 104020321 36911457 3357025
51 20365011074 3185141890 1037658242 1037658242 500787330 232351874 98134146 31025282 31025282
52 32951280099 2886509027 739025379 739025379 202154467 202154467 67936739 827875 827875
53 53316291173 1776683621 1776683621 702941797 166070885 166070885 31853157 31853157 31853157
54 86267571272 368225352 368225352 368225352 368225352 99789896 99789896 32681032 32681032


Odgovor je bolje vidjeti u xls fajlu, ali zbog rounding accurancy u excel-u odgovori nisu baš tačni, tačni su recimo na 12 decimalki.
Sada trebam samo još koji dobar programčič ....

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Čini mi se da je za $ F(n) equiv 0 mod 2^{32} $, $n$ jako veliki broj. Zato ti double ne može pomoći, već samo ili program ili procedura koja može da radi sa jako velikim brojevima. Moj ti je savet, ako ne poznaješ problematiku, da uzmeš Matlab i napišeš generator $F(n)$ u njemu.

Matlab će odraditi preciznu aritmetiku za tebe.

U suprotnom slučaju ti treba procedura u VB koja ume da sabira veeeelike brojeve, koju možeš i sam da napišeš. Ideja je da sabiraš Fibonačijeve brojeve dok ne pronađeš onaj čija su 32 donja bita jednaka nuli.

Da li si probao da proceniš koliko je $n$ tog broja. Da li postoji negde dokaz na primer da $n$ ne može biti manje od dvestapedeset milijardi ili tako nešto? Pitanje je da li brute force pristup može bilo šta da uradi.

poz.

Odgovor od frenda :
On Maple it took half day to get to f(1000000000)
On 16-bit asm it took 1min 42sec to find an answer
On 32-bit asm it toom 28sec to get the answer
On Delphi also 28 sec - checked with disassembler - the code matched with my assembly code.

Ja osobno mislim, da je n << 1000000000
Probavam sa matematikom upravo sada :)
Pa ču vam "ako usoijem" dati odgovor, a probajte da to riješite i sami

Pozdrav

Boris

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Da li znaš koliko cifara ima $ F(n) $ ako je $ n = 1000000000? Ja ne znam, al evo ti brza procena. Naime $ F(n) $ eksponencijalno raste sa $n$ što se vidi iz funkcije generatrise.

S druge strane broj cifara raste logaritamski sa porastom vrednosti broja tako da bih rekao da je broj cifara broja kog tražiš proporcionalan sa $n$.

A milijardu cifara traži oko milijardu bajtova za pamćenje. Dobro, nije _baš_ tako, al hoću da ti kažem da ti je problem kao malko veći nego što očekuješ, tim pre što ne znaš ni da li broj koji ispunjava tvoj uslov uopšte postoji.

brute force sa matematikom je prespor, treba nešto drugo, kakvu binarnu sličnost gore navedenih postupka ili koja fora fibb sequence/členova u njime, deduktivni pristup u binarnom smislu ????

Nemam pojma, a nemem ni riješenja
Fibonacci[10000000] u attachmentu

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

ne ide ni u zip !
txt fajl rješenja je dug 2.170.283 bytes !!!!

broj decimalnih mjesta u njemu : 2089877
a početak :

1,12983437822539976031706363774586637294483719048904088151357764324553473116793*E2089877

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Proveri da li je broj koji si dobio stvarno resenje ili je samo posledica gubitka preciznosti. To ti kažem zbog onog E u rezultatu.

poz.

Ne to nije rezultat koji bi mogao biti rješenje.

I'm still working on it ...

Svaka pomoč pri izradi programa je dobrodošla

Boris

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Heh, evo i dodatnog razloga

>dir /b
fibonacci.asm
fibonacci.exe
fibonacci.obj
Makefile

\>fibonacci.exe
X = *********, time elapsed: 4.828s

can anyone beat this?
(assuming i have PIII 1GHz and average time after 10 runs was 4.8265)

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

koliko ja vidim,ovo vise nije matematika,pa ti savetujem da isto pitanje postavis u forumu art of programing(ako sam dobro napisala)
istovremeno bih zamolila bilo koga,ko ima volje,da mi objasni oznake tipa $n$ i sl,primetila sam da se to i jos neke dr. oznake koriste ovde,a ja ne znam da ih tumacim.verovatno je neki mat. program,ali ...
poz

Potpis

beeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeezi

Pazite ovako.. Ja kad probam da iskalkulisem Fibenacijev niz sledecom formulom

Ovo je znaci algoritam koji koristim, i misteriozno nakon 24 broja se niz poremeti, evo kako:

Pocetak Fibonacijevog niza
1: 0
2: 1
3: 1
4: 2
5: 3
6: 5
7: 8
8: 13
9: 21
10: 34
11: 55
12: 89
13: 144
14: 233
15: 377
16: 610
17: 987
18: 1597
19: 2584
20: 4181
21: 6765
22: 10946
23: 17711
24: 28657
25: -19168
26: 9489

Dali neko zna zasto se ovo desava? I zasto bas na tom broju?

Naravno. To je u stvari i jedina teskoca kod ovog problemcica.

Stvar je u tome sto su promenjive koje koristis iz nekog razloga po defaultu 16-bitni oznaceni celi brojevi cija vrednost moze da se krece otprilike u granicama -32000 - +32000. Zato ako sabiras dva broja koji ciji je zbir veci od najveceg broja, rezultat se "premota" u minus. Kao ono ako se secas u tetrisu nekada sto je bilo.

Resenje je da umesto 16-bitnih intova koristis 32-bitne, u kom slucaju je granica podignuta na nekoliko milijardi ali opet postoji. To ti na zalost verovatno nece pomoci da resis zadatak.

poz.

Zdravo. Matematicke formule uokvirene dolarskim znakovima poticu iz programa koji se zove TeX (cita se: teh, a pise bas ovako, sa izmestenim slovima!), ciji je autor covek za koga s obzirom da si matematicar sigurno znas: Donald Ervin Knut.

TeX je program za pripremu za stampu lepih knjiga, narocito onih koje imaju u sebi puno matematike.

Ako otvoris neki od svojih udzbenika, recimo neki koji u sebi ima raskosne matematicke formule, vrlo verovatno ces gledati u knjigu koja je napravljena uz upotrebu TeX-a.

Ideja da se formule uokviruju dolarskim znacima na forumu potice od toga sto bi lako moglo da se namesti da server svaku formulicu provuce kroz TeX i od nje napravi slozenu matematicku formulu sa svim notacijskim pogodnostima. Tako ako bih hteo da napisem sumu svih brojeva od 1 do n mogao bih da stavim

$$ \sum_{i=1}^n i $$

sto bi se pojavilo na slici kao grcko veliko sigma, koje ispod ima tekst i=1 a iznad n i samo i kao argument. Izmedju ostalog u linku koji je dat na dnu poruke imas objasnjenu sintaksu TeX jezika

Ne treba da napominjem da svaki pravi matematicar mora da zna TeX. Zato se sto pre baci na ucenje. :) Za svakodnevnu upotrebu je pogodnija nadogradnja TeX-a koja se zove LaTeX (cita se: lateh, i pise bas ovako, sa izmestenim slovima).

www.ctan.org/tex-archive/info/lshort/english/lshort.pdf

poz.

Potpis

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Ok je to za niz... To moze da se resi pravljenjem sopstvene rutine za unos i sabiranje brojeva kroz array ili matricu..

y= F(x)/2&sup3;&sup2; &#8594; 0

Fora je u tome sto 2&sup3;&sup2; neki konacan broj. Ako pustimo da F(x) tezi beskonacnosti dobicemo rezultat:

y >= 1


JEDINI nacin da dobijemo 0 je da napravimo neku gresku u deljenju i da pobrkamo znakove...

Jesdnostavno, bilo sta podeljeno sa nesto konacno ce biti >0, ovo ne znam kako resiti, ali mi se sve cini da je to kao onaj 'dokaz', 1+1=3 gde se gresi sa znakovima i matematickim pravilima da bi se dobio rezultat...

E sad... Ako pustimo da F(x) &#8594; &#8734; radi analiziranja ovog problema vec moramo da ulazimo u domen vise matematike... A uostalom beskonacnost jos uvek nije definisanja niti je ponasanje brojeva u beskonacnosti jos uvek dovoljno ispitano da bi mi mogli da navedemo resenje ovog problema.