[VB.NET 2008] Faculteiten

[Gimmeabrake]

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:

Visual Basic .NET:

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:

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:

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 ), daar zijn dit soort dingen nooit aan bod gekomen.

[ Voor 0% gewijzigd door Gimmeabrake op 09-04-2009 16:12 . Reden: typo ]

[codeneos]

Probeer eens een long in plaats van een double. Het enigste wat ik zou kunnen bedenken is een afrondingsfout ergens met de double.

[Woy]

Als je "afrondingen" in een andere volgorde uitvoert, is het toch niet zo vreemd dat je een andere uitkomst krijgt?

stel je wilt 1.3 * 2.1 * 3.6 doen en je rond na elke bewerking af op 1 decimaal krijg je ook andere uitkomsten aan de hand van de volgorde

1.3 * 2.1 * 3.6 = 9.7
3.6 * 2.1 * 1.3 = 9.9

codeneos schreef op donderdag 09 april 2009 @ 16:16:
Probeer eens een long in plaats van een double. Het enigste wat ik zou kunnen bedenken is een afrondingsfout ergens met de double.

Een long introduceert natuurlijk weer het probleem dat je snel een overflow krijgt. Als de TS een BigInteger ( moet je even een implementatie zoeken, aangezien hij volgens mij nog niet standaard in het framework zit ) gebruikt zou hij wel de goede antwoorden moeten krijgen.

[ Voor 46% gewijzigd door Woy op 09-04-2009 16:23 ]

[RobIII]

Floats en afronding

In het eerste geval begin je met 55 * 54 * 43 etc... en in het andere geval begin je met 1 * 2 * 3 etc... nogal wiedes dat er dan verschillen ontstaan

[Gimmeabrake]

Hmm... ok. Ik zal zo eens kijken wat er met een long gebeurt. Wel interessant om hier eens kennis mee te maken. Had al heel vaak van dit soort issues gehoord maar er nog nooit echt last van gehad.