Solidity 平方乘算法

平方再乘算法在 $O(log⁡n)$ （对数时间）内计算整数指数。 计算指数 $x^n$ 的简单方法是将 x 与自身相乘 n 次，这将需要 $O(n)$ 时间来计算。

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

$$ \begin{align} x^2&=x\cdot x\ x^4&=x^2\cdot x^2\ x^8&=x^4\cdot x^4\ x^{16}&=x^8\cdot x^8 \end{align} $$

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

$$x^{20}=x^4x^{16}$$

指数以这种方式“相加”的事实在代数中称为幂的乘积规则。

本文是 关于 Uniswap V3 代码库的系列文章 的一部分。 Uniswap V3 使用平方再乘算法将 tick 索引转换为平方根价格。 但是，本文也适用于任何想学习平方再乘算法工作原理的人。

平方指数序列

我们将在本文中多次使用术语“平方指数序列”，即 $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，我们可以预先计算以下值：

$$ \begin{align*} &0.7\ &0.7^2=0.49\ &0.7^4=0.2401\ &0.7^8=0.05764801\ &0.7^{16}=0.00332329\ &0.7^{32}=0.00001104

\end{align*} $$

然后，例如，如果我们想计算 $0.7^{44}$，我们可以将平方指数序列中的适当的预计算值相乘，如下所示：

$$ \begin{align} 0.7^{44}&=0.7^{32}\times0.7^{8}\times0.7^{4}\ 0.00000015&=0.00001104\times0.05764801\times0.2401 \end{align} $$

鼓励读者在他们的计算器上重做 $0.7^{44}$ 以仔细检查这一点。

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

具有分数指数的平方再乘算法

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

$$ 0.7^{44/3}=0.7^{32/3}\times0.7^{8/3}\times0.7^{4/3} $$

要计算 $0.7^{44/3}$，我们将更改 0.7 的幂，我们预先计算如下：

0. 71/3=0.8879040017426006
1. 72/3=0.7883735163105242
2. 74/3=0.6215328012198205
3. 78/3=0.38630302299215685
4. 716/3=0.14923002557287887
5. 732/3=0.02226960053248208

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

$0.7^{44/3} = 0.7^{32/3} \times 0.7^{8/3} \times 0.7^{4/3}$ $0.005346931087848946 = 0.02226960053248208 \times 0.38630302299215685 \times 0.6215328012198205$

同样，鼓励读者自己重做这些计算。

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

如果想计算 b44，我们如何确定我们需要平方指数序列中的哪些 b 的幂？ 换句话说，我们如何快速确定我们需要 $ b^{32}, b^{8}, b^{4} $而不是 $b^{32}, b^{4}, b^{1}$？

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

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

使用二进制表示提取和分量

我们可以通过观察到目标指数的二进制表示准确地告诉我们应该使用平方指数序列中的哪些元素，而不是使用上述线性搜索，我们可以更有效率。

通过示例可以最好地说明这一点。

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

$$ \text{decimal_value}=2^{n-1}b_{n-1}\dots+8b_3+4b_2+2b_1+b0=\sum{i=0}^{n-1}2^ib_i $$

13 的二进制值是 1101，因为

$$ \begin{align} 44=8&\cdot1 \ +4&\cdot1 \ +2&\cdot0 \ +1&\cdot1 \end{align} $$

52 的二进制值是 110100，因为

$$ \begin{align} 52 = 32&\cdot1\ +16&\cdot1\ +8&\cdot0\ +4&\cdot1\ +2&\cdot0\ +1&\cdot0 \end{align} $$

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

$$ b^{13}=b^8\cdot b^4\cdot b^1 $$

因为

$$ 13=8+4+1 $$

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

检测是否设置了位

我们可以使用以下逻辑检测二进制表示中是否设置了第 n 位：

function nthB...