BinaryExponentiation [二分求幂]

# 介绍

在数学和程序设计中，平方求幂（英语：exponentiating by squaring）或快速幂是快速计算一个数（或更一般地说，一个半群的元素，如多项式或方阵）的大正整数乘幂的一般方法。这些算法可以非常通用，例如用在模算数或矩阵幂。对于通常使用加性表示法的半群，如密码学中使用的椭圆曲线，这种方法也称为 double-and-add。

# 实现

# JavaScript

迭代法:

// To calculate x^n i.e. exponent(x, n) in O(log n) time in iterative way
// n is an integer and n >= 0

// Explanation: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

// Examples:
// 2^3 = 8
// 5^0 = 1

// Uses the fact that
// exponent(x, n)
//          = exponent(x*x, floor(n/2))   ; if n is even
//          = x*exponent(x*x, floor(n/2)) ; if n is odd
const exponent = (x, n) => {
  let answer = 1
  while (n > 0) {
    if (n % 2 !== 0) answer *= x
    n = Math.floor(n / 2)
    if (n > 0) x *= x
  }
  return answer
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

递归法:

/*
  Modified from:
    https://github.com/TheAlgorithms/Python/blob/master/maths/binary_exponentiation.py

  Explanation:
    https://en.wikipedia.org/wiki/Exponentiation_by_squaring
*/

const binaryExponentiation = (a, n) => {
  // input: a: int, n: int
  // returns: a^n: int
  if (n === 0) {
    return 1
  } else if (n % 2 === 1) {
    return binaryExponentiation(a, n - 1) * a
  } else {
    const b = binaryExponentiation(a, n / 2)
    return b * b
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 参考

编辑

上次更新: 2022/10/18, 22:58:49

← AverageMedian [中位数] BisectionMethod [二分法]→