6 006 Introduction to Algorithms Lecture 22 Prof Patrick Jaillet Outline Numerics algorithms for operations on large numbers high precision cryptography simulations etc Today we will see irrationals large number operations multiplication division 4 14159265358979323846264338327950288419 7169399375105820974944592307816406286208 9986280348253421170679821480865132823066 4709384460955058223172535940812848111745 0284102701938521105559644622948954930381 9644288109756659334461284756482337867831 6527120190914564856692346034861045432664 8213393607260249141273724587006 2 4142135623730950488016887242096980785696718753769480731766797379907 324784621070388503875343276415727350138462309122970249248360558507372 126441214970999358314132226659275055927557999505011527820605714701095 599716059702745345968620147285174186408891986095523292304843087143214 508397626036279952514079896872533965463318088296406206152583523950547 45750287759961729835575220337531857011354374603 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 lattice 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 to lots of digits why geometry problem B 1 C D A 1000 000 000 000 BD 1 what is AD AD AC CD 500 000 000 000 500 000 000 000 2 1 Computing h Heron s method Iterative approach also called the Babylonian method can be seen to be equivalent to the Newton method more later y0 h x0 1 y1 x0 y0 2 x1 h y1 in general yi 1 xi yi 2 xi 1 h yi 1 c 10 70 AD Computing h 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 converges quickly 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 c 10 70 AD Computing h Newton s method Newton s method Iterative approach to solving f x 0 0 6 0 5 0 4 Iterative step f 0 3 0 2 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 1 0 0 1 xi xi 1 0 2 for computing h f x x2 h xi 1 xi xi2 h 2xi xi h xi 2 Computing h Newton s method xi 1 xi xi2 h 2xi xi h xi 2 convergence 0 1 2 3 4 5 1 000000000000000 1 500000000000000 1 416666666666670 1 414215686274510 1 414213562374690 1 414213562373090 Large number addition Given two positive n digit numbers x y with radix r e g r 2 r 10 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 Need to 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 Division 1 b Inversion given positive n digit number b radix r compute 1 b i e for some R rk compute R b Iterative algorithm start from some x0 keep computing xi 1 from xi hope prove this converges to the answer Division again 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 xi xi 1 0 2 here we have next slide f x 1 x b R xi 1 2xi xi2b R Division want to solve f x 1 x b R 0 we have f x 1 x2 iterative step xi 1 xi f xi f xi yields xi 1 xi xi2 1 xi b R i e xi 1 2xi xi2b R convergence Convergence of xi 1 2xi xi2b R Assume xi R b 1 ei ei error Assumptions ei is small Ignore the round off errors caused by the R operation How does each iteration affect ei xi 1 2xi xi2b R 2R b 1 ei R b 1 ei 2 b R R b 2 2ei 1 2ei ei2 R b 1 ei2 R b 1 ei 1 where ei 1 ei2 We have ei 1 ei 2 quadratic convergence
View Full Document
Unlocking...