题目

The Art of Computer Programming, Volume 1, Fascicle 1, MMIX, Donald E. Knuth, 2004. 习题 1.3.2'-30 (pages 48-49):

这道题目基本上等价于《计算机程序设计艺术·卷1:基本算法(第3版)》习题 1.3.2-16(第 129 页)。

解答

是充分小的正实数时,。因此,我们有

,则当且仅当 时,。因此,我们得到

最终,我们得到以下 MMIX 程序(根据书上的习题答案 (pages 109-110) 稍做修改):

简要说明:

  • 程序中标号栏的 0H, 1H, 2H 的 H 意思是 Here,而操作数栏的 2F, 1B, 0B 的 F 和 B 意思分别是 Forward 和 Backward 。(See pages 35-36)
  • 第 2 至 14 行是 MMIXAL 伪操作码,定义一些常量和变量等。
  • 第 17 至 46 行是外层循环。题目要求对于 1 ≤ n ≤ 10 计算 Sn,程序中对 -9 ≤ nn ≤ 0 进行循环。参考第 10 行。这是汇编语言编程的常用技巧,可以节省一条 CMP 指令。
  • 第 15 行设置 nn 的初值为 -9,第 44 行在外层循环中将 nn 加 1。
  • 第 16 行设置 c 的初值为 20,第 45 行在外层循环中将 c 乘以 10。参考第 4 行。
  • 第 20 至 31 行的内层循环计算所求的和,结果在寄存器 s 中。
  • 第 32 至 43 行打印 s 的值。注意,s 是整数,正好是所求的和的 10n 倍。即小数点后正好有 n 位数字。
  • 第 32 至 33 行在小数点后第 n+1 位放一个 '\n',即换行符。
  • 第 35 至 41 行的内层循环从右到左得到 s 的各位数字。
  • 第 40 行判断当前位置是否在小数点处,如是,再左移一格,以跳过小数点。

等价的 C 程序:

#include <stdio.h>

int main(void)
{
  for (long n = 0, s = 10, c = 20; ++n <= 10; s = (c *= 10) >> 1) {
    for (long mm, m = 1, r = 1; r != 0; m = mm)
      r = (c + m) / ((m + 1) << 1),
      s += r * ((mm = (c - 1) / ((r << 1) - 1)) - m);
    printf("%3ld.%0*ld\n", s / (c >> 1), n, s % (c >> 1));
  }
}

MMIX 程序的运行时间不到 1 秒,C 程序为 0.01 秒。这两个程序的运行结果是相同的,都是:

  3.7
  6.13
  8.445
 10.7504
 13.05357
 15.356255
 17.6588268
 19.96140681
 22.263991769
 24.5665766342