Ik ben gisteravond iets tegengekomen wat ik niet kan verklaren. Ik ben met een parser bezig voor een rekenmachine, en ik moest even snel een functie schrijven voor faculteiten. Dit is wat ik toen even snel had verzonnen:
Een vriend van mij kwam toen met het idee om een recursieve functie te gebruiken, en schreef daar even de code voor. Ik was wel benieuwd welke code sneller is, dus ik zette even snel een benchmark inelkaar. Mijn functie won het, maar ik kwam tegelijk een fout in de uitkomsten tegen. Ik heb hem uiteindelijk verbeterd door de for-lus om te draaien. Hier de functies van die vriend van mij en mijn wel goed werkende functie:
Het interessante is dat alle drie de functies bij 5! nog het juite antwoord geven. Pas bij een bepaald getal gaat die bovenste functie de mist in. Voorbeeld wat ik toevallig nog in een msn log heb staan:
Volgens Windows Calculator: 55! = 1,2696403353658275925965100847567e+73
Oude functie: 1.2696403353658264E+73
Nieuwe/recursieve functie: 1.2696403353658276E+73
Daar is mijn oude functie dus fout, en mijn nieuwe goed. De recursieve en de nieuwe functie vermenigvuldigen van laag naar hoog(1 naar 55 in dit voorbeeld), mijn oude functie van hoog naar laag(55 naar 1), daar ligt dus ook de "fout". Ik vermoed dat dit te maken heeft met de onnauwkeurigheid in floating points, toch vind ik het raar. Die onnauwkeurigheid zou toch in beide richtingen moeten voorkomen? Wat maakt het nou uit of ik 1*2*3*...119*120 doe of ik 120*119*118*...2*1 doe?
Wie kan mij hier meer over vertellen? Ik heb zelf alleen maar informatica op de middelbare school gevolgd(1 week afgesloten
), daar zijn dit soort dingen nooit aan bod gekomen.
Visual Basic .NET:
1
2
3
4
5
6
7
8
9
10
11
| Public Shared Function Faculty(ByVal Value As Integer) As Double 'We moeten ons aan de regeltjes houden If Value = 0 Then Return 1 Dim Out As Double = -1 For a As Integer = Value To 1 Step -1 If Out = -1 Then Out = a Else Out *= a Next Return Out End Function |
Een vriend van mij kwam toen met het idee om een recursieve functie te gebruiken, en schreef daar even de code voor. Ik was wel benieuwd welke code sneller is, dus ik zette even snel een benchmark inelkaar. Mijn functie won het, maar ik kwam tegelijk een fout in de uitkomsten tegen. Ik heb hem uiteindelijk verbeterd door de for-lus om te draaien. Hier de functies van die vriend van mij en mijn wel goed werkende functie:
Visual Basic .NET:
1
2
3
4
5
6
7
8
9
10
11
| Public Shared Function Faculty(ByVal Value As Integer) As Double 'We moeten ons aan de regeltjes houden If Value = 0 Then Return 1 Dim Out As Double = 1 For a As Integer = 1 To Value Out *= a Next Return Out End Function |
Visual Basic .NET:
1
2
3
4
5
6
| Public Function RecursiveFaculty(Byval Value As Double) As Double 'We moeten ons aan de regeltjes houden If Value = 0 Then Return 1 If Value = 1 then Return Value Else Return Value * RecursiveFaculty(Value-1) End Function |
Het interessante is dat alle drie de functies bij 5! nog het juite antwoord geven. Pas bij een bepaald getal gaat die bovenste functie de mist in. Voorbeeld wat ik toevallig nog in een msn log heb staan:
Volgens Windows Calculator: 55! = 1,2696403353658275925965100847567e+73
Oude functie: 1.2696403353658264E+73
Nieuwe/recursieve functie: 1.2696403353658276E+73
Daar is mijn oude functie dus fout, en mijn nieuwe goed. De recursieve en de nieuwe functie vermenigvuldigen van laag naar hoog(1 naar 55 in dit voorbeeld), mijn oude functie van hoog naar laag(55 naar 1), daar ligt dus ook de "fout". Ik vermoed dat dit te maken heeft met de onnauwkeurigheid in floating points, toch vind ik het raar. Die onnauwkeurigheid zou toch in beide richtingen moeten voorkomen? Wat maakt het nou uit of ik 1*2*3*...119*120 doe of ik 120*119*118*...2*1 doe?
Wie kan mij hier meer over vertellen? Ik heb zelf alleen maar informatica op de middelbare school gevolgd(1 week afgesloten
[ Voor 0% gewijzigd door Gimmeabrake op 09-04-2009 16:12 . Reden: typo ]