russisk bondemultiplikasjon

[pippi]

Dette er en liten ting jeg lurer på.
du skal multiplisere to tall f.eks. 24*36
algoritmen er slik at du halverer venstre side og dobler høyre:
12*72
6*144
3*288
1*576 (når man får ,5 runder man av nedover)
så stryker man alle tall der det er partall på venstre side. i dette tilfelle står vi igjen med: 3*288
1*576 til slutt summerer vi tallene på høyre side.
det blir : 864

ergo:24*36=864. Nå kan du prøve med hvilke tall du vil- litt tungvint kanskje, men for en som bare kan doble, halvere og legge sammen er det en fin metode. Nå mitt problem: hvorfor funker dette? Hva er hemmeligheten? Hilsen pippi.

[oro2]

På denne siden er det beskrevet hvorfor det virker, og hvordan det henger sammen med binære tall.
http://mathforum.org/dr.math/faq/faq.peasant.html


PS:

(...) men for en som bare kan doble, halvere og legge sammen er det en fin metode.

En enkel ALU (enheten som utfører logiske og aritmetriske beregninger i en datamaskin) kan faktisk bare dette. Datamaskiner regner med binære tall. Et binært tall kan du multiplisere med 2 ved å flytte alle sifrene(bits) et hakk til venstre, og dividere på to ved å flytte til høyre, forutsatt at ingen 1'ere faller ut. Også kalt "skiftoperasjon". Adderingen går greit, det er bare liten krets av logiske porter.
eks: 01001[sub]2[/sub]*10[sub]2[/sub]=10010[sub]2[/sub]