Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\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 x1=1/1000=0.001 (dus vervang 1124 door 1000)
Bereken nu herhaald xn+1=2·xn-1124xn2
Op je rekenmachine gaat dit heel aardig zo:
Toets in: 0.001 ENTER.
2·Ans-1124·Ans2
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