Expected value Il The two quantities are not equal, so the corollary must be false. But here is another false corollary, which we can actually prove"! False Corollary 4. IfEx(r/T)>l, then Ex (r)> Ex t Proof. We begin with the if-Part, multiply both sides by Ex (T), and then apply Theo- rem Ex(r/T)>1 Ex(R/T)·Ex(T)>Ex(T) Ex(r)>Ex(T) This "proof"is bogus! The first step is valid only if Ex(T)>0. More importantly, we cant apply Theorem 1 in the second step because R/T and T are not necessarily independent. Unfortunately, the fact that Corollary 4 is false does not mean it is never 3.3.1 A RISC Paradox The following data is taken from a paper by some famous professors. They wanted to show that programs on a RiSC processor are generally shorter than programs on a CISC processor. For this purpose, they made a table of program lengths for some benchmark problems, which looked like this Benchmark RISC CISC CISC/ RISC E-string search 150 120 0.8 F-bit test 120180 1.5 Ackerman 150300 Rec 2-sort 28001400 0.5 1.2 Each row contains the data for one benchmark. The numbers in the first two columns are program lengths for each type of processor. The third column contains the ratio of the CISC program length to the RISC program length. Averaging this ratio over all bench- marks gives the value 1. 2 in the lower right. The authors conclude that"CISC programs are 20% longer on averag But there's a pretty serious problem here. Suppose we redo the final column, taking the inverse ratio, risc / CISC instead of CiSc/ risc Benchmark RISC CISC RISC/CISC E-str ng F-bit test 120180 0.67 Ackerman 150300 0.5 Rec 2-sort 28001400 AExpected Value II 7 The two quantities are not equal, so the corollary must be false. But here is another false corollary, which we can actually “prove”! False Corollary 4. If Ex (R/T) > 1, then Ex (R) > Ex (T). “Proof”. We begin with the ifpart, multiply both sides by Ex (T), and then apply Theorem 1: Ex (R/T) > 1 Ex (R/T) · Ex (T) > Ex (T) Ex (R) > Ex (T) This “proof” is bogus! The first step is valid only if Ex (T) > 0. More importantly, we can’t apply Theorem 1 in the second step because R/T and T are not necessarily independent. Unfortunately, the fact that Corollary 4 is false does not mean it is never used! 3.3.1 A RISC Paradox The following data is taken from a paper by some famous professors. They wanted to show that programs on a RISC processor are generally shorter than programs on a CISC processor. For this purpose, they made a table of program lengths for some benchmark problems, which looked like this: Benchmark RISC CISC CISC / RISC Estring search 150 120 0.8 Fbit test 120 180 1.5 Ackerman 150 300 2.0 Rec 2sort 2800 1400 0.5 Average 1.2 Each row contains the data for one benchmark. The numbers in the first two columns are program lengths for each type of processor. The third column contains the ratio of the CISC program length to the RISC program length. Averaging this ratio over all benchmarks gives the value 1.2 in the lower right. The authors conclude that “CISC programs are 20% longer on average”. But there’s a pretty serious problem here. Suppose we redo the final column, taking the inverse ratio, RISC / CISC instead of CISC / RISC. Benchmark RISC CISC RISC / CISC Estring search 150 120 1.25 Fbit test 120 180 0.67 Ackerman 150 300 0.5 Rec 2sort 2800 1400 2.0 Average 1.1