Fast MultiplicationObjectivesDivide et impera (Divide and Conquer)About the AlgorithmHow It WorksHow It Works (cont.)Slide 7Slide 8The “Old” WayNew WaySlide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23ObservationsSourcesQuestionsFast MultiplicationThe Divide and Conquer MethodOmar HemmaliObjectivesDefine Divide and ConquerExplain the Karatsuba Multiplication Method (Fast Multiplication)Work an example using the Karatsuba MethodDivide et impera(Divide and Conquer)A Divide and Conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly.The solutions to the sub-problems are then combined to give a solution to the original problem. [taken from wikipedia]About the AlgorithmDiscovered by Anatolii Karatsuba in 1960.Published in a joint paper with Yu. Ofman in 1962.O ( )Disproved Andrey Kolmogorov's 1956 conjecture that the fastest multiplication algorithm was O( )First Divide and Conquer AlgorithmHow It WorksAssume two numbers A, B in base 10A = B = m = half the number of digits in A,BHow It Works (cont.)Multiplying the four subproducts separately gives O( )Example: 25 * 16We can do better12 3 4How It Works (cont.)Let LetLetWhat? How?How It Works (cont.)Let LetLetNow only 3 multiplicationsSo123The “Old” WayMultiplyingNew Way1962 * 1960 = (19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = X0 Y0Z0New Way1962 * 1960 =X0 Y019 * 19 = (1 * 1) * 100 + (10 * 10 – X1 – Z1 ) * 10 + (9 * 9) =1X1 Y1 Z11 8181(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = Z0New Way1962 * 1960 =X0 Y019 * 19 = (1 * 1) * 100 + (10 * 10 – X1 – Z1 ) * 10 + (9 * 9) =1X1 Y1 Z11 818110 * 10 =(1 * 1) * 100 + (1 * 1 – X2 – Z2 ) * 10 + (0 * 0) =11001X2 Y2Z20100(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = Z0(1 * 1) * 100 + (10 * 10 – X1 – Z1 ) * 10 + (9 * 9) =New Way1962 * 1960 =X0 Y019 * 19 = 1X1 Y1 Z11 818110 * 10 =(1 * 1) * 100 + (1 * 1 – X2 – Z2 ) * 10 + (0 * 0) =11001X2 Y2Z20100100(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = Z018New Way1962 * 1960 =X0 Y019 * 19 = (1 * 1) * 100 + (10 * 10 – X1 – Z1 ) * 10 + (9 * 9) =1X1 Y1 Z11 8181100 18361(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = Z0(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = New Way1962 * 1960 =19 * 19 = (1 * 1) * 100 + (10 * 10 – X1 – Z1 ) * 10 + (9 * 9) =1X1 Y1 Z11 8181100 18361361X0361Y0Z0(6 * 6) * 100 + (8 * 6 – X1 – Z1 ) * 10 + (2 * 0) =0(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = New Way1962 * 1960 =361X0361Y0Z062 * 60 =X1 Y1 Z13636 048 12 3720(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = New Way1962 * 1960 =361X0361Y0Z062 * 60 = (6 * 6) * 100 + (8 * 6 – X1 – Z1 ) * 10 + (0 * 2) =X1 Y1 Z136120372037203720)(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = New Way1962 * 1960 =361X0361Y0Z03720372091 * 79 = (9 * 7) * 100 + (10 * 16 – X1 – Z1 ) * 10 + (1 * 9) =X1 Y1 Z16363993720)(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = New Way1962 * 1960 =361X0361Y0Z0372091 * 79 = (9 * 7) * 100 + (10 * 16 – X1 – Z1 ) * 10 + (1 * 9) =X1 Y1 Z163639910 * 16 =(1 * 1) * 100 + (1 * 7 – X2 – Z2 ) * 10 + (0 * 6) =X2 Y2Z21 1 00761603720)(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = New Way1962 * 1960 =361X0361Y0Z0372091 * 79 = (9 * 7) * 100 + (10 * 16 – X1 – Z1 ) * 10 + (1 * 9) =X1 Y1 Z163639910 * 16 =(1 * 1) * 100 + (1 * 7 – X2 – Z2 ) * 10 + (0 * 6) =X2 Y2Z21 1 00761601603720)(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = New Way1962 * 1960 =361X0361Y0Z0372091 * 79 = (9 * 7) * 100 + (10 * 16 – X1 – Z1 ) * 10 + (1 * 9) =X1 Y1 Z163639916088 71893720)(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = New Way1962 * 1960 =361X0361Y0Z0372091 * 79 = (9 * 7) * 100 + (10 * 16 – X1 – Z1 ) * 10 + (1 * 9) =X1 Y1 Z163639916088 71897189 3720)(19 * 19) * 10000 + (91 * 79 – X0 – Z0) * 100 + (62 * 60) = New Way1962 * 1960 =361X0361Z037207189Y038455203720)3108Observations13 Multiplications in the exampleTime Complexity = O( )Sourceshttp://en.wikipedia.org/wiki/Karatsuba_algorithmhttp://en.wikipedia.org/wiki/Divide_and_conquer_algorithmQuestions1. Who discovered the Karatsuba Multiplication Method?2. What is the significance of the numbers in the
View Full Document
Unlocking...