Square-and-multiply

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Square-and-multiply je algoritmus pro mocnění čísel pomocí převodu z desítkové do binární soustavy.

Příklad:
Máme spočítat 510. Desítka je v binární soustavě je 1010.

  • Při každém kroku algoritmu se číslo umocní na druhou (základ dvojkové soustavy);
  • začíná se s číslem x, které je rovno mocněnému číslu (0. krok);
  • pokud je v mocnině 1, pak se číslo nejen mocní na základ, ale i násobí původním mocněným číslem.

1: 5
0: x2 = 25
1: x2 · 5 = 625 · 5 = 3125
0: x2 = 9 765 625

510 = 9 765 625

Odkazy[editovat | editovat zdroj]