De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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.

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
maandag 23 januari 2006



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3