打印功能坏掉的时候如何打印文件

[geelaw]

据说在伯克利的加州大学曾经发布过这样的通告：

由于一个已知的 bug，Linux 下的 evince PDF 查看器在打印文档 n 份的时候会导致打印出 n^2 份。一个绕过方法是使用 Adobe Reader 打印，另一个方法是利用拉格朗日四平方和定理。

拉格朗日四平方和定理 是说任何自然数都可以写成至多 4 个完全平方数的和。

于是一个自然的想法是，当我需要打印文档 n 份的时候，寻找 x,y,z,w 使 n=x^2+y^2+z^2+w^2，然后分别“打印” x,y,z,w “份”。

已经有文献表明寻找 n 的四平方和分解只需要 O((logn)^2) 的期望时间（需要假设扩展黎曼猜想是对的）。该方法的计算复杂度是 O((logn)^2)，通信复杂度是 O(1) 个打印任务。（注：时间是按照对不超过 n 的数进行四则运算的次数计算的）

另一个自然的想法是，第一次“打印” floor(sqrt(n)) “份”，然后化为一个更小的问题。这个方法每进行一次，剩下还需要的份数不超过 2sqrt(n)+1。因此可以得出该方法的通信复杂度是 O(loglogn) 个打印任务。每次迭代，我们需要算出 n 的平方根的整数部分，利用牛顿迭代法，可以在 O(loglogn) 的时间内算出。总的来说，这个方法的计算复杂度是 O((loglogn)^2)。它的好处是不需要使用黎曼猜想。

原文：Chit-chat on Lagrange ’ s four-square theorem。