位复杂度

二进制长度把“数字有多大”转换成“必须保存多少信息”。$2^{1000}$ 的数值巨大，但写下它只需 $1001$ bit；反过来，输入一个长度约为 $1000$ bit 的指数 $e$，要求完整输出 $3^e$，答案可能需要指数多的位。

位复杂度也不等于实际处理器逐个 bit 地执行。Word-RAM 模型公理库Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。允许一个有限宽度的机器字作为计费单位，实际大整数库则常按字分块。两种分析都可以有用，但从字操作数换成位成本，必须展开操作和存储实现，尤其不能把任意长整数视为一个字。

同样是算术操作，单次成本不同 ​

对至多 $b$ bit 的两个非负整数，传统进位加法扫描各位，耗时 $O(b)$，输出至多 $b+1$ bit。传统乘法形成至多 $b$ 行移位部分积，每行至多 $2b$ bit，总成本为 $O(b^2)$。这两个界对应具体逐位实现；乘法的二次界是该算法的上界，不是所有乘法算法的下界。

输入输出本身也有成本。在每步只能写常数个输出符号的模型中，显式输出 $L$ bit 至少需要 $\mathrm{\Omega }(L)$ 步。若任务要求完整读入 $n$ bit，读取需 $\mathrm{\Omega }(n)$；若正确性迫使某些最坏输入上的全部位都被检查，也有相同下界。但不能据此断言所有任务都必须读完整个输入，例如只返回第一个 bit 的任务可忽略后缀。

重复平方：少量乘法怎样生成很长的答案 ​

固定底数 $3$，令 $x_0=3$、$x_{i+1}=x_i^2$，于是 $x_i=3^{2^i}$。四次平方得到：

例如 $2^6\le 81<2^7$，所以 $81$ 占 $7$ bit；$2^{25}\le 43046721<2^{26}$，所以最后一项占 $26$ bit。位长来自二进制表示，不能用表中的十进制数字大小直接代替。

一般地，$\ell (x_i)=\lfloor 2^i{\log }_{2}3\rfloor +1=\mathrm{\Theta }(2^i)$。因此用传统乘法算到 $x_k$，平方部分的成本是

这个推导没有把 $k$ 次平方一律按初始的两位整数收费。即使换用更快的乘法，完整输出仍有 $\mathrm{\Omega }(2^k)$ 的成本：当指数 $e=2^k$ 用二进制给出时，指数输入仅有 $k+1$ bit，而 $3^e$ 的输出有 $\mathrm{\Theta }(2^k)$ bit。因此“重复平方用了 $O(\log e)$ 次乘法”并不能推出完整求幂对输入位长是多项式时间。

每步取模为什么改变结论 ​

若任务改为求 $3^{2^k}mod17$，可以令 $r_0=3$、$r_{i+1}=r_i^{2}mod17$。关键是每次平方之后立即取模，而不是先生成完整整数再取模。表中 $9^{2}mod17=13$、${13}^{2}mod17=16$、${16}^{2}mod17=1$，每次存回的结果始终小于 $17$。

推广到 $m$ bit 的模数 $N\ge 2$，已约化的余数至多 $m$ bit；一次平方先产生至多 $2m$ bit 的积，再用传统长除法求余，二者合计 $O(m^2)$ 位操作。对 $e=2^k$ 只需 $k$ 次这样的模平方，算术部分为 $O(k{m}^2)$；把读入与初始处理包含在内可写为 $O((k+1)m^2)$。任意 $k$ bit 指数可沿二进制位做平方及必要的模乘，也得到 $O(k{m}^2)$ 的算术成本。这里默认底数已约化或本身至多 $m$ bit；若底数更长，其读取与首次求余必须另计。

分析大整数、精确有理数和符号表达式算法时，应先控制中间表示的长度，再统计操作次数。分数约分可能压低后续成本，延迟约分则可能造成分子、分母膨胀；只比较加乘次数无法决定哪种实现更快。浮点运算若固定精度，可以采用另一套固定字长成本，但不能据此声称任意精度精确运算也是常数时间。

位复杂度还帮助检查确定性时间类公理库确定性时间复杂性类Deterministic time class · DTIME由确定性图灵机在给定时间界内判定的语言集合。中的“多项式”究竟相对于什么参数。按数值 $N$ 执行 $N$ 轮，与按 $\ell (N)$ 执行多项式轮数是两种保证；随后再使用渐近记号公理库渐近记号Asymptotic notation · Big O notation忽略常数和低阶项，比较函数在输入趋于无穷时的增长速度。，才能避免编码变化掩盖指数成本。

自测。 输入二进制指数 $e=2^k$，分别要求输出 $2^e$ 的完整二进制串，以及输出 $2^{e}mod17$。前者的输出下界是多少？后者能否套用同一下界？检查标准：完整串是一个 1 后接 $e$ 个 0，长度为 $2^k+1$；模结果至多 $5$ bit，不受这个指数输出下界约束。若允许把答案写成字符串“$2^e$”，那已经改变了输出表示与计算任务。