[java]Fibonacci reeks verder uit rekenen

[wvdburgt]

Beste mede programmeurs.

Allereerst zal ik eerst uitleggen wat nou de fibonacci reeks is voor de gene die dit niet weten. Dat is een reeks waarvan de vorige 2 getallen bij elkaar opgeteld het volgende getal is. Het staat goed uitgelegd op deze pagina: http://www.home.zonnet.nl/LeonardEuler/fibo1.htm

Ik ben eens weze proberen of ik dit met de huidige kennis en ervaring kan programmeren. ( 2 jaar java op mbo niv 4)
Na wat geklooi en wat hulp van een kennis kwam ik op deze code:

code:

import java.awt.*;
import java.applet.*;

public class Fibonacci_reeks extends Applet {
long [] fibo;

    public void init() {
    fibo = new long [ 1000 ];
    fibo[ 0 ] = 0; 
    fibo[ 1 ] = 1; 
 
    for (i = 2; i < 1000; i++) 
        { 
        fibo[ i ] = fibo[ i - 2  ] + fibo[ i - 1  ]; 
        }  
 }

    public void paint(Graphics g) {
    int yPos = 20;

    for( i = 0; i < 1000; i++)
        { 
        g.drawString(""+fibo [i], 50, yPos );
        yPos +=20;
        }

    }

Dit werkt in principe prima alleen ik kom op een gegeven moment het bereik van de long tegen. Ik kom na ongeveer 70 keer die berekening te hebben uitgevoerd in de min terecht. Dit is me allemaal duidelijk hoe ik hier kom. (Na het maximale getal gaat het in in de min met het hoogste getal verder en loopt zo weer naar de 0 toe).

Wat ik me af vroeg is hoe ik nog meer getallen kan uitrekenen zonder dat ik het probleem met die long tegen kom. Ik heb van alles bedacht maar ik kom er niet uit met mijn ervaring. Ik heb al wat gezocht maar ik weet niet waar ik op moet zoeken. (zoektermen grotere waardes java en grotere getallen java).

Heeft iemand een tip zodat ik weer verder kan?
nou ga ik mooi slapen het is al laat genoeg:)

[4VAlien]

je kan je datatypes nog wat oprekken met unsigned long of long long en anders moet je een grote getallen library gebruiken (kan zo maar in Java SDK zitten) verder kan je natuurlijk ook gewoon de getallen opslaan in strings en dan optellen net als je op papier twee getallen onder elkaar optelt, van rechts naar links.

[T.T.]

Misschien moet je even naar BigInteger kijken (en BigDecimal als je wilt gaan delen ofzo)

http://java.sun.com/j2se/...java/math/BigInteger.html

voorbeeldje gebruik

[ Voor 49% gewijzigd door T.T. op 01-07-2005 03:03 ]

[RicX]

Je moet het recursief programmeren (oftewel: de functie roept zichzelf steeds weer aan). Dat je verder kan uitrekenen omdat alleen het laatste getal wordt opgeslagen, de long kun je typecasten naar een string en zo lang mogelijk maken als je wilt... (en ook nog eens gemakkelijk printen )

[4VAlien]

ehm de niet recursieve optie is in principe beter voor dit probleem

[NMe]

4VAlien schreef op vrijdag 01 juli 2005 @ 03:51:
ehm de niet recursieve optie is in principe beter voor dit probleem

Inderdaad. Dynamisch programmeren is de snelste oplossing, al gebruikt de topicstarter dat niet echt:

Java:

fibo[ i ] = fibo[ i - 2  ] + fibo[ i - 1  ];

Door dit te doen bereken je elk getal in de rij (behalve fibo[0] en fibo[1]) twee keer. Wanneer je tussendoor alles opslaat in een lijstvorm of tussenvariabele hoef je niet telkens getallen te berekenen die je al berekend hebt.

Overigens is een bigint inderdaad een goede oplossing hier. Bigints zijn intern opgeslagen als string of array, en zijn daardoor niet begrensd door de grootte van een datatype.

[Robtimus]

Er zijn (minimaal) 3 manieren om fib(n) te berekenen: de recursieve, de lineaire en de exponentiele. Deze laatste twee staan in 'Programming: The Derivation of Algorithms' van Anne Kaldewaij.

Lineair voor fib(N):

Java:

// N = n
long x = 0; // x = fib(N-n)
long y = 1; // y = fib(N-n+1)
while (n > 0)
{
    // volgend blok is niets anders dan x, y = y, x + y
    long t = x;
    x = y;
    y = t + y;
    n--;
}
// n = 0, so x = fib(N)
return x;

De exponentiele heeft te maken met matrixes, maar hier is de code:

Java:

// N = n
long a = 0; // the first matrix value
long b = 1; // the second matrix value
long x = 0; // x = fib(N-n)
long y = 1; // y = fib(N-n+1)
while (n != 0)
{
    if ((n % 2) == 0)
    {
        long p = a; // p = a
        long q = b; // q = b
        a = p * p + q * q;
        b = p * q + q * p + q * q;
        n /= 2;
    }
    else
    {
        // (n % 2) == 1
        long p = x; // p = x
        long q = y; // q = y
        x = a * p + b * q;
        y = b * p + a * q + b * q;
        n--;
    }
}
// n = 0, so x = fib(N)
return x;

Nu nog even BigInteger gaan gebruiken tegen de overflow et voila.

[Glimi]

-NMe- schreef op vrijdag 01 juli 2005 @ 04:04:
Door dit te doen bereken je elk getal in de rij (behalve fibo[0] en fibo[1]) twee keer. Wanneer je tussendoor alles opslaat in een lijstvorm of tussenvariabele hoef je niet telkens getallen te berekenen die je al berekend hebt.

Dit is juist een schoolvoorbeeld van dynamisch programmeren , fibo[i -1] en fibo[i-2] zijn gewoon lookups in een array welke al bekend is en dus niet uitgerekend hoeven te worden.
Trouwens, dit zou ook kunnen dmv 3 variabelen ipv een long[1000], dat scheelt geheugen, maar kost je extra kopieeracties.
_{zoals IcemanX het beschrijft dus}

[ Voor 4% gewijzigd door Glimi op 01-07-2005 09:33 ]

[MSalters]

Kopieeracties zijn niet nodig als je een loop-unroll doet en het 3 keer uitschrijft:

code:

c = b + a
a = b + c
b = a + c

[Glimi]

MSalters schreef op vrijdag 01 juli 2005 @ 10:06:
Kopieeracties zijn niet nodig als je een loop-unroll doet en het 3 keer uitschrijft:

code:

c = b + a
a = b + c
b = a + c

True, maar echt doorzichtiger wordt het er niet echt op, aangezien je 3 stappen per iteratie gaat doen. Echter wel lekker efficiënt

[.oisyn]

Binet's fibonacci number formula:
         (1 + √5)ⁿ - (1 - √5)ⁿ
f(n) = -----------------------------
                (2ⁿ√5)

[ Voor 39% gewijzigd door .oisyn op 01-07-2005 10:54 ]

[T.T.]

.oisyn schreef op vrijdag 01 juli 2005 @ 10:51:
Binet's fibonacci number formula:
(1 + √5)ⁿ - (1 - √5)ⁿ
f(n) = -----------------------------
(2ⁿ√5)

Als je alleen het n-de Fibonnaci nummer wilt uitrekenen is dat inderdaad handig, als je echter de hele rij wilt uitrekenen, dan is dat minder handig omdat je per fibonnaci-nummer meer berekeningen doet. Alhoewel je natuurlijk het iets zou kunnen vereenvoudigen door:

      (1.6180339...)[sup]n[/] - (–0.6180339...)[sup]n[/]
f(n) = -----------------------------
                 2.236067977...

Je krijgt dan wel met afrondingsfouten te maken, maar omdat je weet dat je altijd een Integer moet krijgen, kun je dat wel afronden zonder problemen.

Van het feit dat je toch te maken hebt met Integers, kun je nog meer gebruik maken, door een benadering te geven:

                 (1.6180339...)[sup]n[/] 
f(n) =round( ------------------------)
                     √5

(wel met n>0 natuurlijk) en die 1.6180339... is eigenlijk (1+√5)/2

[ Voor 52% gewijzigd door T.T. op 01-07-2005 12:01 ]

[.oisyn]

T.T. schreef op vrijdag 01 juli 2005 @ 11:47:
Je krijgt dan wel met afrondingsfouten te maken, maar omdat je weet dat je altijd een Integer moet krijgen, kun je dat wel afronden zonder problemen.

Het probleem is echter dat je met doubles nog minder ver komt dan met longs (53 bits precisie van een double vs 64 bits precisie van een long). Ik gaf de formule dus ook niet als manier om het probleem van de topicstarter op te lossen, maar om de al aangedragen methodes om het uit te rekenen aan te vullen.

[ Voor 7% gewijzigd door .oisyn op 01-07-2005 12:11 ]

[NMe]

Glimi schreef op vrijdag 01 juli 2005 @ 09:32:
Dit is juist een schoolvoorbeeld van dynamisch programmeren.

Woeps, ik was er met mijn hoofd niet helemaal bij, je hebt gelijk.

[Janoz]

T.T. schreef op vrijdag 01 juli 2005 @ 11:47:
(wel met n>0 natuurlijk) en die 1.6180339... is eigenlijk (1+√5)/2

Ook wel als φ(phi) of gulden snede

[Verwijderd]

ik heb dit gedaan

/**
* bereken het aantal konijnen
*/
public void berekenAantalKonijnen(int maand)
{
int index = 1;
int index2 = 1;
int index3 = 1;
while(index3<maand) {
index = index2 + index;
index2 = index - index2;
index3++;
}
if (index3>=maand) {
System.out.println(index2);
}
}

[RobIII]

Geweldig, maar om daar een topic uit 2005 voor te schoppen...