Mastering Euclid's Algorithm in Discrete Math
Dive deep into Euclid's Algorithm for finding the Greatest Common Divisor in Discrete Math. Understand the concepts, proof of algorithms, and example runs. Learn about termination conditions, correctness, and efficiency of Euclid's Algorithm.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Proofs for algorithms: Euclid s algorithm Section 3.7 in Jenkyns, Stephenson
GCD GCD = Greatest Common Divisor GCD(a,b): largest n such that n|a and n|b One way to compute it: Factor a,b to prime factors n = product of common prime factors No efficient way to do so (since we don t know how to factor to prime numbers efficiently) Euclid s algorithm provides a much faster way
Euclids algorithm Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) 1. While b>0: a. x=a mod b b. a=b c. b=x 2. Return a
Euclids algorithm Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) 1. While b>0: a. x=a mod b b. a=b c. b=x 2. Return a (a,b) (b,a mod b)
Euclids algorithm Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) 1. While b>0: ?,? (?,? ??? ?) 2. Return a
Euclids algorithm Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) Example run: a=20, b=30 a 20 30 20 10 b 30 20 10 0 1. While b>0: ?,? (?,? ??? ?) 2. Return a
Euclids algorithm The same basic questions 1. Does it always terminate? 2. Does it return the correct answer? 3. How fast is it?
Euclids algorithm: termination Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) Loop invariant (after 1st iteration): ? > ? 1. While ? > 0: ?,? (?,? ??? ?) 2. Return a
Euclids algorithm: termination Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) Loop invariant (after 1st iteration): ? > ? 1. While ? > 0: ?,? (?,? ??? ?) 2. Return a Loop beginning: (a,b) Loop end: (b, a mod b) By definition, ? ??? ? 0, ,? 1 and hence (a mod b) < b
Euclids algorithm: termination Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) Loop invariant (after 1st iteration): ? > ? 1. While ? > 0: ?,? (?,? ??? ?) 2. Return a The value of a keeps decreasing, which proves termination
Euclids algorithm: correctness Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) 1. While ? > 0: ?,? (?,? ??? ?) 2. Return a g=gcd(a,b)
Euclids algorithm: correctness Need to prove the following lemma Lemma: ?,? 1,gcd ?,? = gcd(?,? ??? ?)
Euclids algorithm: correctness Need to prove the following lemma Lemma: ?,? 1,gcd ?,? = gcd(?,? ??? ?) Proof: we will actually show ? 1, ? ? ? ? (? ? ? ? ??? ? ) In particular, the largest such m is (by definition) the GCD, and so gcd ?,? = gcd(?,? ??? ?)
Euclids algorithm: correctness Lemma: ?,? 1,gcd ?,? = gcd ?,? ??? ? Proof ( ): ? ? ? ? (? ? ? ? ??? ? ) Let ? = ?? + ?, where ? = ? ??? ?, ? = ? ??? ?. If ?|?,?|? then ? = ??, ? = ??, where ?,? ?. Then: ? ??? ? = ? = ? ?? = ?? ?? ? = ? ? ?? So, ?|(? ??? ?).
Euclids algorithm: correctness Lemma: ?,? 1,gcd ?,? = gcd ?,? ??? ? Proof ( ): ? ? ? ? (? ? ? ? ??? ? ) Let ? = ?? + ?, where ? = ? ??? ?, ? = ? ??? ?. If ?|?,?|? then b = ??, q = ??, where ?,? ?. Then: ? = ?? + ? = ?? ? + ?? = ?(?? + ?) So, ?|?.
Euclids algorithm: correctness Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) 1. While ? > 0: ?,? (?,? ??? ?) 2. Return a g=gcd(a,b) Proved!
Euclids algorithm: speed Euclid(a,b): Input: ?,? ? Output: ? = gcd(?,?) How many iterations? 1. While ? > 0: ?,? (?,? ??? ?) 2. Return a
Euclids algorithm: speed Consider one iteration: ?,? (?,? ??? ?) We know that a,b become smaller But by how much?
Euclids algorithm: speed Consider one iteration: ?,? (?,? ??? ?) We know that a,b become smaller But by how much? Intuition: Since ? ??? ? {0,..,? 1}, on average ? ??? ? ?/2. Hence, value of b decreases by a factor of 2 at each iteration (so log(b) iterations will be needed) Can we justify this?
Euclids algorithm: speed Consider one iteration: ?,? (?,? ??? ?) Lemma: ? + ? 3 2(? + ? ??? ? ) Sum decreases by 3/2 at each iteration; So, we need at most ~log(a+b) iterations In fact, at most ~log(b) iterations, since after the first iteration, both values are at most b
Euclids algorithm: speed Consider one iteration: ?,? (?,? ??? ?) Lemma: ? + ? 3 2(? + ? ??? ? ) Proof: Since ? > ? > ? ??? ?, and since b|? (? ??? ?), we must have ? ? ??? ? ?. So: (i) ? ? + (? ??? ?) (ii) ? =? 2? + ? ??? ? 2+? 2 1 ? + ? 3 2(? + ? ??? ? )
Extended Euclids algorithm Theorem: ?,? ? ?,? ? ?? + ?? = gcd(?,?) (this is called Extended Euclid s algorithm) Example: a=3, b=5, gcd(a,b)=1 3*(-3)+5*2 = 1 (solution: x=-3, y=2)
Extended Euclids algorithm Theorem: ?,? ? ?,? ? ?? + ?? = gcd(?,?) (this is called Extended Euclid s algorithm) Example: a=3, b=5, gcd(a,b)=1 3*(-3)+5*2 = 1 (solution: x=-3, y=2) The proof will use our analysis of Euclid s algorithm So, even though the theorem has nothing to do with algorithms, the proof will use an algorithm!
Extended Euclids algorithm Theorem: ? ? 1 ?,? ? ?? + ?? = gcd(?,?) Proof (by strong induction on b): Base case: b=1, so gcd(a,1)=a, can take x=1,y=1 Inductive case: Use the identity: gcd ?,? = gcd(?,? ??? ?) Since ? > ? ??? ?, by the inductive assumption ? ,? ?,?? + ? ??? ? ? = gcd b,a mod b = gcd ?,? Let ? = ?? + ?, where ? = ? ??? ?, ? = ? ??? ?. Then: ?? + ? ?? ? = gcd ?,? Take ? = ? ,? = ? ?? so that ?? + ?? = gcd ?,? .
Next class Relations Read section 6.1 in Jenkyns, Stephenson
