chap33.htm

介绍算法的书籍

<a name="09a6_1b59">33.1-10<a name="09a6_1b59"><P>
Prove Theorem 33.8.<P>
<a name="09a6_1b5a">33.1-11<a name="09a6_1b5a"><P>
Give efficient algorithms for the operations of dividing a <img src="../images/beta14.gif"><I>-bit integer by a shorter integer and of taking the remainder of a <img src="../images/beta14.gif"></I>-bit integer when divided by a shorter integer. Your algorithms should run in time <I>O</I>(<img src="../images/beta14.gif"><I><SUP>2</SUP>).</I><P>
<a name="09a6_1b5b">33.1-12<a name="09a6_1b5b"><P>
<a name="09a6_1b4e">Give an efficient algorithm to convert a given <img src="../images/beta14.gif"><I>-</I>bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most <img src="../images/beta14.gif"><I> takes time </I>M<I>(<img src="../images/beta14.gif"></I>), then binary-to-decimal conversion can be performed in time <img src="../images/bound.gif">(<I>M</I>(<img src="../images/beta14.gif"><I>) lg <img src="../images/beta14.gif"></I>). (<I>Hint</I>: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions.)<P>
<P>


<P>







<h1><a name="09a7_1b52">33.2 Greatest common divisor<a name="09a7_1b52"></h1><P>
<a name="09a7_1b4f"><a name="09a7_1b50">In this section, we use Euclid's algorithm to compute the greatest common divisor of two integers efficiently. The analysis of running time brings up a surprising connection with the Fibonacci numbers, which yield a worst-case input for Euclid's algorithm.<P>
We restrict ourselves in this section to nonnegative integers. This restriction is justified by equation (33.10), which states that gcd(<I>a</I>,<I>b</I>) = gcd(|<I>a</I>|, |<I>b</I>|).<P>
In principle, we can compute gcd(<I>a</I>, <I>b</I>) for positive integers <I>a</I> and <I>b</I> from the prime factorizations of <I>a</I> and <I>b</I>. Indeed, if<P>
<img src="808_a.gif"><P>
<h4><a name="09a7_1b53">(33.13)<a name="09a7_1b53"></sub></sup></h4><P>
<h4><a name="09a7_1b54">(33.14)<a name="09a7_1b54"></sub></sup></h4><P>
with zero exponents being used to make the set of primes <I>p</I><SUB>1</SUB>, <I>p</I><SUB>2</SUB>, . . . , <I>p<SUB>r</I></SUB> the same for both <I>a</I> and <I>b</I>, then<P>
<img src="809_a.gif"><P>
<h4><a name="09a7_1b55">(33.15)<a name="09a7_1b55"></sub></sup></h4><P>
As we shall show in Section 33.9, the best algorithms to date for factoring do not run in polynomial time. Thus, this approach to computing greatest common divisors seems unlikely to yield an efficient algorithm.<P>
Euclid's algorithm for computing greatest common divisors is based on the following theorem.<P>
<a name="09a7_1b56">Theorem 33.9<a name="09a7_1b56"><P>
<a name="09a7_1b51">For any nonnegative integer <I>a</I> and any positive integer <I>b</I>,<P>
<pre>gcd(<I>a</I>,<I>b</I>) = gcd(<I>b</I>,<I>a</I> mod <I>b</I>) .</sub></sup></pre><P>
<I><B>Proof     </I></B>We shall show that gcd (<I>a</I>, <I>b</I>) and gcd (<I>b</I>, <I>a</I> mod <I>b</I>) divide each other, so that by equation (33.7) they must be equal (since they are both nonnegative).<P>
We first show that gcd (<I>a</I>, <I>b</I>) | gcd(<I>b</I>, <I>a</I> mod <I>b</I>). If we let <I>d</I> = gcd (<I>a</I>, <I>b</I>), then <I>d</I> | <I>a</I> and <I>d</I> | <I>b</I>. By equation (33.2), (<I>a</I> mod <I>b</I>) = <I>a </I>- <I>qb</I>, where <I>q</I> = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>a/b<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>. Since (<I>a</I> mod <I>b</I>) is thus a linear combination of <I>a</I> and <I>b</I>, equation (33.6) implies that <I>d</I> | (<I>a</I> mod <I>b</I>). Therefore, since <I>d</I> | <I>b</I> and <I>d</I> | (<I>a</I> mod <I>b</I>), Corollary 33.3 implies that <I>d</I> | gcd(<I>b</I>, <I>a</I> mod <I>b</I>) or, equivalently, that<P>
<pre>gcd(<I>a</I>, <I>b</I>) | gcd(<I>b</I>, <I>a</I> mod <I>b</I>).</sub></sup></pre><P>
<h4><a name="09a7_1b57">(33.16)<a name="09a7_1b57"></sub></sup></h4><P>
Showing that gcd (<I>b</I>, <I>a</I> mod <I>b</I>) | gcd(<I>a</I>, <I>b</I>) is almost the same. If we now let <I>d </I>= gcd(<I>b</I>, <I>a</I> mod <I>b</I>), then <I>d</I> | <I>b</I> and <I>d</I> | (<I>a</I> mod <I>b</I>). Since <I>a</I> = <I>qb</I> + (<I>a</I> mod <I>b</I>), where <I>q</I> = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>a</I></FONT>/<I>b</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>, we have that <I>a </I>is a linear combination of <I>b</I> and (<I>a</I> mod <I>b</I>). By equation (33.6), we conclude that <I>d</I> | <I>a</I>. Since <I>d</I> | <I>b</I> and <I>d</I> | <I>a</I>, we have that <I>d</I> | gcd(<I>a</I>, <I>b</I>) by Corollary 33.3 or, equivalently, that<P>
<pre>gcd (<I>b</I>,<I>a</I> mod <I>b</I>) | gcd(<I>a</I>,<I>b</I>).</sub></sup></pre><P>
<h4><a name="09a7_1b58">(33.17)<a name="09a7_1b58"></sub></sup></h4><P>
Using equation (33.7) to combine equations (33.16) and (33.17) completes the proof.      <P>





<h2>Euclid's algorithm</h2><P>
The following gcd algorithm is described in the <I>Elements</I> of Euclid (<I>circa</I> 300 <FONT FACE="Courier New" SIZE=2>B.C</FONT>.), although it may be of even earlier origin. It is written as a recursive program based directly on Theorem 33.9. The inputs <I>a</I> and<I> b</I> are arbitrary nonnegative integers.<P>
<pre><a name="09a8_1b52">EUCLID (<I>a</I>, <I>b</I>)</sub></sup></pre><P>
<pre>1  <B>if</B> <I>b</I> = 0</sub></sup></pre><P>
<pre>2      <B>then return</B> <I>a</I></sub></sup></pre><P>
<pre>3      <B>else return</B> EUCLID(<I>b</I>,<I>a</I> mod <I>b</I>)</sub></sup></pre><P>
As an example of the running of <FONT FACE="Courier New" SIZE=2>EUCLID</FONT>, consider the computation of gcd (30,21):<P>
<pre>EUCLID(30, 21)  =  EUCLID(21, 9)</sub></sup></pre><P>
<pre>=  EUCLID(9, 3)</sub></sup></pre><P>
<pre>=  EUCLID(3, 0)</sub></sup></pre><P>
<pre>=  3 .</sub></sup></pre><P>
In this computation, there are three recursive invocations of <FONT FACE="Courier New" SIZE=2>EUCLID</FONT>.<P>
The correctness of <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> follows from Theorem 33.9 and the fact that if the algorithm returns <I>a </I>in line 2, then<I> b</I> = 0, so equation (33.11) implies that gcd(<I>a</I>, <I>b</I>) = gcd(<I>a</I>, 0) = <I>a</I>. The algorithm cannot recurse indefinitely, since the second argument strictly decreases in each recursive call. Therefore, <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> always terminates with the correct answer.<P>
<P>







<h2>The running time of Euclid's algorithm</h2><P>
We analyze the worst-case running time of <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> as a function of the size of <I>a</I> and <I>b</I>. We assume with little loss of generality that <I>a</I> &gt; <I>b</I> <img src="../images/gteq.gif"> 0. This assumption can be justified by the observation that if <I>b</I> &gt; <I>a</I> <img src="../images/gteq.gif"> 0, then E<FONT FACE="Courier New" SIZE=2>uclid</FONT> (<I>a</I>, <I>b</I>) immediately makes the recursive call <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> (<I>b</I>, <I>a</I>). That is, if the first argument is less than the second argument, <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> spends one recursive call swapping its arguments and then proceeds. Similarly, if <I>b</I> = <I>a</I> &gt; 0, the procedure terminates after one recursive call, since <I>a</I> mod <I>b</I> = 0.<P>
The overall running time of <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> is proportional to the number of recursive calls it makes. Our analysis makes use of the Fibonacci numbers <I>F<SUB>k</I></SUB>, defined by the recurrence (2.13).<P>
<a name="09a9_1b54">Lemma 33.10<a name="09a9_1b54"><P>
If <I>a</I> &gt; <I>b </I><img src="../images/gteq.gif"> 0 and the invocation <FONT FACE="Courier New" SIZE=2>Euclid</FONT>(<I>a</I>, <I>b</I>) performs <I>k</I> <img src="../images/gteq.gif"> 1 recursive calls, then <I>a</I> <img src="../images/gteq.gif"> <I>F<SUB>k</I>+2</SUB> and <I>b</I> <img src="../images/gteq.gif"> <I>F<SUB>k</I>+l</SUB>.<P>
<I><B>Proof     </I></B>The proof is by induction on<I> k</I>. For the basis of the induction, let <I>k</I> = 1. Then, <I>b</I> <img src="../images/gteq.gif"> 1 = <I>F</I><SUB>2</SUB>, and since <I>a</I> &gt;<I> b</I>, we must have <I>a</I> <img src="../images/gteq.gif"> 2 = <I>F</I><SUB>3</SUB>. Since <I>b</I> &gt; (<I>a</I> mod <I>b</I>), in each recursive call the first argument is strictly larger than the second; the assumption that<I> a</I> &gt; <I>b</I> therefore holds for each recursive call.<P>
Assume inductively that the lemma is true if <I>k</I> - 1 recursive calls are made; we shall then prove that it is true for <I>k</I> recursive calls. Since <I>k</I> &gt; 0, we have <I>b</I> &gt; 0, and <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> (<I>a</I>, <I>b</I>) calls <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> (<I>b</I>, <I>a</I> mod <I>b</I>) recursively, which in turn makes <I>k</I> - 1 recursive calls. The inductive hypothesis then implies that<I> b</I> <img src="../images/gteq.gif"> <I>F<SUB>k</I>+ 1</SUB> (thus proving part of the lemma), and (<I>a</I> mod <I>b</I>) <img src="../images/gteq.gif"> <I>F<SUB>k</I></SUB>. We have<P>
<pre><I>b</I> + (<I>a</I> mod <I>b</I>)  =  <I>b</I> + (<I>a</I> - <img src="../images/hfbrdl12.gif"><I>a</I>/<I>b</I><img src="../images/hfbrdr12.gif"> <I>b</I>)</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif">  <I>a</I>,</sub></sup></pre><P>
since <I>a</I> &gt; <I>b</I> &gt; 0 implies <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"><I>a</I></FONT>/<I>b</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> <img src="../images/gteq.gif"> 1. Thus,<P>
<pre><I>a  </I><img src="../images/gteq.gif">  <I>b </I>+ (<I>a</I> mod <I>b</I>)</sub></sup></pre><P>
<pre><img src="../images/gteq.gif">  <I>F<SUB>k </I>+ 1</SUB> + <I>F<SUB>k</I></sub></sup></pre><P>
<pre>=  <I>F<SUB>k</I>+2</SUB> .      </sub></sup></pre><P>
The following theorem is an immediate corollary of this lemma.<P>
<a name="09a9_1b55">Theorem 33.11<a name="09a9_1b55"><P>
<a name="09a9_1b53">For any integer <I>k</I> <img src="../images/gteq.gif"> 1, if <I>a</I> &gt; <I>b</I> <img src="../images/gteq.gif"> 0 and <I>b</I> &lt; <I>F<SUB>k</I>+1</SUB>, then the invocation <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> (<I>a</I>, <I>b</I>) makes fewer than<I> k</I> recursive calls.      <P>
We can show that the upper bound of Theorem 33.11 is the best possible. Consecutive Fibonacci numbers are a worst-case input for <FONT FACE="Courier New" SIZE=2>EUCLID</FONT>. Since <FONT FACE="Courier New" SIZE=2>Euclid</FONT> (<I>F</I><SUB>3</SUB>, <I>F</I><SUB>2</SUB>) makes exactly one recursive call, and since for<I> k</I> <img src="../images/gteq.gif"> 2 we have <I>F<SUB>k</I>+1</SUB> mod <I>F<SUB>k</I></SUB> = <I>F<SUB>k-</I>1</SUB>, we also have<P>
<pre>gcd(<I>F<SUB>k</I>+1</SUB>,<I>F<SUB>k</I></SUB>)  =  gcd(<I>F<SUB>k</I></SUB>, (<I>F<SUB>k</I>+1</SUB> mod <I>F<SUB>k</I></SUB>))</sub></sup></pre><P>
<pre>=  gcd(<I>F<SUB>k</I></SUB>,<I> F<SUB>k</I>-1</SUB>) .</sub></sup></pre><P>
Thus, <FONT FACE="Courier New" SIZE=2>Euclid</FONT>(<I>F<SUB>k</I>+1</SUB>,<I>F<SUB>k</I></SUB>) recurses <I>exactly k</I> - 1 times, meeting the upper bound of Theorem 33.11.<P>
Since <I>F<SUB>k</I></SUB> is approximately <img src="811_a.gif">, where <img src="../images/phicap12.gif"> is the golden ratio <img src="811_b.gif"> defined by equation (2.14), the number of recursive calls in <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> is <I>O</I>(lg <I>b</I>). (See Exercise 33.2-5 for a tighter bound.) It follows that if <FONT FACE="Courier New" SIZE=2>EUCLID</FONT> is applied to two <img src="../images/beta14.gif"><I></I>-bit numbers, then it will perform <I>O</I>(<img src="../images/beta14.gif"><I></I>) arithmetic operations and <I>O</I>(<img src="../images/beta14.gif"><I><SUP></I>3</SUP>) bit operations (assuming that multiplication and division of <img src="../images/beta14.gif"><I></I>-bit numbers take <I>O</I>(<img src="../images/beta14.gif"><I><SUP></I>2</SUP>) bit operations). Problem 33-2 asks you to show an <I>O</I>(<img src="../images/beta14.gif"><I><SUP></I>2</SUP>) bound on the number of bit operations.<P>
<P>







<h2>The extended form of Euclid's algorithm</h2><P>
We now rewrite Euclid's algorithm to compute additional useful information. Specifically, we extend the algorithm to compute the integer coefficients <I>x</I> and <I>y</I> such that<P>