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

标签：

• Tokyo-University
• Horner-Method
• Karatsuba-Integer-Multiplication
• Recurrence-Relation-Complexity

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 (多项式和大整数运算)