Den såkalte russiske multiplikasjonsteknikken består i å dividere multiplikatoren med 2 (og deretter oppnådde kvotienter), til en nullkvotient, og i å merke resten. og multipliserer multiplikalen parallelt med 2. Vi legger deretter til multiplene oppnådd fra multiplikatoren som tilsvarer resten som ikke er null.
Dette er faktisk det samme som å skrive multiplikatoren i base 2 og deretter gjøre multiplikasjoner med 2 og tillegg. Det er derfor en variant av multiplikasjonsteknikken i det gamle Egypt , selv om den kunne gjenoppdages uavhengig.
I pseudokode kan den såkalte russiske multiplikasjonsalgoritmen skrives:
Merk: operasjonene som utføres her er operasjoner på heltall og har verdier i heltall.
13 x 238 skriver vi
13/2 = kvotient 6 forblir 1, | 238, | 238 |
6/2 = kvotient 3 forblir 0, | (476 for ordens skyld), | 238 |
3/2 = kvotient 1 forblir 1, | 952, | 1190 |
1/2 = kvotient 0 forblir 1, | 1904 (stopp: kvotienten er null), | 3094 |
13 × 238 = | 3094 |
13 = 1101 i base 2 (oppnådd ved å lese resten fra bunnen til toppen i tabellen, og skrevet i henhold til vanlig konvensjon av høyre - enheter - til venstre - høye krefter).
For å begrense antall operasjoner er det vanligvis nødvendig å velge som multiplikator det minste av de to tallene som skal multipliseres. Imidlertid, hvis en av dem er en styrke på 2, er det heller han som bør foretrekkes (det er ingen tillegg). Resten blir nødvendigvis null, og derfor blir resultatet stabilt, fra det øyeblikket kvotienten i seg selv er null. Formelt sett er derfor stopptilstanden (stopp når kvotienten er null) bare en bekvemmelighet.
Grafisk kan vi si at en multiplikasjon forvandler et multiplikator x multiplikat- rektangel til en linje ved å beholde antall elementer.
Den grafiske algoritmen består for russisk multiplikasjon i:
Den såkalte russiske multiplikasjonsteknikken er veldig relatert, matematisk, til den raske eksponentieringsalgoritmen , og kan sees på som en "additiv" versjon av sistnevnte. Faktisk gjør den såkalte russiske multiplikasjonsteknikken det mulig å beregne, for ethvert heltall k og element g av et additivt monoid , elementet (tillegg av k- termer) mens den raske eksponentieringsalgoritmen gjør det mulig å beregne, for ethvert heltall k og element g av en multiplikativ monoid , elementet (multiplikasjon av k- termer). Med andre ord, uttrykt på språket til monoider, er disse to algoritmene strengt identiske.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">