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.Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Multiplication 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 13Slide 14Ancient Recursion: Euclid’s GCD algorithmA small exampleBut is it correct?Does the algorithm stop?Slide 19Euclid’s GCD TerminationSlide 21Slide 22Slide 23Slide 24Slide 25EUCLID(A,B) // requires AB0 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.Euclid’s Extended GCD algorithm Input: X,Y Output: r,s,d such that rX+sY = d = GCD(X,Y)Slide 29Slide 30Slide 31Leonardo 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 40Slide 41Slide 42Slide 43A Pattern?Slide 45Slide 46An infinite continued fractionQuadratic EquationsA Periodic CFSlide 50Slide 51Non-periodic CFsWhat is the pattern?Slide 54Slide 55ConvergentsBest Approximator TheoremBest Approximators of 1.6180339887498948482045…..KhufuGreat Pyramid at GizehSlide 62Golden Ratio: the divine proportionParthenon, Athens (400 B.C.)PentagonRatio of height of the person to the height of a person’s navelDefinition of (Euclid)Slide 68The Divine QuadraticExpanding RecursivelySlide 71Slide 72Continued Fraction RepresentationSlide 74Remember?1,1,2,3,5,8,13,21,34,55,….Continued fraction representation of a standard fraction67/29 = 2 with remainder 9/29 = 2 + 1/ (29/9)A Representational CorrespondenceEuclid’s GCD = Continued FractionsTheorem: All fractions have finite continuous fraction expansionsFibonacci Magic TrickAnother Trick!REFERENCESAncient Wisdom:Primes, Continued Fractions, The Golden Ratio, and Euclid’s GCDGreat Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2005Lecture 12 Feb 17, 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 = 13Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Let n be the least counter-example. Hence, n has at least two ways of being written as a product of primes:n = p1 p2 .. pk = q1 q2 … qtThe p’s must be totally different primes than the q’s or else we could divide both sides by one of a common prime and get a smaller counter-example. Without loss of generality, assume p1 > q1 .Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Let n be the least counter-example. n = p1 p2 .. pk = q1 q2 … qt [with p1 > q1] n ¸ p1p1 > p1 q1 + 1 [since p1 > q1]m = n – p1q1 [hence 1 < m < n]Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Let n be the least counter-example. n = p1 p2 .. pk = q1 q2 … qt [with p1 > q1] n ¸ p1p1 > p1 q1 + 1 [since p1 > q1]m = n – p1q1 [hence 1 < m < n]Notice: m = p1(p2 .. pk – q1) = q1(q2 … qt - p1)Thus, p1|m and q1|mTheorem: Each natural has a unique factorization into primes written in non-decreasing order.Let n be the least counter-example. n = p1 p2 .. pk = q1 q2 … qt [with p1 > q1] n ¸ p1p1 > p1 q1 + 1 [since p1 > q1]m = n – p1q1 [hence 1 < m < n]Notice: m = p1(p2 .. pk – q1) = q1(q2 … qt - p1)Thus, p1|m and q1|mBy unique factorization of m, p1q1|m. Thus m = p1q1z We have: m = n – p1q1 = p1( p2 .. pk - q1 ) = p1q1zTheorem: Each natural has a unique factorization into primes written in non-decreasing order.Let n be the least counter-example. n = p1 p2 .. pk = q1 q2 … qt [with p1 > q1] n ¸ p1p1 > p1 q1 + 1 [since p1 > q1]m = n – p1q1 [hence 1 < m < n]Notice: m = p1(p2 .. pk – q1) = q1(q2 … qt - p1)Thus, p1|m and q1|mBy unique factorization of m, p1q1|m. Thus m = p1q1z We have: m = n – p1q1 = p1( p2 .. pk - q1 ) = p1q1z Dividing by p1 we obtain: ( p2 .. pk - q1 ) = q1z p2 .. pk = q1z + q1 = q1(z+1) q1|p2…pkTheorem: Each natural has a unique factorization into primes written in non-decreasing order.Let n be the least counter-example. n = p1 p2 .. pk = q1 q2 … qt [with p1 > q1] n ¸ p1p1 > p1 q1 + 1 [since p1 > q1]m = n – p1q1 [hence 1 < m < n]Notice: m = p1(p2 .. pk – q1) = q1(q2 … qt - p1)Thus, p1|m and q1|mBy unique factorization of m, p1q1|m. Thus m = p1q1z We have: m = n – p1q1 = p1( p2 .. pk - q1 ) = p1q1z Dividing by p1 we obtain: ( p2 .. pk - q1 ) = q1z p2 .. pk = q1z + q1 = q1(z+1) q1|p2…pkNow by unique factorization of p2…pk, q1 must be one of p2,…,pk. But this contradicts the fact that the p’s and q’s are disjoint.Multiplication 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) // requires AB0 If B=0 then return A else return Euclid(B, A mod B)A small
View Full Document