真正的完全体倩女幽魂第一弓已经完_ 课件

MIT The Intel Pentium Division Flaw Alan Edelman Department of Mathematics Laboratory for Computer Science Massachusetts Institute of Technology MIT Not So Well Known The bug itself is (mathematically) neat! A Lesson (for me anyway) So much incomplete So much incomplete information is out rmation is out there. MIT Interesting Related Topics (but my topic is the bug) vRisk to Pentium owners vIntels chip replacement blunder vKahans SRT division tester vMoler, Coe, and Mathisen software workaround vOnly the lawyers get rich vThose ubiquitous Pentium jokes MIT Outline vNicelys Discovery vComputer Science Prerequisites vDivision (SRT=Sweeney,Robertson,Tocher) vPentium Lookup Table vDivision Example vSix Ones Result vInequality Analysis v“Send More Money” Puzzle vAlways nearly five good digits MIT Nicelys Twin Prime Bug Discovery vTwin primes: (5,7) (11,13) (17,19) (29,31) . vNicely was summing twin prime reciprocals: v S = 1/5 + 1/ 7 + 1/11 + 1/13 + 1/17 + 1/19 + . vS is finite. vNicely computed on many platforms. vNicely checked his work. MIT Computer Science Prerequisites vCarry Save Addition. vOnes vs. Twos Complement. MIT Carry-save Addition 1212 21 21 + 19+ 19 52 52 MIT Carry-save Addition 12 21 + 19 52 20 Answer (mod 32) MIT Carry-save Addition 0110001100 1010110101 1001110011 1010010100 + + 12 21 + 19 52 20 Answer (mod 32) MIT Carry-save Addition 0110001100 1010110101 1001110011 1010010100 0110001100 1010110101 1 1 0 0 Sum Bits (s) Carry Bits (c) + + + + 12 21 + 19 52 20 Answer (mod 32) MIT Carry-save Addition 0110001100 1010110101 1 1 0 0 s = xyz = x+y+z (mod 2) c = xy xz yz = (x+y+z | 2) 0110001100 1010110101 1001110011 1010010100 + + + + Sum Bits (s) Carry Bits (c) 12 21 + 19 52 20 Answer (mod 32) MIT Carry-save Addition 0110001100 1010110101 1001110011 1010010100 0110001100 1010110101 01 01 00 00 s = xyz = x+y+z (mod 2) c = xy xz yz = (x+y+z | 2) + + + + Sum Bits (s) Carry Bits (c) 12 21 + 19 52 20 Answer (mod 32) MIT Carry-save Addition 0110001100 1010110101 1001110011 1010010100 0110001100 1010110101 1100111001 0100001000 s = xyz = x+y+z (mod 2) c = xy xz yz = (x+y+z | 2) + + + + Sum Bits (s) Carry Bits (c) 12 21 + 19 52 20 Answer (mod 32) MIT Carry-save Addition 0110001100 1010110101 1001110011 1010010100 0110001100 1010110101 1100111001 0100001000 s = xyz = x+y+z (mod 2) c = xy xz yz = (x+y+z | 2) +10011+10011 + + + + Sum Bits (s) Carry Bits (c) 12 21 + 19 52 20 Answer (mod 32) MIT Carry-save Addition 0110001100 1010110101 1001110011 1010010100 0110001100 1010110101 1100111001 0100001000 s = xyz = x+y+z (mod 2) c = xy xz yz = (x+y+z | 2) +10011+10011 00010 00010 10010 10010 Sum Bits (s) Carry Bits (c) + + + + Sum Bits (s) Carry Bits (c) 12 21 + 19 52 20 Answer (mod 32) MIT Ones vs. Twos Complement Twos Complement 300011 200010 100001 000000 -111111 -211110 -311101 MIT Ones vs. Twos Complement Twos Complement Ones Complement 30001100011 20001000010 10000100001 00000000000 -11111111110 -21111011101 -31110111100 MIT Ones vs. Twos Complement Twos Complement Ones Complement 30001100011 20001000010 10000100001 00000000000 -11111111110 -21111011101 -31110111100 MIT vDivision Algorithms: MIT Long Division Example 1.42857 1.42857 7 71010.00000 .00000 7 7 3030 28 28 2020 14 14 6060 MIT Long Division Example q0 q1q2q3q4q5 1.42857 710.00000 7 30 28 20 14 60 Chosen to satisfy usual inequalities MIT p = 10, d = 7p = 10, d = 7 10d = 7010d = 70 p p k+1k+1 = 10(p = 10(p k k q q k k d d) ) 0 p0 pk+1 k+1 70 70 Long Division Example q0 q1q2q3q4q5 1.42857 710.00000 p0 7 30 p1 28 20 p2 14 60 p3 MIT Long Division Radix 10 Compute Compute q = p / dq = p / d. . p p0 0 := p := p for k=0,1,.for k=0,1,. Find the digit Find the digit q q k k 0, 1, 2, , 90, 1, 2, , 9 such thatsuch that p pk+1 k+1 := 10(p := 10(pk k - - q qk k d) d) satisfiessatisfies p pk k +1 +1 0, 10)d0, 10)d endend q = p / d = q q = p / d = q i i / 10 / 10 i i S S i=0 i=0 MIT SRT Division Radix 4 Such qk exists? Algorithm correct? Compute Compute q = p / dq = p / d. . p p0 0 := p := p for k=0,1,.for k=0,1,. Look up a digit Look up a digit q q k k -2,-1,0,1,2 -2,-1,0,1,2 such thatsuch that p pk+1 k+1 := 4(p := 4(pk k - - q qk k d) d) satisfiessatisfies|p|pk k +1 +1| (8/3)d | (8/3)d endend q = p / d = q q = p / d = q i i / 4 / 4 i i S S i=0 i=0 MIT Such q q k k exists? exists? Given Given 11p,d2. Compute q=p,d2. Compute q=p/dp/d. . p p0 0 := p := p for k=0,1,.for k=0,1,. Look up a digit Look up a digit q q k k -2,-1,0,1,2 -2,-1,0,1,2 such thatsuch that p pk+1 k+1 := 4(p := 4(pk k - - q qk k d) d) satisfies|psatisfies|pk k +1 +1| (8/3)d | (8/3)d endend q = q = p/dp/d = = q q i i / 4/ 4 i i S S i=0i=0 q qk k := 0:= 0 q qk k := 2 := 2 q qk k := +2 := +2 q qk k := +1:= +1 q qk k := 1 := 1 3 3 8 8 d d 8 8 3 3 d d 3 3 2 2 d d 2 2 3 3 d d MIT 4(p4(pk k - 0) - 0) Such q q k k exists? exists? Given Given 11p,d2. Compute q=p,d2. Compute q=p/dp/d. . p p0 0 := p := p for k=0,1,.for k=0,1,. Look up a digit Look up a digit q q k k -2,-1,0,1,2 -2,-1,0,1,2 such thatsuch that p pk+1 k+1 := 4(p := 4(pk k - - q qk k d) d) satisfies|psatisfies|pk k +1 +1| (8/3)d | (8/3)d endend q = q = p/dp/d = = q q i i / 4/ 4 i i S S i=0i=0 q qk k := 0 := 0 -2 / 3d pk 2 / 3d pk+1 := 4(pk - 0) 3 3 8 8 d d 8 8 3 3 d d 3 3 2 2 d d 2 2 3 3 d d MIT Such q q k k exists? exists? Given Given 11p,d2. Compute q=p,d2. Compute q=p/dp/d. . p p0 0 := p := p for k=0,1,.for k=0,1,. Look up a digit Look up a digit q q k k -2,-1,0,1,2 -2,-1,0,1,2 such thatsuch that p pk+1 k+1 := 4(p := 4(pk k - - q qk k d) d) satisfies|psatisfies|pk k +1 +1| (8/3)d | (8/3)d endend q = q = p/dp/d = = q q i i / 4/ 4 i i S S i=0i=0 4 / 3d pk 8 / 3d pk+1 := 4(pk - 2d) q qk k := +2 := +2 3 3 4 4 d d3 3 8 8 d d 8 8 3 3 d d MIT Such q q k k exists? exists? Given Given 11p,d2. Compute q=p,d2. Compute q=p/dp/d. . p0 := p for k=0,1,.,. Look up a digit Look up a digit q q k k -2,-1,0,1,2 -2,-1,0,1,2 such thatsuch that p pk+1 k+1 := 4(p := 4(pk k - - q qk k d) d) satisfies|psatisfies|pk k +1 +1| (8/3)d | (8/3)d endend q = q = p/dp/d = = q q i i / 4/ 4 i i S S i=0i=0 4/3 pk 8/3 pk+1 := 4(pk - 2d) q qk k := +2 := +2 p pk k - 2d- 2d 3 3 8 8 d d 8 8 3 3 d d 3 3 2 2 d d 2 2 3 3 d d MIT 4(p4(pk k - 2d) - 2d) Such q q k k exists? exists? Given Given 11p,d2. Compute q=p,d2. Compute q=p/dp/d. . p p0 0 := p := p for k=0,1,.for k=0,1,. Look up a digit Look up a digit q q k k -2,-1,0,1,2 -2,-1,0,1,2 such thatsuch that p pk+1 k+1 := 4(p := 4(pk k - - q qk k d) d) satisfies|psatisfies|pk k +1 +1| (8/3)d | (8/3)d endend q = q = p/dp/d = = q q i i / 4/ 4 i i S S i=0i=0 q qk k := +2 := +2 4 / 3d pk 8 / 3d pk+1 := 4(pk - 2d) p pk k - 2d- 2d 3 3 8 8 d d 8 8 3 3 d d 3 3 2 2 d d 2 2 3 3 d d MIT A q q k k For Every Point For Every Point q qk k := 0:= 0 q qk k := 2 := 2 q qk k := +2 := +2 q qk k := +1:= +1 q qk k := 1 := 1 3 3 8 8 d d 8 8 3 3 d d 3 3 2 2 d d 2 2 3 3 d d MIT Algorithm Correct? Claim:Claim: p qp q 1 1 q qk-1 k-1 p p k k d 4 4d 4 4k-1 k-1 d d Proof by Induction:Proof by Induction: p p k k+1 +1 = 4(p = 4(p k k - - q q k k d d) ) p p k k q q k k p p k+1k+1 d d 4 4 k k d d = q = q 0 0 + + . . . + + + + . . . + + 4 4-k -k 4 4-k -k = + 4 = + 4-(k+1) -(k+1) MIT Algorithm Correct? Claim:Claim: p qp q 1 1 q qk-1 k-1 q qk k p p k+1k+1 d 4 4d 4 4k-1 k-1 4 4k k d d Proof by Induction:Proof by Induction: p p k k+1 +1 = 4(p = 4(p k k - - q q k k d d) ) p p k k q q k k p p k+1k+1 d d 4 4 k k d d = q = q 0 0 + + . . . + + + + . . . + + + 4 + 4-(k+1) -(k+1) 4 4-k -k = + 4 = + 4-(k+1) -(k+1) MIT Algorithm Correct? Claim:Claim: p qp q 1 1 q qk-1 k-1 q qk k p p k+1k+1 d 4 4d 4 4k-1 k-1 4 4k k d d Proof by Induction:Proof by Induction: p p k k+1 +1 = 4(p = 4(p k k - - q q k k d d) ) p p k k q q k k p p k+1k+1 d d 4 4 k k d d Letting Letting k k proves proves p qp q 1 1 q q 2 2 d 4 4d 4 4 2 2 = q = q 0 0 + + . . . + + + 4 + + . . . + + + 4-(k+1) -(k+1) 4 4-k -k = + 4 = + 4-(k+1) -(k+1) = q = q 0 0 + + + . . . + + + . . . MIT Pentium Lookup Table (P-d plot) Divisor Shifted Partial Remainder 1.0000 1.0001 1.0010 1.0011 1.0100 1.0101 1.0110 1.0111 1.1000 1.1001 1.1010 1.1011 1.1100 1.1101 1.1110 1.1111 1/16 1/8 Blue Green q := 2 q := 1 q := 0 q := -1 q:= -2 MIT Pentium Lookup Table (P-d plot) Shifted Partial Remainder Divisor 1.0000 1.0001 1.0010 1.0011 1.0100 1.0101 1.0110 1.0111 1.1000 1.1001 1.1010 1.1011 1.1100 1.1101 1.1110 1.1111 Blue Green q := 2 q := 1 q := 0 q := -1 q:= -2 1/16 1/8 MIT A Close-up Look at One Column (D=1.0001) 2 2 1 1 0 0 -1-1 -2-2 2.8752.875 1.5 1.5 1.375 1.375 0.375 0.375 0.25 0.25 -0.5-0.5 -0.625-0.625 -1.625-1.625 -1.75-1.75 -3-3 P MIT 2 2 1 1 0 0 -1-1 -2-2 2.8752.875 1.5 1.5 1.375 1.375 0.375 0.375 0.25 0.25 -0.5-0.5 -0.625-0.625 -1.625-1.625 -1.75-1.75 -3-3 0 0 0 0 2 2 2 2 2 2 2 2 2 2 P 3.375 Off the Chart 3.25 Off the Chart 3.125 Off the Chart 3 Off the Chart 2.875 Buggy Entry 2.75 Foothold A Close-up Look at One Column (D=1.0001) MIT Pentium Division Example: 1.875/1.000 pk+1 := 4(pk qkd) 0001.111 00000000000 0001.111 00000000000 S S 0000.000 00000000000 0000.000 00000000000 C C 1.875 = 1.875 = q qk k :=0:=0 q qk k :=2:=2 q qk k :=+2:=+2 q qk k :=+1:=+1 q qk k :=1:=1 MIT pk+1 := 4(pk qkd) 0001.111 00000000000 0001.111 00000000000 S S 0000.000 00000000000 0000.000 00000000000 C C 1101.111 111111111111101.111 11111111111 1100.000 11111111111 1100.000 11111111111 S S 0011.110 00000000001 0011.110 00000000001 C C q qk k :=0:=0 q qk k :=2:=2 q qk k :=+2:=+2 q qk k :=+1:=+1 q qk k :=1:=1 2 2 1 =1 = -0.125 = -0.125 = 1.875 = 1.875 = Pentium Division Example: 1.875/1.000 MIT -0.125-0.125 4 = 4 = -0.5 = -0.5 = pk+1 := 4(pk qkd) 0001.111 00000000000 0001.111 00000000000 S S 0000.000 00000000000 0000.000 00000000000 C C 1101.111 111111111111101.111 11111111111 0000.011 1111111110000.011 11111111100 00 S S 1111.000 0000000011111.000 00000000100 00 C C q qk k :=0:=0 q qk k :=2:=2 q qk k :=+2:=+2 q qk k :=+1:=+1 q qk k :=1:=1 2 2 1 =1 = Pentium Division Example: 1.875/1.000 1.875 = 1.875 = MIT pk+1 := 4(pk qkd) 0001.111 00000000000 0001.111 00000000000 S S 0000.000 00000000000 0000.000 00000000000 C C 1101.111 111111111111101.111 11111111111 0000.011 11111111100 0000.011 11111111100 S S 1111.000 00000000100 1111.000 00000000100 C C 0001.000 000000000000001.000 00000000000 1001.111 11111100000 1001.111 11111100000 S S 1000.000 00000100000 1000.000 00000100000 C C q qk k :=0:=0 q qk k :=2:=2 q qk k :=+2:=+2 q qk k :=+1:=+1 q qk k :=1:=1 22 1 =1 = 1 1 1 =1 = 1.875 = 1.875 = Pentium Division Example: 1.875/1.000 MIT 2/1 + 1/4 + 2/16 + 0/64 = 1.875/1.000 0001.111 00000000000 0001.111 00000000000 S S 0000.000 00000000000 0000.000 00000000000 C C 1101.111 111111111111101.111 11111111111 0000.011 11111111100 0000.011 11111111100 S S 1111.000 00000000100 1111.000 00000000100 C C 0001.000 000000000000001.000 00000000000 1001.111 11111100000 1001.111 11111100000 S S 1000.000 00000100000 1000.000 00000100000 C C 1101.111 111111111111101.111 11111111111 0000.000 00011111100 0000.000 00011111100 S S 1111.111 11100000100 1111.111 11100000100 C C 0000.000 000000000000000.000 00000000000 1111.111 11111100000 1111.111 11111100000 S S 0000.000 00000100000 0000.000 00000100000 C C q qk k :=0:=0 q qk k :=2:=2 q qk k :=+2:=+2 q qk k :=+1:=+1 q qk k :=1:=1 22 1 =1 = 1 1 1 =1 = 22 1 =1 = 00 1 =1 = 1.875 = 1.875 = Pentium Division Example: 1.875/1.000 MIT Inequality AnalysisInequality Analysis Pk pk Pk + 1/4 D d D+ D + 1/16 Pk+1 = 4(Pk qkD+) + Rk R Rk k R R k k MaxMax 3/4 if 3/4 if q q k k = 2 = 2 3/4 if 3/4 if q q k k = 1 = 1 3/4 if 3/4 if q q k k = 0 = 0 1 if 1 if q q k k = 1 = 1 5/4 if 5/4 if q q k k = 2 = 2 MIT Reaching the Flaw is Not Easy! 2 2 qk Pk+1 2 Pbad - 1/8 1 Pbad - 1/8 0 Pbad - 1/8 1 Pbad - 1/8 Pk Pbad - 1/8 Pbad - 1/8 Pk = Pbad - 1/8 Pbad MIT foothold buggy entry MIT “Send More Money” Puzzle SEND +MORE MONEY 32 Massachusetts Institue of Technology 77 Massachusetts Ave. Cambridge, MA 02139 intel 22 Mission College Blvd. Santa Clara, CA 95052 MIT The Path to Failure Bad Divisors: d = 1.d1d2d3d4111111d11 . . . . . . 1 1 1 1 1 1 1 1 1 1 . . . . . . 1 1 1 1 1 1 1 1 1 1 .d.d 2 2d d3 3d d4 41 1 1 1 1 1 1 1 1 1 . . 1 1 1 1 1 1 1 1 1 1 . .1 1 1 1 1 1 1 1 1 1 1 1 .d.d 2 2d d3