De manier waarop de meeste mensen grote natuurlijke getallen hebben leren vermenigvuldigen, ziet er ongeveer als volgt uit
57 × 86 ------- 342 + 456 ------- 4902
Als je de tafels van vermenigvuldiging van buiten kent, dan is deze zogenaamde lange vermenigvuldiging snel en relatief eenvoudig te berekenen.
Er bestaan echter nog tal van andere manieren om te vermenigvuldigen. Een van deze methoden staat bekend als het Russische boerenalgoritme. Om een vermenigvuldiging uit te voeren volgens deze methode heb je de tafels van vermenigvuldiging niet nodig. Je moet enkel getallen kunnen verdubbelen, halveren en optellen. Het algoritme van de Russische boeren gaat als volgt:
Schrijf de twee getallen die moeten vermenigvuldigd worden aan het hoofd van twee kolommen.
Verdubbel telkens het getal in de eerste kolom en halveer het getal in de tweede kolom. Als het getal in de tweede kolom oneven is, deel het dan door twee en laat de rest vallen.
Doorstreep de volledige rij als het getal in de tweede kolom even is.
Blijf verdubbelen, halveren en doorstrepen totdat het getal in de tweede kolom gelijk is aan 1.
Tel de niet-doorstreepte getallen uit de eerste kolom bij elkaar op. Deze som levert het product op van de twee originele getallen.
Hieronder wordt de volledige vermenigvuldigingstabel getoond die volgt uit het Russische boerenalgoritme wanneer we het gebruiken om de getallen 57 en 86 met elkaar te vermenigvuldigen. We schrijven eerst de getallen 57 en 86 als hoofding van twee kolommen. Omdat het getal in de tweede kolom in dit geval even is, doorstrepen we de volledige rij. Daarna verdubbelen we 57 tot 114 en halveren we 86 tot 43. We blijven verdubbelen, halveren en doorstrepen totdat het getal in de tweede kolom gelijk is aan 1. De som van de niet-doorstreepte getallen uit de eerste kolom levert het product van de vermenigvuldiging op.
57 86 114 43 228 21 456 10 912 5 1824 2 + 3648 1 ---------- 4902
Er wordt beweerd dat deze methode nog steeds gebruikt wordt door boeren in sommige gebieden binnen Rusland. Wat er ook van zij, het blijft gissen naar de oorsprong van de boerenvermenigvuldiging. Mogelijk gaat ze terug naar een eeuwenoud Russisch boek waarin de methode voor het eerst wordt beschreven in de (relatief) moderne tijd. De verwijzing naar Rusland in de naam van het algoritme slaat vermoedelijk op de Russische vertaling ervan in dit boek, terwijl de verwijzing naar de boeren vermoedelijk werd toegevoegd door het feit dat algemeen werd aangenomen (in ieder geval in vroegere tijden) dat het Russische grondgebied bijna uitsluitend door boeren werd bevolkt. Zij het dan zeer dunnetjes.
Het zou even goed kunnen dat de methode zijn oorsprong vind in de Oud-Egyptische wiskunde, aangezien een soortgelijke procedure gebruikt wordt in de Rhind-papyrus1. De methode wordt soms ook de Ethiopische (boeren)vermenigvuldiging genoemd, omdat deze twee volkeren in elkaars nabijheid woonden en heel wat culturele uitwisseling vertoonden.
Twee getallen $$m, n \in \mathbb{N}_0$$, elk op een afzonderlijke regel.
De opeenvolgende regels die geproduceerd worden door $$m$$ en $$n$$ met elkaar te vermenigvuldigen volgens het Russische boerenalgoritme. Elke regel moet twee getallen bevatten die van elkaar worden gescheiden door een spatie. Het is niet nodig om aan te geven welke regels moeten doorstreept worden.
Als laatste regel moet het product van $$m$$ en $$n$$ uitgeschreven worden. Hierbij is het niet toegelaten om in je broncode een vermenigvuldiging van de twee getallen uit te voeren. Je moet dus de som berekenen van de niet doorstreepte getallen uit de eerste kolom.
Invoer:
57
86Uitvoer:
57 86
114 43
228 21
456 10
912 5
1824 2
3648 1
4902