In het oude Egypte werden (enkel positieve gehele) getallen genoteerd met symbolen. Optellen, aftrekken, verdubbelen en halveren kan je daarmee vrij makkelijk uitvoeren. Vermenigvuldigen van twee getallen was echter helemaal niet evident. Hiervoor werd volgende methode ontwikkeld, dat in de afbeelding links getoond wordt voor 11 x 17: Splits het eerste getal op in een som van machten van 2: 11 = 1 + 2 + 4 + 8 Verdubbel het tweede getal in elke stap: 17 --- 34 --- 68 --- 136 Omdat 11 de som is van de vier eerste machten van 2, bekom je het product als de som: 17 + 34 + 68 + 136 = 187 Hoe kan je hiermee 9 x 17 berekenen? Omdat 9 = 1 + 8 sommeer je enkel 17 + 136 = 153.

Het algoritme:

Deze Egyptische vermenigvuldiging (ook bekend als Russische boerenvermenigvuldiging) wordt praktisch als volgt uitgewerkt:

Om a * b te berekenen maak je drie kolommen en schrijf de waarden a en b in de eerste, resp. derde kolom (het voorbeeld toont a=11 en b=17). Deel het getal in eerste kolom steeds door twee. De restwaarde (0 of 1) komt in de tweede kolom. Verdubbel tegelijkertijd in elke rij het getal in derde kolom. Doe dit tot je bij 1 uitkomt. Schrap alle rijen waarin het getal in de tweede kolom een nul is (dit komt neer op het schrappen van alle rijen waarin het getal in de eerste kolom even is.) Tel de overgebleven getallen in de laatstekolom bij elkaar op. Dit is het eindresultaat van a * b.

a % 2 b 11 1 17 5 1 34 2 0 68 1 1 136 a * b = 187

Link met de binaire notatie

Uit de tweede kolom kan je nu onmiddellijk de binaire weergave van a afleiden: lees hiervoor de kolom van onder naar boven.
De binaire weergave van 1110 = 1011₂ (wat staat voor 8 + 2 + 1).
Dit betekent dat we eigenlijk (1 + 2 + 8) × 17 hebben uitgerekend.

Opdracht

In het hoofdprogramma lees je twee positieve gehele getallen in (je moet dit niet controleren).
Bereken het product van die twee getallen zonder ergens * te gebruiken (dit wordt gecontroleerd in Dodona!).
Schrijf het product naar het scherm.