Binär exponentiering

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif
icon_anmal.gif
rp-wp-sv.gif

Binär exponentiering är en algoritm för att beräkna heltalspotenser, multiplikation av ett tal med sig självt ett antal gånger, på ett effektivt sätt. Idén är att utnyttja exponentens binära representation för att reducera förfarandet till en serie kvadreringar och multiplikationer.

Algoritmen kan beskrivas på rekursiv form av

\mbox{potens}(x,\,n)=\left\{ \begin{matrix} x, & \mbox{om }n\mbox{ = 1} \\ \mbox{potens}(x^2,\,n/2), & \mbox{om }n\mbox{ jamnt} \\ x\times\mbox{potens}(x^2,\,(n-1)/2), & \mbox{om }n >\mbox{2 udda}. \\ \end{matrix}\right.

Antalet multiplikationer som krävs är av storleksordningen O(log n), vilket då exponenten är stor gör metoden oerhört mycket mer effektiv än direkt upprepad multiplikation. Till exempel krävs endast 25 multiplikationer för att med denna metod beräkna 101000000, 10 gånger sig självt en miljon gånger.

Algoritmen används med fördel för att beräkna modulära potenser, en tillämpning som har betydelse inom kryptografi.

Hämtad från "https://sv.rilpedia.org/wiki/Bin%C3%A4r_exponentiering"
Personliga verktyg