Skip to content

東京大学 新領域創成科学研究科 メディカル情報生命専攻 2016年8月実施 問題7

Author

zephyr

Description

(1) Given an integer \(x\), we calculate a polynomial, \(f = \sum_{i=0}^{n} a_i x^i \, (n, a_i (0 \leq i \leq n) \text{ are natural numbers})\). A single addition or multiplication of two values takes a unit time regardless of the number of the digits in the representation of the values.

  • (A) Let \(f_i = a_i x^i\). Find the time complexity (with regard to \(n\)) of an algorithm that calculates \(f_0, f_1, \ldots, f_n\) individually and then calculates \(f = \sum_{i=0}^{n} f_i\).

  • (B) Let \(g_i = \begin{cases} a_n & \text{(when } i = n\text{)} \\ g_{i+1} x + a_i & \text{(when } i < n\text{)} \end{cases}\). Notice that \(f = g_0\) holds. Find the time complexity (with regard to \(n\)) of an algorithm that calculates \(g_0\), hence \(f\) by calculating \(g_n, g_{n-1}, \ldots, g_0\) in this order.

(2) Given two \(2^{n+1}\)-bit integers \(a\) and \(b\), let \(a_{hi}, b_{hi}\) be the highest \(2^n\) bits of \(a\) and \(b\), and \(a_{lo}, b_{lo}\) the lowest \(2^n\) bits of \(a\) and \(b\), respectively. We calculate the product of \(a\) and \(b\) when \(n\) is fairly large. Assume that computation time for addition or shift is negligible compared to that for multiplication.

  • (A) The multiplication of \(2^{n+1}\)-bit integers can be constructed from the multiplication of \(2^n\)-bit integers as follows: \(ab = r_2 2^{2n} + r_1 2^n + r_0\), where \(r_2 = a_{hi} b_{hi}, r_1 = a_{hi} b_{lo} + a_{lo} b_{hi}, r_0 = a_{lo} b_{lo}\). We can recursively apply this reduction until every multiplication only involves integers small enough to fit in the machine word of the computer. Let \(T(2^{n+1})\) be the number of machine-word multiplications required in the multiplication of two \(2^{n+1}\)-bit integers. Express \(T(2^{n+1})\) in terms of \(T(2^n)\).

  • (B) Solve the recursive equation you answered in (A), and express \(T(2^n)\) in Landau's \(O\) notation.

  • (C) We reduce the number of multiplications in the calculation in (A) by calculating \(r_1\) as \(r_1 = r_2 + r_0 - (a_{hi} - a_{lo})(b_{hi} - b_{lo})\). Express \(T(2^n)\) in Landau's \(O\) notation, and prove it.

(1) 给定一个整数 \(x\)，我们计算一个多项式，\(f = \sum_{i=0}^{n} a_i x^i \, (n, a_i (0 \leq i \leq n) \text{ 是自然数})\)。两个值的单次加法或乘法的计算时间是一个单位时间，与值的表示形式中的位数无关。

  • (A) 令 \(f_i = a_i x^i\)。找到一个算法的时间复杂度（关于 \(n\)），该算法分别计算 \(f_0, f_1, \ldots, f_n\)，然后计算 \(f = \sum_{i=0}^{n} f_i\)。

  • (B) 令 \(g_i = \begin{cases} a_n & \text{(当 } i = n\text{ 时)} \\ g_{i+1} x + a_i & \text{(当 } i < n\text{ 时)} \end{cases}\)。注意 \(f = g_0\) 成立。找到一个算法的时间复杂度（关于 \(n\)），该算法计算 \(g_0\)，从而通过依次计算 \(g_n, g_{n-1}, \ldots, g_0\) 得到 \(f\)。

(2) 给定两个 \(2^{n+1}\) 位的整数 \(a\) 和 \(b\)，令 \(a_{hi}, b_{hi}\) 为 \(a\) 和 \(b\) 的最高 \(2^n\) 位，\(a_{lo}, b_{lo}\) 为 \(a\) 和 \(b\) 的最低 \(2^n\) 位。我们在 \(n\) 较大时计算 \(a\) 和 \(b\) 的乘积。假设加法或移位的计算时间相对于乘法可以忽略不计。

  • (A) \(2^{n+1}\) 位整数的乘法可以通过 \(2^n\) 位整数的乘法构造，如下所示：\(ab = r_2 2^{2n} + r_1 2^n + r_0\)，其中 \(r_2 = a_{hi} b_{hi}, r_1 = a_{hi} b_{lo} + a_{lo} b_{hi}, r_0 = a_{lo} b_{lo}\)。我们可以递归地应用这种缩减，直到每次乘法仅涉及足够小的整数以适应计算机的机器字。设 \(T(2^{n+1})\) 为两个 \(2^{n+1}\) 位整数相乘所需的机器字乘法次数。用 \(T(2^n)\) 表示 \(T(2^{n+1})\)。

  • (B) 解答你在 (A) 中回答的递归方程，并用 Landau 符号 \(O\) 表示 \(T(2^n)\)。

  • (C) 我们通过计算 \(r_1\) 为 \(r_1 = r_2 + r_0 - (a_{hi} - a_{lo})(b_{hi} - b_{lo})\) 来减少 (A) 中的乘法次数。用 Landau 符号 \(O\) 表示 \(T(2^n)\)，并证明它。

Kai

(1)

(A)

First, consider calculating each term \(f_i = a_i x^i\) individually and then summing them to get \(f = \sum_{i=0}^{n} f_i\).

  • To compute each \(f_i = a_i x^i\):
  • Computing \(x^i\) takes \(i\) multiplications.

  • Therefore, the time to compute \(f_i\) is \(O(i)\).

  • Summing up the times for all \(f_i\):

\[ \sum_{i=0}^{n} O(i) = O(0 + 1 + 2 + \cdots + n) = O\left(\frac{n(n+1)}{2}\right) = O(n^2) \]

Thus, the overall time complexity is \(O(n^2)\).

(B)

The recurrence relation for \(g_i\) is:

\[ g_i = \begin{cases} a_n & \text{when } i = n \\ g_{i+1} x + a_i & \text{when } i < n \end{cases} \]

We calculate \(g_n, g_{n-1}, \ldots, g_0\) in this order:

  • Calculating \(g_n\) takes \(O(1)\).
  • Calculating \(g_{n-1}\) from \(g_n\) involves one multiplication and one addition, so it takes \(O(1)\).
  • Similarly, calculating each \(g_i\) from \(g_{i+1}\) takes \(O(1)\).

Since there are \(n+1\) such calculations, the overall time complexity is \(O(n)\).

(2)

(A)

Given:

\[ ab = r_2 2^{2n} + r_1 2^n + r_0 \]

where: - \(r_2 = a_{hi} b_{hi}\) - \(r_1 = a_{hi} b_{lo} + a_{lo} b_{hi}\) - \(r_0 = a_{lo} b_{lo}\)

This involves four multiplications of \(2^n\)-bit integers:

\[ T(2^{n+1}) = 4T(2^n) \]

(B)

The recurrence relation is:

\[ T(2^{n+1}) = 4T(2^n) \]

Let \(k = n+1\). Then we have:

\[ T(2^k) = 4T(2^{k-1}) \]

Expanding this, we get:

\[ T(2^k) = 4^k T(2^0) \]

Since \(T(2^0)\) is a constant \(C\), we get:

\[ T(2^k) = 4^k C \]

Therefore, in terms of \(n\):

\[ T(2^n) = O(2^{2n}) \]

(C)

Using the optimized method for \(r_1\):

\[ r_1 = r_2 + r_0 - (a_{hi} - a_{lo})(b_{hi} - b_{lo}) \]

This involves three multiplications of \(2^n\)-bit integers:

\[ T(2^{n+1}) = 3T(2^n) \]

Solving this recurrence relation similarly:

\[ T(2^k) = 3^k T(2^0) \]

Since \(T(2^0)\) is a constant \(C\), we get:

\[ T(2^k) = 3^k C \]

Therefore, in terms of \(n\):

\[ T(2^n) = O(3^n) = O(2^{n \log_2 3}) \]

knowledge

时间复杂度 递归 复杂度分析

重点词汇

  • polynomial 多项式
  • time complexity 时间复杂度
  • recurrence relation 递归关系
  • multiplication 乘法

参考资料

  1. Introduction to Algorithms, Cormen et al., Chap. 2 (时间复杂度分析)
  2. Introduction to Algorithms, Cormen et al., Chap. 30 (多项式和大整数运算)