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