Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

Delen door 13 voor gevorderden


In Trivia, door Ionica

Ernst (één van de heren achter wiskundesletjes.nl, maar dat terzijde) wees me op een gave truc om snel te delen bij programmeren. Ik was zelf nooit een goede, elegante programmeur (brute force is my middle name), maar ik herinner we wel dat delen meer tijd kost dan vermenigvuldigen. Dus als je delen op de een of andere manier kunt vervangen door vermenigvuldigen, dan wordt je programma sneller.


ridiculousfish

Op Ridiculous Fish Blog staat een prachtig stuk over delen door 13.

Stel dat je een of andere geheel getal wilt delen door 13 en dat programmeert in C. De compiler code doet dan iets geks, namelijk vermenigvuldigen met 1321528399 (en daarna nog wat andere dingen). Zoals de scherpe lezer nu zal opmerken, is delen door 13 niet hetzelfde als vermenigvuldigen met 1321528399.

Echter: vermenigvuldigen met 1321528399 en daarna delen door \(\) (en bedenk dat delen door 2 makkelijk is, dat is een bitshift) is hetzelfde als delen door 12,9999999977299... En dat lijkt dan weer heel erg op 13.

Lees op Ridiculous Fish Blog een mooie, intuïtieve uitleg waarom de afronding altijd goed gaat. Of koop gelijk Hacker's Delight, het boek waar deze truc al veel eerder stond. Dit is trouwens verder geen speciale eigenschap van 13, voor andere delers kun je ook een getal vinden om mee te vermenigvuldigen (en bitshiften).

8 reacties op “Delen door 13 voor gevorderden”

  1. Rogier:

    Ik las laatst op Wikipedia, over de geschiedenis van logaritmen
    http://en.wikipedia.org/wiki/Logarithm#History
    de uitspraak :
    "Since (1 − 10^(−7))^(10^7) is approximately 1/e, ..."
    dus dat Napier's logaritmen vrijwel equivalent zijn aan onze huidige conventie (op teken na en de komma zeven plaatsen schuiven). Ook leuk, maar hoe kom je er op?

  2. Aldo:

    Over brute kracht gesproken: http://tiny.cc/brute145

  3. Rene:

    @Rogier: Dat is een simpel gevolg van de gelijkheid

    \[\]


    Vul \(\) in en je ziet dat als n een niet te klein getal is, zoals 10000000,

    \[\]

  4. (andere) Rene:

    @Aldo: die slogan is erg mooi! :)

  5. Johan:

    Als programmeur wil ik wel zeggen dat als je dit soort trucs in je code toepast, je aardig wat strafpunten verdient.

    Je moet wel ontzettend vaak door 13 delen om dit soort onduidelijke trucs te rechtvaardigen. Het is meer macho-vertoon: kijk ik eens slim zijn.

    Ik vind dat je bij het schrijven van programmacode niet de communicatie met de computer in je achterhoofd moet houden maar de communicatie met degene die na jou de code gaat bekijken. Bijv. je zelf een half jaar later.

    Dat compilers dit soort trucs toepassen: OK. Daar heb ik geen last van.

  6. HJ:

    Een beroemd verhaal over "trucs" die in programma's worden toegepast gaat over de code van Morris, één van de ontdekkers van het algoritme van Knuth-Morris-Pratt. Zijn slimme vondst (in 1967, om te zoeken zonder in de tekst terug te hoeven springen) werd niet begrepen met als gevolg dat de code later terug-verbeterd werd.
    Zelf deel ik gewoon door 13. Ik ben nog uit de tijd van de staartdeling.

  7. Johan:

    Over hoeveel % tijdsverschil spreken we dan?

    PS: niet dezelfde Johan als hierboven ;)

  8. Rogier:

    Dank Rene, daar had ik niet aan gedacht. Helder!

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.