平方乘算法在 $\mathcal{O}(\log n)$（对数时间）内计算整数指数。计算指数 $x^n$ 的朴素方法是将 $x$ 自身相乘 $n$ 次，这需要 $\mathcal{O}(n)$ 的计算时间。

假设我们想计算 $x^{20}$。我们不是将 $x$ 与自身相乘 20 次，而是从 $x$ 开始不断进行平方，直到计算出 $x^{16}$：

观察到我们可以将 $x^{20}$ 计算为：

在代数中，指数以这种方式“相加”的性质被称为同底数幂相乘法则（product-of-powers rule）。

本文是 关于 Uniswap V3 代码库的系列文章 的一部分。Uniswap V3 使用平方乘算法将 tick 索引转换为平方根价格。不过，本文也适合任何想要了解平方乘算法工作原理的读者。

平方指数序列

在本文中，我们将多次使用“平方指数序列”（squared-exponents sequence）一词，即 $x^1,x^2,x^4,x^8,\dots$。每一项都是前一项的平方。底数 $x$ 可以是任何非零值。例如，$0.7^1,0.7^2,0.7^4,...$ 是一个有效的平方指数序列。同样，$-1.56,-1.56^2,...,-1.56^{32},-1.56^{64}$ 也是一个有效的平方指数序列。

小数底数的平方乘

如果我们提前知道底数是一个固定值，并且我们可能计算的指数有一个已知的上限，那么我们可以预先计算出平方指数序列，然后通过查表代替乘法。例如，如果我们想计算 $0.7^x$，并且提前知道 $x$ 不会大于 63，我们可以预先计算以下值：

那么，例如我们想计算 $0.7^{44}$，我们可以将平方指数序列中相应的预计算值相乘如下：

鼓励读者在计算器上重新计算 $0.7^{44}$ 以仔细核对。

当以这种方式缓存值时，我们必须提前知道我们的应用程序必须处理的指数上限。

带有分数指数的平方乘算法

假设我们不想计算 $0.7^x$，而是想计算 $\sqrt[3]{0.7^x}$？这等同于 $0.7^{x/3}$。我们仍然可以使用平方乘算法，因为指数被一个常数除，所以同底数幂相乘法则依然适用。换句话说，

为了计算 $0.7^{44/3}$，我们将按如下方式改变我们预计算的 $0.7$ 的幂：

然后，为了计算 $0.7^{44/3}$，我们将预计算的指数相乘如下：

再次鼓励读者自己重新进行这些计算。

从平方指数序列中选取元素

如果想要计算 $b^{44}$，我们如何弄清楚需要从平方指数序列中提取 $b$ 的哪些幂？换言之，我们如何快速确定我们需要的是 $b^{32}, b^{8}, b^{4}$ 而不是 $b^{32}, b^{4}, b^{1}$？

给定一个目标和（例如 44），我们如何快速确定它是 32、8 和 4 的和？或者，假设我们试图计算 $b^{37}$。我们需要的平方指数序列元素是 $b^{32},b^{4},b^{1}$ ——我们如何快速确定我们需要的是 $b^{32},b^{4},b^{1}$ 而不是 $b^{2},b^{8},b^{16}$？

一种朴素的方法是从最大的预计算指数开始向下进行线性搜索，并减去不超过目标值的最大值。例如，如果我们正在计算 $5^{44}$，这意味着我们已经计算了 5 的平方指数序列。我们向下扫描并发现 32 是最接近 44 的值。然后我们再次向下扫描找到 16，但请注意，将 32+16 相加会超过 44，所以我们跳过 16 并继续扫描到 8，依此类推。

使用二进制表示提取和的组成部分

与其使用上述线性搜索，我们可以通过观察发现：目标指数的二进制表示能够精确告诉我们应该使用平方指数序列中的哪些元素，从而提高效率。

这最好用例子来说明。

要将二进制数转换为十进制数，我们使用以下公式，其中 $b_i$ 是二进制数中的第 $i$ 位：

13 的二进制值是 1101，因为

52 的二进制值是 110100，因为

因此，如果我们想计算 $b^{13}$，并且我们的平方指数序列是 $b^8,b^4,b^2,b^1$，那么我们可以查看二进制表示 1011，并确定我们应该选取 8 指数、4 指数和 1 指数，然后计算

因为

因此，我们可以快速确定 13 可以写成 8 + 4 + 1，因为第 3 位、第 2 位和第 0 位都是 1。

检测某一位是否被置位

我们可以使用以下逻辑来检测二进制表示中的第 n 位是否为 1：

Copy
function nthBitSet(uint256 x, uint8 n) public pure returns (bool isSet) {

	isSet = x & uint256(2)**n != 0;
}

考虑 2 的幂的二进制表示：

uint256(2)**n 会创建一个仅在第 n 位设置为 1 的数字。例如，如果 n = 3，这将产生二进制值 1000。$2^3=8$，而 1000 是 8 的二进制表示，如上表所示。如果 x 和 2^n 的按位与不为零，那么 isSet 为 true。

按位与的工作原理

按位与仅当两个对应的位都为 1 时才返回 1；否则，它返回 0。例如，8 & 13 = 8，因为 8 的二进制表示是 1000，而 13 的二进制表示是：

或者是 1101。当我们将 1000 和 1101 进行按位与操作时，我们得到 1000，因为 8 和 13 在第 3 位都有一个共同的 1。

如下所示：

Copy
Suppose x = 13 (binary: 1101) and n = 3:

x           = 1101 (decimal 13)
2**n        = 1000 (decimal 8)
------------------------------
bitwise AND = 1000 (decimal 8) != 0, thus true.

Thus, nthBitSet(13, 3) returns true.

由于最终结果 1000 不等于零，因此我们知道 x 和 2^n 之间必定存在重叠的 1 位——这表明该位必然等于 1。

示例 2： 13 的第 1 位是否为 1？我们可以为第 1 位创建一个“掩码”即 2**1，如下所示：

Copy
Suppose x = 13 (binary: 1101) and n = 1:

x           = 1101 (decimal 13)
2**n        = 0010 (decimal 2)
------------------------------
bitwise AND = 0000 (decimal 0) == 0, thus false.

Thus, nthBitSet(13, 1) returns false.

由于最终结果是 0000，我们知道第 1 位没有被置为 1。

示例 3： 13 的第 0 位是否被置为 1？

Copy
Suppose x = 13 (binary: 1101) and n = 0:

x           = 1101 (decimal 13)
2**n        = 0001 (decimal 1)
------------------------------
bitwise AND = 0001 (decimal 1) == 1, thus true.

Thus, nthBitSet(13, 0) returns true.

$0.7^x$ 的 Python 示例

现在我们将所学的一切结合起来，编写以下函数，将 0.7 提升到不超过 32 的幂：

Copy
pow1 = 0.7
pow2 = 0.48999999999999994 # 0.7^2
pow4 = 0.24009999999999995 # 0.7^4
pow8 = 0.05764800999999997 # 0.7^8
pow16 = 0.0033232930569600965 # 0.7^16

def raise_07_to_p(p):
	# computes 0.7^p
	assert p < 32
	
	# if p = 0, we return 1, which is correct
	# since 0.7^0 = 1
	accumulator = 1
	
	if p & 1 != 0:
		accumulator = accumulator * pow1
	if p & 2 != 0:
		accumulator = accumulator * pow2
	if p & 4 != 0:
		accumulator = accumulator * pow4
	if p & 8 != 0:
		accumulator = accumulator * pow8
	if p & 16 != 0:
		accumulator = accumulator * pow16

	return accumulator

# check correctness
print(0.7**14, raise_07_to_p(14))
print(0.7**18, raise_07_to_p(18))
print(0.7**30, raise_07_to_p(30))

上述代码仅使用与指数二进制表示中的 1 相对应的 0.7 的幂，从而避免了重复计算的乘法。

到目前为止，我们使用的是常规数/浮点数。然而，在智能合约等实际系统中，我们经常使用定点数（或 Q 数）。

使用定点数的平方乘算法

将定点数（或 Q 数）相乘后，结果必须进行“归一化”，即结果需要除以缩放因子。例如，当我们将两个 18 位小数的定点数相乘时，需要将结果除以 $10^{18}$，否则最终结果将被写成 36 位小数。

预计算平方乘的 Python 和 Solidity 实现——使用定点数

我们将首先在 Python 中实现平方乘算法，然后将该代码转化为 Solidity。Solidity 版本将使用定点数，因为 Solidity 没有浮点数。下面，我们使用 Python 计算 0.7 的幂作为 128 位定点 Q 数，以此作为参考实现：

Copy
from decimal import *
import math
getcontext().prec = 100

for i in [1,2,4,8,16,32]:
    print(f"0.7^{i} * 2**128 =", math.floor(Decimal(0.7) ** Decimal(i) * Decimal(2**128)))

运行上述代码后，我们得到以下常量：

Copy
(base) ➜ python sqmul.py
0.7^1 * 2**128 = 238197656844656909312789480019373064192
0.7^2 * 2**128 = 166738359791259825940851714385556537344
0.7^4 * 2**128 = 81701796297717304344478436853479174360
0.7^8 * 2**128 = 19616601291081919795097291374069314602
0.7^16 * 2**128 = 1130858027394302849221997646234907220
0.7^32 * 2**128 = 3758172630847077410107089115980415

平方乘的 Solidity 实现

下面的 Solidity 实现使用 128 位定点数，这意味着小数点后有 128 位，或者等效地，分数通过乘以 $2^{128}$ 进行放大。>> 128 操作等效于除以 $2^{128}$。

Copy
contract SquareAndMultiply {

    // z7_x means 0.7^x
    uint256 constant z7_1 = 238197656844656909312789480019373064192;
    uint256 constant z7_2 = 166738359791259825940851714385556537344;
    uint256 constant z7_4 = 81701796297717304344478436853479174360;
    uint256 constant z7_8 = 19616601291081919795097291374069314602;
    uint256 constant z7_16 = 1130858027394302849221997646234907220;
    uint256 constant z7_32 = 3758172630847077410107089115980415;

    function powZ7(uint256 e) public pure returns (uint256) {
        require(e < 64, "e too large");

        // if e is zero, return 1 as a 128-bit fixed point number
        uint256 acc = 1 << 128;

				// powers of 2 are written in hex, 0x10 = 16 and 0x20 = 32
        if (e & 0x1 != 0) acc = (acc * z7_1) >> 128;
        if (e & 0x2 != 0) acc = (acc * z7_2) >> 128;
        if (e & 0x4 != 0) acc = (acc * z7_4) >> 128;
        if (e & 0x8 != 0) acc = (acc * z7_8) >> 128;
        if (e & 0x10 != 0) acc = (acc * z7_16) >> 128;
        if (e & 0x20 != 0) acc = (acc * z7_32) >> 128;

        // check the answer by doing acc / 2**128
        // in a language that has floating points
        // then check that equals 0.7^e
        return acc;
    }
}

为什么不直接使用指数操作码（opcode）？

当计算整数的整数次幂时，使用虚拟机内置的操作码通常效率更高。

然而，这个操作码并不包含上文所述的归一化步骤。因此，如果 $b^x$ 中的 $b$ 或 $x$ 至少有一个是定点数，那么我们就不能使用虚拟机的 exp 操作码。

Uniswap V3 中的平方乘

要将 tick 转换为平方根价格，Uniswap V3 必须计算

（由于 sqrtPrice 是一个 Q64.96 数，需要进行一些修正）。因为

1. 底数是固定的，唯一的变量是指数，并且

2. tick 的范围是预先知道的。Uniswap V3 可以（也确实）使用了平方乘算法。这将在下一章中解释。

作为预告，这里有一张来自 Uniswap V3 Tickmath Library 中 getSqrtRatioAtTick() 函数的截图。这看起来应该与我们上面编写的 Solidity 代码非常相似。从高层次来看，该函数检查 absTick 中的某一位是否被设置为 1，如果是，它会将 ratio 乘以预计算的 1.0001 的幂。