V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
geelaw
V2EX  ›  算法

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

  •  
  •   geelaw · 2018-01-15 19:26:42 +08:00 · 2503 次点击
    这是一个创建于 2264 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    由于一个已知的 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

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4701 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 09:47 · PVG 17:47 · LAX 02:47 · JFK 05:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.