Recursive Algorithm and Recurrence Relations Instructor:Sheng Zhong December 9,2020 1 Karatsuba Algorithm:One Example of Recursive Algorithms We learned multiplication in primary school.When we do 12 x 34,we essentially calculate 1 x 2 x 100+(2 x 3+1×4)×l0+2×4.In general,.we use the formula 2n-2 =01=0 where b=10 for decimal calculations,while b is often equal to some power of 2 in computers.This naive algorithm needs to do(2n-1)(n-1)"basic"multiplications (i.e.,multiplications over [0,b-1])in order to multiply two number from0-1].Naturally,one might suspect this is the best we could do,because there seems no obvious way to do it faster. Surprisingly,Russian mathematician Anatoly Karatsuba proposed a counter-intuitive algorithm that easily beats the naive algorithm for multiplication.The idea is quite simple:when you do 12 x 34,you should not waste your time doing two "basic"multiplications for(2 x 3+1 x 4).In stead,you should just calculate (1+2)×(3+4)-1×4-2×3,which is identical to(2×3+1×4).Noticing that you have to calculate 1 x 4 and 2x 3 for other parts of the expression anyway,for this specific part you just need to do one "basic" multiplication!Therefore,we have reduced the total amount of work. Below we present a straightforward recursive algorithm based on Karatsuba's idea. Algorithm karatsuba(,y) if (x <2)or (y 20) return xy; split in the middle and get (h,l); split y in the middle and get (hy,ly); ro karatsuba(lz,ly); r1=karatsuba((l+hz),(ly +hy)); r2 karatsuba(h,hy); return the number r2·22b+(r1-T2-ro）.2b+ro:
Recursive Algorithm and Recurrence Relations Instructor: Sheng Zhong December 9, 2020 1 Karatsuba Algorithm: One Example of Recursive Algorithms We learned multiplication in primary school. When we do 12 × 34, we essentially calculate 1 × 2 × 100 + (2 × 3 + 1 × 4) × 10 + 2 × 4. In general, we use the formula ( nX−1 i=0 xi · b i ) · ( nX−1 i=0 yi · b i ) = 2 Xn−2 i=0 ( X i j=0 xjyi−j ) · b i , where b = 10 for decimal calculations, while b is often equal to some power of 2 in computers. This naive algorithm needs to do (2n − 1)(n − 1) “basic”multiplications (i.e., multiplications over [0, b − 1]) in order to multiply two number from [0, bn−1 − 1]. Naturally, one might suspect this is the best we could do, because there seems no obvious way to do it faster. Surprisingly, Russian mathematician Anatoly Karatsuba proposed a counter-intuitive algorithm that easily beats the naive algorithm for multiplication. The idea is quite simple: when you do 12 × 34, you should not waste your time doing two “basic” multiplications for (2 × 3 + 1 × 4). In stead, you should just calculate (1 + 2) × (3 + 4) − 1 × 4 − 2 × 3, which is identical to (2 × 3 + 1 × 4). Noticing that you have to calculate 1 × 4 and 2 × 3 for other parts of the expression anyway, for this specific part you just need to do one “basic” multiplication! Therefore, we have reduced the total amount of work. Below we present a straightforward recursive algorithm based on Karatsuba’s idea. Algorithm karatsuba(x, y) if (x < 2 b ) or (y < 2 b ) return xy; split x in the middle and get (hx, lx); split y in the middle and get (hy, ly); r0 = karatsuba(lx, ly); r1 = karatsuba((lx + hx),(ly + hy)); r2 = karatsuba(hx, hy); return the number r2 · 2 2b + (r1 − r2 − r0) · 2 b + r0. 1
Now,assume that each"basic"multiplication is on a couple of b-bit integers,and that the Karatsuba algorithm needs T(n)"basic"multiplications on a couple of n-bit numbers.Assuming the multiplication of le+h and ly+hy requires no more"basic"multiplication than the multiplication ofl and ly(or that of h and hy),we get the following equation: Tm)=37(5, (1) It is trivial to derive from the above equation that T(n)=3og2T(b)=()og23nlog23,assuming b is small and n is big.In contrast,the naive algorithm needs at least n2"basic"multiplications.For large n,the difference can be very significant. The Karatsuba algorithm is the beginning of a search for formulae that helps reduce the computational cost of multiplication.Many more formulae have been found since then.For example,in 2009,Fan and his collaborators developed a number of Karatsuba-like formulae,including some asymmtric ones.Interested readers can refer to[6]. One might find it interesting to solve recurrence relations like Eq.(1).It turns out that there is no universal approach to solve all recurrence equations.Hereafter we examine a few types of recurrences that we know how to solve. 2 Recurrences,Total and Particular Solutions We say a recurrence is linear if T(n)is equal to a linear combination of T(m)s (m n).For a large class of linear recurrences,we happen to know the structure of their solutions,which is quite analogous to that of linear system solutions. Theorem 1 The set of solutions to the linear recurrence T(m)=∑cT(an+b)+d(n,(n≥no) (2) i=1 (where ain +bi n for all i and all n no)is {To(n)+T(n)To(n)=>cTo(ain+bi)}, =1 where T(n)is an arbitrary solution to Equation (2).Since T(n)itself belongs to the set of solutions,we usually call it a particular solution and the set of all solutions the total solution. Hereafter,we are sloppy in writing things like T(because T is defined on positive integers butmay not be an integer.However. all our discussions hold when we replace with and do some minor modifications.Hence,to keep it simple,we use expressions like T()as if they were legal
Now, assume that each “basic” multiplication is on a couple of b-bit integers, and that the Karatsuba algorithm needs T(n) “basic” multiplications on a couple of n-bit numbers.Assuming the multiplication of lx + hx and ly + hy requires no more “basic” multiplication than the multiplication of lx and ly (or that of hx and hy), we get the following equation:1 T(n) = 3T( n 2 ). (1) It is trivial to derive from the above equation that T(n) = 3log2 n b T(b) = (n b ) log2 3 ≈ n log2 3 , assuming b is small and n is big. In contrast, the naive algorithm needs at least n 2 “basic” multiplications. For large n, the difference can be very significant. The Karatsuba algorithm is the beginning of a search for formulae that helps reduce the computational cost of multiplication. Many more formulae have been found since then. For example, in 2009, Fan and his collaborators developed a number of Karatsuba-like formulae, including some asymmtric ones. Interested readers can refer to [6]. One might find it interesting to solve recurrence relations like Eq. (1). It turns out that there is no universal approach to solve all recurrence equations. Hereafter we examine a few types of recurrences that we know how to solve. 2 Recurrences, Total and Particular Solutions We say a recurrence is linear if T(n) is equal to a linear combination of T(m)s (m < n). For a large class of linear recurrences, we happen to know the structure of their solutions, which is quite analogous to that of linear system solutions. Theorem 1 The set of solutions to the linear recurrence T(n) = X k i=1 ciT(ain + bi) + d(n),(n ≥ n0) (2) (where ain + bi < n for all i and all n ≥ n0) is {T0(n) + T1(n)|T0(n) = X k i=1 ciT0(ain + bi)}, where T1(n) is an arbitrary solution to Equation (2). Since T1(n) itself belongs to the set of solutions, we usually call it a particular solution and the set of all solutions the total solution. 1Hereafter, we are sloppy in writing things like T( n 2 ) because T is defined on positive integers but n 2 may not be an integer. However, all our discussions hold when we replace n 2 with b n 2 c and do some minor modifications. Hence, to keep it simple, we use expressions like T( n 2 ) as if they were legal. 2
Proof:Consider T(m)=∑T(a:n+b) (3) i=1 Equation (3)has all terms being of degree 1,and is thus called a homogeneous equation.Suppose To(n)is a solution to Equation(3)and T1(n)a solution to Equation(2).Easy to get that Ti(n)+To(n)= ∑c五(a,n+b)+d(n)+∑aT(ain+b) i=1 =1 k >ci(Ti(ain+bi)+To(ain+bi))+d(n). =1 Hence,Ti(n)+To(n)must also be a solution to Equation (2). Conversely,if T2(n)is a solution to Equation (2),we can easily verify that T2(n)-T1(n)is a solution to Equation(3).Therefore,T2(n)can be written as the sum of T1(n),a particular solution,and a solution to the homogenous equation. 口 Example 1 Solve the recurrence T=2T()-1. Solution:Clearly the corresponding homogeneous equation has solutions To(n)=kn where k is an arbitrary constant.A particular solution is T(n)=1.Hence,the total solution is T(n)=kn +1. ▣ Nevertheless,homogeneous equations are not always so easy to solve.In many cases,we do not know how to solve it and have to rely on the"guess-and-prove"stragtegy.Below we discuss one(unusual)type of homogeneous equations for which we do have a systematic approach. Definition 1 Consider the homogeneous equation T(n)=cT(m-1)+c2T(n-2)+..+ckT(n-k), (4) where k is a constant positive integer,c1,...,ck are all constants,and cick 0.We say Equation (4)is a linear homogeneous recurrence with constant coefficients of order k.Its characteristic equation is kciak-1-c2xk-2...-ck 0. (5) If you have studied linear algebra,please compare the above definition with the characteristic equation of a real symmetric matrix.If you have studied differential equations,please compare the above definition with the characteristic equation of a linear differential equation with constant coefficients of order k.The comparison will help you understand the deep connection between Equations(4)and(5),which is reflected by the theorem below. Theorem 2 If Equations (5)has k distinct roots r1,...,rk.then the solutions to Equation (4)are To(n)=air?a2r2 +...akre, where a1,...,ak are constants.There is no other solution to Equation (4)
Proof: Consider T(n) = X k i=1 ciT(ain + bi). (3) Equation (3) has all terms being of degree 1, and is thus called a homogeneous equation. Suppose T0(n) is a solution to Equation (3) and T1(n) a solution to Equation (2). Easy to get that T1(n) + T0(n) = X k i=1 ciT1(ain + bi) + d(n) +X k i=1 ciT0(ain + bi) = X k i=1 ci(T1(ain + bi) + T0(ain + bi)) + d(n). Hence, T1(n) + T0(n) must also be a solution to Equation (2). Conversely, if T2(n) is a solution to Equation (2), we can easily verify that T2(n) − T1(n) is a solution to Equation (3). Therefore, T2(n) can be written as the sum of T1(n), a particular solution, and a solution to the homogenous equation. Example 1 Solve the recurrence T(n) = 2T( n 2 ) − 1. Solution: Clearly the corresponding homogeneous equation has solutions T0(n) = kn where k is an arbitrary constant. A particular solution is T1(n) = 1. Hence, the total solution is T(n) = kn + 1. Nevertheless, homogeneous equations are not always so easy to solve. In many cases, we do not know how to solve it and have to rely on the “guess-and-prove” stragtegy. Below we discuss one (unusual) type of homogeneous equations for which we do have a systematic approach. Definition 1 Consider the homogeneous equation T(n) = c1T(n − 1) + c2T(n − 2) + . . . + ckT(n − k), (4) where k is a constant positive integer, c1, . . . , ck are all constants, and c1ck 6= 0. We say Equation (4) is a linear homogeneous recurrence with constant coefficients of order k. Its characteristic equation is x k − c1x k−1 − c2x k−2 − . . . − ck = 0. (5) If you have studied linear algebra, please compare the above definition with the characteristic equation of a real symmetric matrix. If you have studied differential equations, please compare the above definition with the characteristic equation of a linear differential equation with constant coefficients of order k. The comparison will help you understand the deep connection between Equations (4) and (5), which is reflected by the theorem below. Theorem 2 If Equations (5) has k distinct roots r1, . . . , rk, then the solutions to Equation (4) are T0(n) = a1r n 1 + a2r n 2 + . . . + akr n k , where a1, . . . , ak are constants. There is no other solution to Equation (4). 3
Proof:First,since r1,...,rk are roots of Equation (5),for i=1,...,k,we have -car-1-c2r-2-.-c以=0→r=r-1+c2r-2+.+ekr-* Hence. To(n)air a2r2+...+akre =a1(Gr1-1+c2r-2+.+cgr-k+.+ak(C1r-1+2r-2+.+cgr-) =G(a1r1-1+a2r2-1+.+ar-1)++c4(a11-k+a2r3-k++ar-k ciTo(n-1)+...+ckTo(n-k), which means To(n)satisfies Equations (4). Next,we show there is no other solution to Equation (4).Suppose S(n)is a solution to Equation(4),i.e., S(n)=cS(m-1)+c2S(n-2)+..+ckS(n-k) Now,consider the linear system (with unknowns a1,...,an) a1r1+a22+..+akTk=S(1) a1r+a2r吃+..+akr2 =S(2) airf +a2r+...+akr S(k). The coefficient matrix of the left hand side can be viewed as the product of a Vandermonde matrix and a diagonal matrix: T2 Tk 0 0 0 0 Tk Consequently,the coefficient matrix must be full-rank,and the linear system must have a(unique)solu- tion.When we use this solution as the constants in To(n),we are guaranteed that To(1)=S(1),To(2)= S(2),...,To(k)=S(k).A simple induction on n allows us to extend this result to To(n)=S(n)for all positive integer n,because both To()and S()satisfy the same recurrence. 口 Example 2 A function T:++satisfies the following conditions: ·For all n1,n2∈Z+such that ged(n1,n2)=1,T(n1n2）=T(m1)T(n2). ·For all m,n∈2+(m≥2，.T(mn)=ma- (T(mn-2庐. Find the function T
Proof: First, since r1, . . . , rk are roots of Equation (5), for i = 1, . . . , k, we have r k i − c1r k−1 i − c2r k−2 i − . . . − ck = 0 ⇒ r n i = c1r n−1 i + c2r n−2 i + . . . + ckr n−k i . Hence, T0(n) = a1r n 1 + a2r n 2 + . . . + akr n k = a1(c1r n−1 1 + c2r n−2 1 + . . . + ckr n−k 1 ) + . . . + ak(c1r n−1 k + c2r n−2 k + . . . + ckr n−k k ) = c1(a1r n−1 1 + a2r n−1 2 + . . . + akr n−1 k ) + . . . + ck(a1r n−k 1 + a2r n−k 2 + . . . + akr n−k k ) = c1T0(n − 1) + . . . + ckT0(n − k), which means T0(n) satisfies Equations (4). Next, we show there is no other solution to Equation (4). Suppose S(n) is a solution to Equation (4), i.e., S(n) = c1S(n − 1) + c2S(n − 2) + . . . + ckS(n − k). Now, consider the linear system (with unknowns a1, . . . , an) a1r1 + a2r2 + . . . + akrk = S(1) a1r 2 1 + a2r 2 2 + . . . + akr 2 k = S(2) . . . a1r k 1 + a2r k 2 + . . . + akr k k = S(k). The coefficient matrix of the left hand side can be viewed as the product of a Vandermonde matrix and a diagonal matrix: r1 r2 . . . rk r 2 1 r 2 2 . . . r2 k . . . . . . r k 1 r k 2 . . . rk k = 1 1 . . . 1 r1 r2 . . . rk . . . . . . r k−1 1 r k−1 2 . . . rk−1 k r1 0 . . . 0 0 r2 . . . 0 . . . . . . 0 0 . . . rk . Consequently, the coefficient matrix must be full-rank, and the linear system must have a (unique) solution. When we use this solution as the constants in T0(n), we are guaranteed that T0(1) = S(1), T0(2) = S(2), . . . , T0(k) = S(k). A simple induction on n allows us to extend this result to T0(n) = S(n) for all positive integer n, because both T0() and S() satisfy the same recurrence. Example 2 A function T : Z + → Z+ satisfies the following conditions: • For all n1, n2 ∈ Z+ such that gcd(n1, n2) = 1, T(n1n2) = T(n1)T(n2). • For all m, n ∈ Z+ (n ≥ 2), T(mn ) = (T(mn−1 ))3 (T(mn−2))2 . Find the function T. 4
Solution:Consider an aay prime Since Tdefining()og),we get that S(n)=3S(n-1)-2S(n-2).The characteristic equation of this recurrence is x2-3x+2 =0,which has two distinct roots 1 and 2.Hence,the solution to this recurrence is S(n)=ap2n+bp,where ap,bp are constants. From T(1)T(n)=T(n),we easily get that T(1)=1.Hence S(0)=0,which means bp =-ap.Thus, S(n)=ap(2n-1),i.e.,T(p")=(2"-1)=(T(p))2"-1.For a general positive integer p"...where p1..&are primes,T(p)=(T(p))2-1...(T(pK))2-1.The value of T(p)for each prime p can be arbitrarily chosen from positive integers. Theorem 2 perfectly solves Equation(4)when the characteristic equation has distinct roots.But in reality,we often have double roots and triple roots.What can we do then?Fortunately,we have another theorem that takes care of multiple roots. Theorem 3 If Equations (5)has e roots r1,...,re,where ri is of multiplicity mi for i =1,...,e,then the solutions to Equation (4)are To(n) (a1+ai,2n+..+a,mnm-1)r, i=1 where aijs are all constants.There is no other solution to Equation (4). The proof of Theorem 3 is quite similar to that of Theorem 2.There are two major differences: Since ri is a root of multiplicity mi,on top of -g11-2-2-.-4=0, we also have kr5-1-a1(k-1)r-2-c2(k-2)r-3-.-ck-1=0, k(k-1)..(k-mi+2)r-m+1-c(k-1).(k-m+1)r-m-..ck-m+1(mi-11=0. These equations help us to show that To(n)satisfies the recurrence. A generalization of Vandermonde matrix is confluent Vandermonde matrix [12],which is also full-rank. Theorems 2 and 3 tell us how to solve homogeneous equations.To get the total solution of Equation(2), we still need find a particular solution.The bad news is that we do not have a systematic approach of finding a particular solution.The best we can do is only slightly better than the guess-and-prove method:the method of undetermined coefficients.It is slightly better in that we only need to guess what kind of function could be a particular solution,not the parameters of the function.As long as our guess is correct,the method of undertermined coefficients can help us correctly calculate the parameters of the function.Below we demonstrate how the method undetermined coefficients works. Example 3 Solve the recurrence nm=雪a-+营ra-g+-告m+号+
Solution: Consider an arbitrary prime p. Since T(p n ) = (T(p n−1 ))3 (T(pn−2))2 , defining S(n) = log T(p n ), we get that S(n) = 3S(n − 1) − 2S(n − 2). The characteristic equation of this recurrence is x 2 − 3x + 2 = 0, which has two distinct roots 1 and 2. Hence, the solution to this recurrence is S(n) = ap2 n + bp, where ap, bp are constants. From T(1)T(n) = T(n), we easily get that T(1) = 1. Hence S(0) = 0, which means bp = −ap. Thus, S(n) = ap(2n − 1), i.e., T(p n ) = 2ap(2n−1) = (T(p))2 n−1 . For a general positive integer p n1 1 . . . p nk k where p1, . . . , pk are primes, T(p n1 1 . . . p nk k ) = (T(p1))2 n1−1 . . .(T(pk))2 nk −1 . The value of T(p) for each prime p can be arbitrarily chosen from positive integers. Theorem 2 perfectly solves Equation (4) when the characteristic equation has distinct roots. But in reality, we often have double roots and triple roots. What can we do then? Fortunately, we have another theorem that takes care of multiple roots. Theorem 3 If Equations (5) has ` roots r1, . . . , r` , where ri is of multiplicity mi for i = 1, . . . , `, then the solutions to Equation (4) are T0(n) = X ` i=1 (ai,1 + ai,2n + . . . + ai,min mi−1 )r n i , where aij s are all constants. There is no other solution to Equation (4). The proof of Theorem 3 is quite similar to that of Theorem 2. There are two major differences: • Since ri is a root of multiplicity mi , on top of r k i − c1r k−1 i − c2r k−2 i − . . . − ck = 0, we also have krk−1 i − c1(k − 1)r k−2 i − c2(k − 2)r k−3 i − . . . − ck−1 = 0, . . . k(k − 1). . .(k − mi + 2)r k−mi+1 i − c1(k − 1). . .(k − mi + 1)r k−mi i − . . . ck−mi+1(mi − 1)! = 0. These equations help us to show that T0(n) satisfies the recurrence. • A generalization of Vandermonde matrix is confluent Vandermonde matrix [12], which is also full-rank. Theorems 2 and 3 tell us how to solve homogeneous equations. To get the total solution of Equation (2), we still need find a particular solution. The bad news is that we do not have a systematic approach of finding a particular solution. The best we can do is only slightly better than the guess-and-prove method: the method of undetermined coefficients. It is slightly better in that we only need to guess what kind of function could be a particular solution, not the parameters of the function. As long as our guess is correct, the method of undertermined coefficients can help us correctly calculate the parameters of the function. Below we demonstrate how the method undetermined coefficients works. Example 3 Solve the recurrence T(n) = e 3 2 T(n − 1) + e 6 2 T(n − 2) + (1 − e 3 + e 6 2 )en + e 4 2 + e 7 . 5