[Contest] Rij van Fibonacci

[kutkip]

Deze contest bestaat uit het berekenen van de rij van Fibonacci. Klik hier om meer te lezen over Fibonacci.

Dit is een rekenmachine die in staat is de rij van Fibonacci te berekenen en het is te gebruiken als benchmark.
Uiteraard is het voor ons tweakers interressant om te zien welke processoren en/of moederbord/geheugen combinaties het goed doen in zulke testen.

Het programma is hier te vinden:
De rekenmachine

Mijn voornemen is om twee metingen te verrichten.
De instellingen dienen te zijn:

Fibonacci(i) -> Exact(slower) -> From i=1 -> To i=2000

én:

Fibonacci(i) -> Exact(slower) -> From i=1 -> To i=1000

Helaas is er geen automatische tijdswaarneming dus zul je het met een stopwatch je metingen moeten verrichten. We gaan er dus vanuit dat daar geen misbruik van wordt gemaakt. Dat zou ronduit kinderachtig zijn en wordt niet gewaardeerd.

Post in de comments de tijd die je hebt behaald en natuurlijk de hardware waarmee je dat hebt gedaan.

Voorbeeld:

Mijn Tijd:

1 t/m 2000 = ...

1 t/m 1000= 1.26

Mijn Hardware:

CPU: Intel Xeon 2.8 Ghz

RAM: 1024MB RAM PC 3200 Cas3 Kingston

Moederbord: Asus NCCH-DL

succes

[ Voor 4% gewijzigd door kutkip op 08-01-2006 17:55 ]

[_Ernst_]

Mij lijkt het slimmer om met wat grotere waardes te benchen, want tiende van secondes zijn vrijwel niet bij te houden met de hand, en al helemaal niet als je ze ook nog met elkaar wil vergelijken.
Probleem is alleen dan als ik 100000 doe, Firefox dan na 10 seconde een popup geeft die je weer weg moet klikken...

Dus als je toch een indicatie wil hebben zou ik eens benchen met waardes als 20000 of 50000

[Henk007]

Het lijkt me niet slim om dit zo te gaan benchen. Ten eerste zit je vooral java overhead te benchen en ten tweede heb je geen betrouwbare tijdwaarneming.
Beter is om een simpel progje a la superpi in elkaar te zetten en het daarmee te gaan doen. Tevens kun je dan optimaal gebruik maken van compiler optimalisaties. Ik neem aan dat de source van de core berekening wel ergens vrij te verkrijgen is.
Overigens stelt de berekening geen ruk voor:

code:

unsigned long fib(x)
long x;
{
 if (x > 2)
  return(fib(x-1)+fib(x-2));
 else
  return(1);
}

Alleen moet je dan wel gebruik maken van string arithmetics, omdat het niet in long integers past.

[ Voor 25% gewijzigd door Henk007 op 08-01-2006 18:02 ]

[kutkip]

Ik ga i=500 vervangen door i=2000. Echter grotere waardes dan 2000 is volgens de auteur niet aan te raden wegens mogelijke problemen. En je zult inderaad met Internet Explorer de metingen moeten verrichten omdat Firefox de boel onderbreek

[Verwijderd]

Henk007 schreef op zondag 08 januari 2006 @ 17:54:
Overigens stelt de berekening geen ruk voor:

Deze code is verre van efficient; het kan in O(log N), met N-de fib. getal. Pseudocode (zonder garantie van correct overtypen):

code:

int fibonacci(int N)
{
  int a = 0; int b = 1; int x = 0; int y = 1; int n = N;
  while (n <> 0) 
  {
    if (n mod 2 = 0) 
    {
      a = a^2+b^2; b = 2*a*b+b^2; n = n div 2;
    }
    if (n mod 2 = 1)
    {
      x = a*x+b*y; y = b*x+a*y+b*y; n = n-1;
    }
  }
  return x;
}

bron: isbn: 0-13-204108-1

Overigens moet je met deze code nog grotere getallen gaan uitrekenen om een fatsoenlijke benchmark te krijgen.

Bij de voorgestelde code moet er wel rekening mee worden gehouden dat het zo zou kunnen zijn dat recursie-stacks bij verschillende implementaties een performance verschilkan opleveren bij gelijke hardware. Bij deze code is dat niet.

[ Voor 89% gewijzigd door Verwijderd op 08-01-2006 18:23 ]

[Marcel_23]

Verwijderd schreef op zondag 08 januari 2006 @ 18:05:
[...]

Deze code is verre van efficient; het kan in O(log N), met N-de fib. getal.
[...]

Overigens moet je met deze code nog grotere getallen gaan uitrekenen om een fatsoenlijke benchmark te krijgen.

Aangezien dit algoritme logaritmisch is, heeft het totaal geen zin om grotere getallen te gaan gebruiken. Een getal dat twee keer zo groot is resulteert voor dit algoritme in slechts één extra bewerking, dus een getal dat ongeveer een miljoen keer zo groot is zorgt voor slechts 20 extra bewerkingen. Dit aantal extra bewerkingen is op een moderne processor in tijd verwaarloosbaar dus absoluut niet nuttig als benchmark.

[ Voor 1% gewijzigd door Marcel_23 op 09-01-2006 08:28 . Reden: typo ]

[AtleX]

Er is al een Benchmark applicatie die gebasseerd is op de rij van Fibonnacci: Fi-Bench. Er is ook al een topic over, die gaat voornamelijk over multi-core/multi-cpu systemen, maar versie 4.0.0.41 (de meest recente) heb ik ook geschikt gemaakt voor single CPU PC's.

[BalusC]

Ik stel voor om dat tooltje van AtleX te gaan gebruiken Deze is ook wat handiger en betrouwbaarder qua uitvoering