✳flâneur — a map of the web's best reading

Binary Exponentiation - Algorithms for Competitive Programming

cp-algorithms.com · 2,345 words · saved by 1 readers

Binary exponentiation (also known as exponentiation by squaring) is a trick which allows to calculate     𝑎 𝑛 <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>a</mi><mi>n</mi></msup></math> $a^n$  using only     𝑂 ( log ⁡ 𝑛 ) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>log</mi><mo data-mjx-texclass="NONE">⁡</mo><mi>n</mi><mo stretchy="false">)</mo></math> $O(\log n)$  multiplications (instead of     𝑂 ( 𝑛 ) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></math> $O(n)$  multiplications required by the naive approach). It also has important applications in many tasks unrelated to arithmetic, since it can be used with any operations that have the property of associativity: Most obviously this applies to modular multiplication, to multiplication of matrices and to other problems which we will discuss below. Raising     𝑎 <math xmlns="http://www.w3.org/1

Last update: June 10, 2026 &emsp; Translated From: e-maxx.ru Binary Exponentiation &para; Binary exponentiation (also known as exponentiation by squaring) is a trick which allows to calculate $a^n$ , where $n$ is a non-negative integer, using only $O(\log n)$ multiplications (instead of $O(n)$ multiplications required by the naive approach). It also has important applications in many tasks unrelated to arithmetic, since it can be used with any operations that have the property of associativity : $$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)$$ Most obviously this applies to modular multiplication

Explore this link on the map →

saved by

related reading