Fast exponentiation
Në shqip: Fuqizimi i shpejtë
ShpjegimiSQ
Për të llogaritur aⁿ, në vend që të shumëzosh a me veten n herë, e ngre në katror dhe e përgjysmon n-në — vetëm rreth log n hapa. Përdoret në kriptografi dhe gara, shpesh me modul: pow(a, n, m) në Python.
EnglishEN
To compute aⁿ, instead of multiplying a by itself n times, you square it and halve n — only about log n steps. It's used in cryptography and contests, often with a modulus: pow(a, n, m) in Python.
Si ta mendosh
Si palosja e një flete letre: çdo palosje e dyfishon trashësinë, dhe pas pak palosjesh është shumë e trashë.
Lexoje në anglisht
Like folding a sheet of paper: each fold doubles the thickness, and after a few folds it's very thick.
Shembull kodipython
def fuqi(a, n, r=1):
while n:
if n & 1: r *= a
a, n = a * a, n >> 1
return r