Fast Exponentiation

释义 Definition

“快速幂”（fast exponentiation）是一种高效计算 \(a^n\) 的算法思想，通常通过“反复平方/二分指数”（exponentiation by squaring）把时间复杂度从朴素的 \(O(n)\) 降到 \(O(\log n)\)。在需要计算大指数或模幂（如 \(a^n \bmod m\)）时尤其常用。

发音 Pronunciation

IPA: /fæst ɪkˌspoʊnənʃiˈeɪʃən/

例句 Examples

We used fast exponentiation to compute \(2^{100}\) quickly.
我们用快速幂来快速计算 \(2^{100}\)。

In cryptography, fast exponentiation is essential for efficiently computing modular powers like \(a^b \bmod n\) with very large \(b\).
在密码学中，快速幂对于高效计算像 \(a^b \bmod n\) 这样指数 \(b\) 非常大的模幂运算至关重要。

词源 Etymology

fast 意为“快速的”，来自古英语 fæst（稳固、牢固，引申为迅速、紧凑地进行）。exponentiation 意为“幂运算”，源自 exponent（指数），而 exponent 来自拉丁语 exponere（“展示、提出”），后来在数学中指“表示幂的指数”。“fast exponentiation”作为术语主要在计算机科学语境中指“用更少步骤完成幂运算”的方法。

相关词 Related Words

• Algorithm
• Binary Exponentiation
• Complexity
• Exponent
• Exponentiation
• Modular Arithmetic
• Modular Exponentiation
• Power
• Recursion

文学与名著用例 Literary Mentions

• Introduction to Algorithms（CLRS，《算法导论》）：在幂运算/递归与分治思想、以及相关实现（如模幂）讨论中常会提到“exponentiation by squaring”（快速幂思想）。
• Donald E. Knuth, The Art of Computer Programming（《计算机程序设计艺术》）：在数值计算与算法技巧相关内容中涉及高效幂计算的经典方法。
• Graham, Knuth, Patashnik, Concrete Mathematics（《具体数学》）：在递推、对数级复杂度与幂相关的数学工具背景下可见相关讨论与应用。