【无标题】计算机程序设计艺术习题解答（Excercise 1.2.2-25题）

最近突发奇想，想把自己做名著 计算机程序设计艺术(The Art of Computer Programming)（此书名气很大，但能读下去的人寥寥无几）的习题的过程（主要一些比较有意思的习题，太简单的没必要，特别难的说不定我也不会做:)）放在网上和人分享。尽管这在国内是非常冷门的一件事，而且工程浩大（输入数学公式效率不高），幸好本人计算机软件专业出身，目前时间比较充裕，闲云野鹤一枚，这种分享至少可以督促我能把这件事持续地做下去，不至于半途而废。

25. [22] 假设有一个二进制电脑和一个二进制实数 x, 1 ≤ x < 2. 证明如下只使用了二进制移位、加法和减法操作（操作数量与 x 的小数点后有效位数成正比）的算法可用于计算 y =  的近似值:

L1. [Initialize.] Set y ← 0, z ← x 右移 1 位, k ← 1.

L2. [Test for end.] If x = 1, stop.

L3.[Compare.] If x - z < 1, set z ← z 右移 1 位, k ← k + 1, and repeat this step.

L4. [Reduce values.] Set x ← x - z, z ← x 右移 k 位, y ← y + , and go to L2.

这个算法看似有些绕，其实原理很简单。假设小数点后有效位数即精度为 p，则 z 的值相当于先将 x 左移 p 位，再右移 k 位，最后再右移 p 位以恢复小数点位置，即 z 始终等于 （第一个算法不变式），算法的误差就体现在这个（floor）操作上。

算法的核心在 L4 这步。由于 ，当 x 减掉 z 以后，x 变成了，

根据对数的特性，有

这样经过 L4 这个步骤后， 的值始终保持近似恒定（第二个算法不变式），当 x = 1 时算法结束（此时  ），此时 y 的值就是最初所求的  的近似值。当然电脑会保存一个辅助的常量表，记录 ... 这些常量的值。

此算法最终一定会结束。因为首先 1 ≤ x < 2，x 在算法进行中不断减小并逐渐逼近1（但保持大于等于1），当 x - 1 <  时，算法会近似认为 x = 1 并结束。