6 006 Introduction to Algorithms Lecture 22 Piotr Indyk Outline Numerics algorithms for operations on large numbers high precision cryptography simulations etc We will see irrationals large number operations multiplication division matrix multiplication 3 14159265358979323846264338327950288419 7169399375105820974944592307816406286208 9986280348253421170679821480865132823066 4709384460955058223172535940812848111745 0284102701938521105559644622948954930381 9644288109756659334461284756482337867831 6527120190914564856692346034861045432664 8213393607260249141273724587006 2 4142135623730950488016887242096980785696718753769 480731766797379907324784621070388503875343276415727 350138462309122970249248360558507372126441214970999 358314132226659275055927557999505011527820605714701 095599716059702745345968620147285174186408891986095 523292304843087143214508397626036279952514079896872 533965463318088296406206152583523950547457502877599 61729835575220337531857011354374603 Computing h to lots of digits why 1 2 1 1 414 213 562 373 095 048 801 688 724 209 698 078 569 671 875 376 948 073 176 679 Computing h to lots of digits why High precision may be needed in some applications Consider Dijkstra for paths between points on plane h a h i lengths have form i i i 2 2 2 where hi ai bi bi Is 1 40 60 12 17 56 1 40 60 15 07052201275 12 17 56 15 07052201430 Computing h Babylonian method Iterative approach Also called the Heron s method y0 h x0 1 y1 x0 y0 2 x1 h y1 In general yi 1 xi yi 2 xi 1 h yi 1 Since x0 y0 2x01 2 y01 2 x01 2 y01 2 2 0 we have x0 y0 2 x01 2 y01 2 h1 2 c 10 AD c 1700 BC Computing h Babylonian method y0 h x0 1 y1 x0 y0 2 x1 h y1 In general yi 1 xi yi 2 xi 1 h yi 1 Convergence Fast Example for h 2 x y 0 1 000000000000000 2 000000000000000 1 1 333333333333330 1 500000000000000 2 1 411764705882350 1 416666666666670 3 1 414211438474870 1 414215686274510 4 1 414213562371500 1 414213562374690 5 1 414213562373090 1 414213562373090 Computing h Babylonian method Formula yi 1 xi yi 2 xi 1 h yi 1 Need to be able to Add Divide or multiply compute the inverse Large number addition Given two positive n digit numbers x y with radix r e g r 2 r 10 r 60 Goal compute x y using only operations on single digits Algorithm keep adding digits from right to left keeping track of carryovers Time O n xn 1 xn 2 x1 x0 yn 1 yn 2 y1 y0 Large number multiplication Given two positive ndigit numbers x y with radix r Goal compute x y using only operations on single digits Ideas xn 1 xn 2 x1 x0 yn 1 yn 2 y1 y0 Divide and conquer attempt I Split each number into high xn 1 xn 2 x1 x0 and low parts each n 2 digits long x xHrn 2 xL yn 1 yn 2 y1 y0 y yHrn 2 yL We have x y xHrn 2 xL yHrn 2 yL xH yH rn xH yL xL yH rn 2 xL yL Algorithm for mult x y a mult xH yH b mult xH yL c mult xL yH d mult xL yL return add lshift a n lshift b n 2 lshift c n 2 d Attempt I analysis Algorithm a mult xH yH b mult xH yL c mult xL yH d mult xL yL return add lshift a n lshift b n 2 lshift c n 2 d Running time T n recurrence T n 4 T n 2 O n this solves to T n O n2 How to improve on this Attempt II Can we compute x y xH yH rn xH yL xL yH rn 2 xL yL using fewer than 4 recursive multiplications Here is how to do it Karatsuba 62 a xH yH d xL yL e xH xL yH yL a d xH yH xH yL xL yH xL yL a d xH yL xL yH x y a rn e rn 2 d This leads to T n 3 T n 2 O n which solves to T n O nlog 3 O n1 58496 Multiplication further results Toom Cook Split into 3 parts 5 multiplications O nlog3 5 O n1 46 Sch nhage and Strassen 71 Uses Fast Fourier Transform O n log n log log n Furer 07 O n log n 2 log n log n number of times we need to apply logarithm to n until we get a number 1 E g log 265536 1 log 65536 2 log 16 3 log 4 4 log 2 5 Division Newton s method Newton s method Iterative approach to solving f x 0 0 6 0 5 0 4 f 0 3 Iterative step find a line y f xi f xi x xi tangent to f x at xi set xi 1 to the solution of f xi f xi x xi 0 xi 1 xi f xi f xi 0 2 0 1 0 0 1 0 2 xi xi 1
View Full Document
Unlocking...