From 89a95f29c9b596050c3fa30d874c167ea6145313 Mon Sep 17 00:00:00 2001 From: muqiuhan Date: Sat, 21 Oct 2023 00:04:50 +0000 Subject: deploy: f3d97131fc06f173950171c7c4973679948aa930 --- .../index.html" | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to '2023/10/21') diff --git "a/2023/10/21/OCaml-Core-Int-pow-\347\232\204\345\256\236\347\216\260/index.html" "b/2023/10/21/OCaml-Core-Int-pow-\347\232\204\345\256\236\347\216\260/index.html" index 808ab9ca..633c9886 100644 --- "a/2023/10/21/OCaml-Core-Int-pow-\347\232\204\345\256\236\347\216\260/index.html" +++ "b/2023/10/21/OCaml-Core-Int-pow-\347\232\204\345\256\236\347\216\260/index.html" @@ -175,6 +175,22 @@

其实现在 src/int_math_stubs.c 中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int64_t int_pow(int64_t base, int64_t exponent) {
  int64_t ret = 1;
  int64_t mul[4];
  mul[0] = 1;
  mul[1] = base;
  mul[3] = 1;

  while (exponent != 0) {
    mul[1] *= mul[3];
    mul[2] = mul[1] * mul[1];
    mul[3] = mul[2] * mul[1];
    ret *= mul[exponent & 3];
    exponent >>= 2;
  }

  return ret;
}
+

这是一个四分快速幂的实现，它是二分快速幂的一种变种。二分快速幂将指数分为两部分，然后递归地计算每一部分的结果。
而四分快速幂将指数分为四部分，然后递归地计算每一部分的结果。
这里通过将指数右移2位（相当于除以4）和使用位与操作来实现，进一步减少了乘法次数。

+

主要步骤：

+ +

这个实现的优点是它可以在对数时间内计算出幂运算，而且每次循环只需要4次乘法。这比标准的二分快速幂算法需要的乘法次数更少。

-- cgit v1.2.3