Bondemultiplikasjon

Dette er en metode for å multiplisere tall som bare forutsetter at du kan 2-gangen. Det omtales ofte som "russisk bondemultiplikasjon"

Vi skal altså utføre jobben P=AxB. Vi bruker betegnelsen multiplikand for A og multiplikator for B. Resultatet er produktet.

Vi ser på to enkle eksempler og forutsetter inntil videre (!) at vi kan 3-gangen og 4-gangen. Vi vet da fra grunnskolen at vi kan sette opp følgende for å utføre jobben: 

3 x 4
--------
  12
========

13 x 14
--------
    52
   13
--------
   182
========

Hvis vi skriver tallene som binærtall blir det slik: 

11 x 100
--------
    00
   00
  11
-------
  1100
========

1101 x 1110
------------
     0000
    1101
   1101
  1101
-----------
 10110110
===========

Hvis vi betrakter kolonnen som summeres for å få produktet ser vi at i den binære løsningen er hver rad enten 0 eller eller multiplikanden, tallet til venstre. Altså 1101 x 0 eller 1101 x 1. I begge tilfellene er tallet flyttet et siffer til venstre for raden over. Det vil si at det er ganget med 2. I vår desimale oppsett ganger vi med 10 når vi flytter taller et hakk til venstre. Tallet vi ganger med er er det siste tallet i halvparten av multiplikatoren, som jo er 0 eller 1.

Vi prøver å overføre det binære resonnementet til heltall. Det betyr at vi skulle kunne bruke en algoritme som lager to kolonner der vi plasserer det dobbelte av multiplikanden (venstre tall) til venstre og halvparten av multiplikator (høyre tall) til høyre. Når vi halverer et tall ignorerer vi desimaler. Kort sagt kan vi vel si at vi behandler desimaltallene som om de skulle vært binære.

Når vi skal finne produktet summere vi venstre kolonne og ignorerer tall som har et partall til høyre for seg.
Altså: 12=12 og 26 + 52 + 104 = 182 

3  4
6  2
12 1
--
12
==


13  14
26   7
52   3
104  1
---
182
===

Javascriptkode

En enkel Javascript-versjon av den algoritmen russiske bønder i følge historien har anvendt: 

function mult(A,B){
  var P=0;
  while(B >= 1){
    if(B%2 == 1)
      P+=A;
    A*=2;
    B=parseInt(B/2); // drop desimalene		
  }
  return P;
}

Test

Skriv inn de positive heltallene du vil multiplisere og "Start regning". Tar maks 3-sifrede tall av praktiske årsaker.

X