![]() ![]() Let us solve this recurrence by an iterative approach. Recurrence equation for this problem is given as, Return c 2*10 n + (x – c 2 – c 0) * 10 n/2 + c 0 end Complexity Analysisįor n digit integer, we have to perform 3 multiplications of integers of size (n / 2). X ← DC_ CLEVER_MULTIPLICATION(a 1 + a 0, b 1 + b 0) Input : Number A and B, where A = an-1…a1a0, and B = bn-1.b1b0Ĭ 2 ← DC_ CLEVER_MULTIPLICATION(a 1, b 1)Ĭ 0 ← DC_ CLEVER_MULTIPLICATION(a 0, b 0) This can be solved by applying recursion till n reaches to 1. If size of integer is n digit, then we can generalize multiplication as, This formulation leads to same result, with three multiplications only. It is same as c 1 = (a 1*b 0 + a 0*b 1) of dumb multiplication approach, but does only one multiplication rather than two. = (a 1b 1 + a 1b 0 + a 0b 1 + a 0b 0) – (a 1b 1 + a 0b 0)Įquation (1) and Equation (2) are the same, but the second approach of computing c1 involves only one multiplication rather than two as it requires in the first approach. Let’s reformulate it to reduce numbers of multiplications to three.Ĭ 1 = (a 1 + a 0) * (b 1 + b 0) – (c 2 + c 0) Previous DC approach does four multiplications. Size of both operands must be even, so pad zero to the multiplier.Ī = a 1a 0 = 2345, hence a 1 = 23 and a 0 = 45ī = b 1b 0 = 0678, hence b 1 = 06 and b 0 = 78 Return c 2*10 n + c 1 * 10 n/2+ c 0 end Example: Multiply 2345 with 678 using divide and conquer approach. N ← max(|A|, |B|) // returns maximum number digits Output : Multiplication of A and B as C, i.e. Input : Number A and B, where A = an-1…a1a0, Description : Perform multiplication of large numbers using divide and conquer strategy. Algorithm for this approach is described below : Algorithm DC_DUMB_MULTIPLICATION(A, B) This is as dumb as grade school multiplication. This method does four multiplications, same as conventional method. If we consider A = a 1a 0 and B = b 1b 0, then Let’s derive formula to multiply two numbers of two digits each. Each digit d i is the i th least significant digit in number D. Let us represent number D as D = d n -1d n-2. Second method – we call clever approach – performs better then the traditional approach for integer multiplication. The first method – we call dumb method – does not improve the running time. There are two ways to perform large integer multiplication using divide and conquer. Large Integer Multiplication using Divide and Conquer Approach Let’s look into a more convenient method of multiplication. This technique takes quadratic time, which is insufficient for big numbers. If multiplicand has n digits and multiplier has m digits, the complexity of multiplication would be O(mn). This approach is simple to grasp, yet it is time-consuming and inefficient. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |