Ancient Wisdom: Primes, Continued Fractions, The Golden Ratio, and Euclid’s GCDSlide 2Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Multiplication might just be a “one-way” function Multiplication is fast to compute Reverse multiplication is apparently slowGrade School GCD algorithmHow to find GCD(A,B)?Slide 7Slide 8Ancient Recursion: Euclid’s GCD algorithmA small exampleSlide 11Does the algorithm stop?Important questions to askBut is it correct?Slide 15Slide 16Slide 17Slide 18Slide 19Euclid’s GCD TerminationSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Let <r,s> denote the number r*67 + s*29. Calculate all intermediate values in this representation.Slide 30Euclid’s Extended GCD algorithm Input: X,Y Output: r,s,d such that rX+sY = d = GCD(X,Y)Slide 32Slide 33Slide 34Slide 35Leonardo FibonacciInductive Definition or Recurrence Relation for the Fibonacci NumbersA (Simple) Continued Fraction Is Any Expression Of The Form:A Continued Fraction can have a finite or infinite number of terms.A Finite Continued FractionAn Infinite Continued FractionRecursively Defined Form For CFAncient Greek Representation: Continued Fraction RepresentationSlide 44Slide 45Slide 46Slide 47A Pattern?Slide 49Slide 50An infinite continued fractionQuadratic EquationsSlide 53A Periodic CFSlide 55Slide 56Non-periodic CFsWhat is the pattern?Slide 59Slide 60Slide 61More good news: ConvergentsBest Approximator TheoremBest Approximators of Golden Ratio: the divine proportionGolden ratio supposed to arise in…PentagonDefinition of (Euclid)Expanding RecursivelySlide 70Slide 71Continued Fraction RepresentationSlide 73Remember?1,1,2,3,5,8,13,21,34,55,….Continued fraction representation of a standard fractione.g., 67/29 = 2 with remainder 9/29 = 2 + 1/ (29/9)A Representational CorrespondenceEuclid’s GCD = Continued FractionsFibonacci Magic TrickREFERENCESStudy BeeAncient Wisdom: Primes, Continued Fractions, The Golden Ratio, and Euclid’s GCDGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2005Lecture 12 Oct 6, 2005 Carnegie Mellon University3 13 13123131313131313133 ....+= ++++++++++Definition: A number > 1 is prime if it has no other factors, besides 1 and itself.Each number can be factored into primes in a unique way. [Euclid]Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Definition: A number > 1 is prime if it has no other factors, besides 1 and itself. Primes: 2, 3, 5, 7, 11, 13, 17, …Factorizations:42 = 2 * 3 * 784 = 2 * 2 * 3 * 713 = 13Multiplication might just be a “one-way” functionMultiplication is fast to computeReverse multiplication is apparently slowWe have a feasible method to multiply 1000 bit numbers [Egyptian multiplication]Factoring the product of two random 1000 bit primes has no known feasible approach.Grade School GCD algorithmGCD(A,B) is the greatest common divisor, i.e., the largest number that goes evenly into both A and B.What is the GCD of 12 and 18?12 = 22 * 3 18 = 2*32Common factors: 21 and 31Answer: 6How to find GCD(A,B)?A Naïve method:Factor A into prime powers. Factor B into prime powers.Create GCD by multiplying together each common prime raised to the highest power that goes into both A and B.Hang on!This requires factoring A and B. No one knows a particularly fast way to factor numbers in general.EUCLID had a much better way to compute GCD!Ancient Recursion: Euclid’s GCD algorithmEuclid(A,B)If B=0 then return A else return Euclid(B, A mod B)A small exampleNote: GCD(67, 29) = 1Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)A small exampleNote: GCD(67, 29) = 1Euclid(67,29) 67 mod 29 = 9Euclid(29,9) 29 mod 9 = 2Euclid(9,2) 9 mod 2 = 1 Euclid(2,1) 2 mod 1 = 0 Euclid(1,0) outputs 1Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Does the algorithm stop?Claim: After first step, A B 0Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Important questions to askIs the algorithm correct?Does the algorithm stop?How many steps does the algorithm run for?But is it correct?Claim: GCD(A,B) = GCD(B, A mod B)Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)But is it correct?Claim: GCD(A,B) = GCD(B, A mod B)value of GCD isan invariant!Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)But is it correct?Claim: GCD(A,B) = GCD(B, A mod B)d|A and d|B d| (A - kB )The set of common divisors of A, B equalsthe set of common divisors of B, A-kB. Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Does the algorithm stop?Claim: A mod B < ½ AEuclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Does the algorithm stop?Claim: A mod B < ½ AProof: If B > ½ A then A mod B = A - B < ½ A If B < ½ A then any X Mod B < B < ½ A If B = ½ A then A mod B = 0 Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Does the algorithm stop?GCD(A,B) calls GCD(B, A mod B)Less than ½ of AEuclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Euclid’s GCD TerminationGCD(A,B) calls GCD(B, <½A)Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Euclid’s GCD TerminationGCD(A,B) calls GCD(B, <½A)which calls GCD(<½A, B mod <½A)Less than ½ of AEuclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Euclid’s GCD TerminationEvery two recursive calls, the input numbers drop by half. Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Euclid’s GCD TerminationTheorem: If two input numbers have an n bit binary representation, Euclid’s Algorithm will not take more than 2n calls to terminate. Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Important questions to askIs the algorithm correct?Does the algorithm stop?How many steps does the algorithm run for?Trick Question:If X and Y are less than n, what is a reasonable upper bound on the number of recursive calls that Euclid(X,Y) will make?.Answer:If X and Y are less than n, Euclid(X,Y) will make no more than 2log2n calls.Euclid(67,29) 67 – 2*29 = 67 mod 29 = 9Euclid(29,9) 29 – 3*9 = 29 mod 9 = 2Euclid(9,2) 9 – 4*2 = 9 mod 2 = 1Euclid(2,1) 2 – 2*1 = 2 mod 1 = 0Euclid(1,0) outputs 1Euclid(A,B)If B=0 then return A else return Euclid(B, A mod B)Let <r,s> denote the number r*67 + s*29. Calculate all intermediate values in this representation.67 29 Euclid(67,29) 9Euclid(29,9)
View Full Document