6.006 Lecture 11: Integer Arithmetic, Karatsuba Multiplication

Lecture 11: Numerics I Lecture Overview • Irrationals p • Newton’s Method ( (a), 1/b) • High precision multiply ← Irrationals: Pythagoras discovered that a square’s diagonal and its side are incommensurable, i.e., could not be expressed as a ratio - he called the ratio “speechless”! 1 √2 1 Figure 1: Ratio of a Square’s Diagonal to its Sides. Pythagoras worshipped numbers “All is number” Irrationals were a threat! Motivating Question: Are there hidden patterns in irrationals? √ 2 = 1. 414 213 562 373 095 048 801 688 724 209 698 078 569 671 875 Can you see a pattern? 1 Digression Catalan numbers: Set P of balanced parentheses strings are recursively defined as • λ ∈ P (λ is empty string) • If α, β ∈ P , then (α)β ∈ P Every nonempty balanced paren string can be obtained via Rule 2 from a unique α, β pair. For example, (()) ()() obtained by ( () ) ()() |{z} |{z} α β Enumeration Cn : number of balanced parentheses strings with exactly n pairs of parentheses C0 = 1 empty string Cn+1 ? Every string with n + 1 pairs of parentheses can be obtained in a unique way via rule 2. One paren pair comes explicitly from the rule. k pairs from α, n − k pairs from β Cn+1 = n X Ck · Cn−k n≥0 k=0 C0 = 1 C1 = C0 2 = 1 C2 = C 0 C1 + C1 C0 = 2 C3 = · · · = 5 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368 2 Newton’s Method Find root of f (x) = 0 through successive approximation e.g., f (x) = x2 − a xi xi+1 y = f(x) Figure 2: Newton’s Method. Tangent at (xi , f (xi )) is line y = f (xi ) + f 0 (xi ) · (x − xi ) where f 0 (xi ) is the derivative. xi+1 = intercept on x-axis f (xi ) xi+1 = xi − 0 f (xi ) Square Roots f (x) = x2 − a 2 χi+1 = χi − (χi − a) = 2χi χi + a χi 2 Example χ0 χ1 χ2 χ3 χ4 = 1.000000000 = 1.500000000 = 1.416666666 = 1.414215686 = 1.414213562 a=2 Quadratic convergence, ] digits doubles. Of course, in order to use Newton’s method, we need high-precision division. We’ll start with multiplication and cover division in Lecture 12. 3 High Precision Computation √ 2 to d-digit precision: 1| .414213562373 {z }··· √d digits √ d Want integer b10 2c = b 2 · 102d c - integral part of square root Can still use Newton’s Method. High Precision Multiplication Multiplying two n-digit numbers (radix r = 2, 10) 0 ≤ x, y < rn x = x1 · rn/2 + x0 y = y1 · r n/2 + y0 0 ≤ x0 , x1 < r x1 = high half x0 = low half n/2 0 ≤ y0 , y1 < rn/2 z = x · y = x1 y1 · rn + (x0 · y1 + x1 · y0 )rn/2 + x0 · y0 =⇒ quadratic algorithm θ(n2 ) time 4 multiplications of half-sized ]’s Karatsuba’s Method log2n log2n 3T(n/2) 3log n = nlog 3 4T(n/2) log n 4 = nlog 4 = n2 2 2 2 Figure 3: Branching Factors. 4 2 Let z0 = x0 · y0 z2 = x1 · y1 z1 = (x0 + x1 ) · (y0 + y1 ) − z0 − z2 = x0 y1 + x1 y0 z = z2 · rn + z1 · rn/2 + z0 There are three multiplies in the above calculations. T (n) = time to multiply two n-digit]0 s = 3T (n/2) + θ(n)

= θ nlog2 3 = θ n1.5849625··· This is better than θ(n2 ). Python does this, and more (see Lecture 12). Fun Geometry Problem B 1 C D A 1000,000,000,000 Figure 4: Geometry Problem. BD = 1 What is AD? AD = AC − CD = 500, 000, 000, 000 − s 500, 000, 000, 0002 − 1 | {z } a Let’s calculate AD to a million places. (This assumes we have high-precision division, which we will cover in Lecture 12.) Remarkably, if we evaluate the length 5 to several hundred digits of precision using Newton’s method, the Catalan numbers come marching out! Try it at: http://people.csail.mit.edu/devadas/numerics_demo/chord.html. An Explanation This was not covered in lecture and will not be on a test. Let’s start by looking at the power series of a real-valued function Q. Q(x) = c0 + c1 x + c2 x2 + c3 x3 + . . . (1) Then, by ordinary algebra, we have: 1 + xQ(x)2 = 1 + c20 x + (c0 c1 + c1 c0 )x2 + (c0 c2 + c1 c1 + c2 c0 )x3 + . . . (2) Now consider the equation: Q(x) = 1 + xQ(x)2 (3) For this equation to hold, the power series of Q(x) must equal the power series of 1 + xQ(x)2 . This happens only if all the coefficients of the two power series are equal; that is, if: c0 = 1 (4) c1 = c20 (5) c2 = c0 c1 + c1 c0 (6) c3 = c0 c2 + c1 c1 + c2 c0 (7) etc. (8) In other words, the coefficients of the function Q must be the Catalan numbers! We can solve for Q using the quadratic equation: Q(x) = 1± √ 1 − 4x 2x Let’s use the negative square root. From this formula for Q, we find: 6 (9) √ 1 − 4 · 10−24 10−12 · Q(10−24 ) = 10−12 · −24 2 · 10√ = 500000000000 − 5000000000002 − 1 1± (10) (11) From the original power-series expression for Q, we find: 10−12 · Q(10−24 ) = c0 10−12 + c1 10−36 + c2 10−60 + c3 10−84 + . . . (12) √ Therefore, 500000000000 − 5000000000002 − 1 should contain a Catalan number in every twenty-fourth position, which is what we observed. 7