\require{AMSmath}

Efficient delen

Hallo,

Bij een staartdeling deel je door steeds (veelvouden van) de noemer van de teller af te trekken. Als de noemer heel groot en de teller heel klein is, duurt dat echter relatief lang.

Is er een algoritme dat dit efficiënter zou kunnen doen? Het hoeft niet door mensen gebruikt te worden, maar door computers, dus het mag complex zijn, als het aantal handelingen maar beperkt is.

Vincen
Leerling bovenbouw havo-vwo - maandag 16 januari 2006

Antwoord

Het antwoord op je vraag is afhankelijk van het feit of je een 'floating point' algoritme wilt hebben of een voor 'integer division'.

Voor floating-point is het volgende algoritme wel aardig.
Veronderstel dat je 3/1124 wilt benaderen.

Doe nu het volgende:

Kies startgetal x₁=1/1000=0.001 (dus vervang 1124 door 1000)
Bereken nu herhaald x_n+1=2·x_n-1124x_n²
Op je rekenmachine gaat dit heel aardig zo:
Toets in: 0.001 ENTER.
2·Ans-1124·Ans²
Druk nu een aantal keren op ENTER.

Na een paar keer drukken op ENTER heb je het getal 8.896797153E-4 gevonden.

Dit is een benadering van 1/1124. (Controleer maar).
Dan nog even vermenigvuldigen met 3 en je hebt 3/1124.

Het leuke van dit algoritme is dat je alleen maar vermenivuldiging, aftrekken (en kwadrateren) hoeft te implementeren om de deling te kunnen definieren. (plus een slimme manier om het startgetal te bepalen))

Voor 'multiple length integer division' ligt het wat complexer.

hk
maandag 23 januari 2006

©2001-2024 WisFaq