在执行诸如幂、阶乘或计算斐波那契数列之类的迭代计算时，我们需要在某个点“停止计算”。
例如，如果我们计算 $x^7$，我们会将 $x$ 乘以自身七次。但是，条件停止在算术电路中是不可能的。由于电路的大小是固定的（底层 R1CS 具有固定数量的行，你不能更改它），它们必须足够大，以适应我们关心的每个指数的计算。
因此，解决方案是计算直到某个大于我们期望在实践中计算的限制的每个可能值。然后我们使用 Quin 选择器来选择所需的值。
本章展示了一个使用阶乘、斐波那契数列来执行此操作的示例，并将计算幂作为练习留给读者。
我们可以将这些计算中的每一个都视为一个状态机，它经历一个固定的状态转换一定的次数（其中迭代次数在证明时确定，而不是烘焙到电路中）。
这些序列在每个步骤中只有一个可能的计算（例如，加上前两个状态，或将前一个状态乘以某个数字）。但是，如果我们在每个状态添加条件分支，那么我们就拥有了有状态计算所需的所有组件。
在本章中，我们只展示只有一个可能的状态变化且状态变化的次数可变的示例。在接下来的章节中，我们将展示如何使状态转换本身有条件，即具有多个可能的状态转换。
阶乘示例
我们现在展示如何编写一个电路，以证明我们正确计算了
$$ y =x!\pmod p $$
其中 $!$ 是阶乘，$p$ 是默认的字段模数。
要在传统的编程语言（例如 Python）中计算阶乘，代码如下：
def factorial_mod_p(x, p):
if x == 0:
return 1
acc = 1
for i in range(1, x+1):
acc = (acc * i) % p
return acc
但是，如果直接转换为 Circom，上面的代码会有一些问题：
- Circom 不支持 if 语句，因此
if x == 0: return 0 行将无法编译。
- Circom 不支持未知迭代次数的循环。由于
x 决定了循环的值，因此这也无法编译。Circom 在底层编译为 R1CS，并且底层 R1CS 需要具有固定的大小，并且不能基于输入的值来更改大小。
为了使代码与诸如 R1CS 之类的算术化表示形式兼容，我们需要计算从零到我们打算支持的某个上限的阶乘。
例如，如果我们知道我们永远不需要计算超过 99 的阶乘，那么我们必须计算从 0 到 99（包括 0 到 99）的每个阶乘。如果我们想为 80 的阶乘创建一个证明，我们仍然需要计算从 0 到 99 的阶乘，但是我们使用 Quin 选择器来返回 80 的结果。
这是一个没有 if 语句和固定长度循环的 Python 示例：
def factorial_mod_p(x, p):
assert x < 100
# allocate the array
ans = [0] * 100
ans[0] = 1 # 0! = 1
for i in range(1, 100):
ans[i] = (ans[i-1] * i) % p
return ans[x]
从某种意义上说，我们正在创建一个长度为 100 的数组，并用该索引的阶乘填充这些值。然后，我们将使用 Quin 选择器“选择”我们关心的阶乘。
转换为 Circom 很简单：
include "./node_modules/circomlib/circuits/multiplexer.circom";
include "./node_modules/circomlib/circuits/comparators.circom";
template factorial(n) {
signal input in;
signal output out;
// precompute factorials from 0 to n
signal factorials[n+1];
// compute the factorials
factorials[0] <== 1;
for (var i = 1; i <= n; i++) {
factorials[i] <== factorials[i - 1] * i;
}
// ensure that in < n
signal inLTn;
inLTn <== LessThan(252)([in, n]);
inLTn === 1;
// select the factorial of interest
component mux = Multiplexer(1, n);
mux.sel <== in;
// assign factorials into the multiplexer
for (var i = 0; i < n; i++) {
mux.inp[i][0] <== factorials[i];
}
out <== mux.out[0];
}
component main = factorial(100);
/*
INPUT = { "in": "3" }
*/
一个不安全的实现
许多 Circom 新手工程师经常使用“直观的”解决方案，该解决方案避免了任何二次约束问题，并生成诸如以下代码：
pragma circom 2.1.8;
include "./node_modules/circomlib/circuits/comparators.circom";
template factorial(n) {
signal input in;
signal output out;
signal factorials[n + 1];
// compute the factorials
var acc = 1;
for (var i = 1; i < n; i++) {
acc = acc * i;
}
out <-- acc;
}
component main = factorial(100);
尽管 out 会有正确的答案，但是完全没有 <== 或 === 运算符意味着该电路没有约束。
在上面的代码中，程序员生成了代码来正确计算阶乘，但没有约束它。
斐波那契模 p 示例
在阶乘示例中，由于 0! = 1，因此我们必须“硬编码” factorials 的第 0 个条目为 1。在斐波那契数列中，前两个数字是 1，此后的所有数字都是序列中前两个数字的和。因此，对于斐波那契代码，我们硬编码前两个值，然后计算其余的值。
下面的电路计算直到第 n 个数字模 p 的斐波那契数列，然后输出感兴趣的“in”斐波那契数。
include "./node_modules/circomlib/circuits/multiplexer.circom";
include "./node_modules/circomlib/circuits/comparators.circom";
template Fibonacci(n) {
assert(n >= 2); // so we don't break the hardcoding
signal input in; // compute the kth Fibonacci number
signal output out;
// precompute Fibonacci sequence from
// 0 to n
signal fib[n + 1];
// compute the factorials
fib[0] <== 1;
fib[1] <== 1;
for (var i = 2; i < n; i++) {
fib[i] <== fib[i - 1] + fib[i - 2];
}
// ensure that in < n
signal inLTn;
inLTn <== LessThan(252)([in, n]);
inLTn === 1;
// select the fibonacci number
// of interest
component mux = Multiplexer(1, n);
mux.sel <== in;
// assign Fibonacci into
// the Quin Selector
for (var i = 0; i < n; i++) {
mux.inp[i][0] <== fib[i];
}
out <== mux.out[0];
}
component main = Fibonacci(99);
/*
INPUT = {"in": 5}
*/
与往常一样，显式约束斐波那契数列的每次更新非常重要，而不仅仅是在无约束的循环中计算结果。
练习：
在 Circom Puzzles 中完成 pow 练习。
