4 ms·
>Why eight steps? Well, to differentiate between 256 equally likely possibilities requires eight bits. Each experiment, since it differentiates between two equa
by lucio 8y ago
>Why eight steps? Well, to differentiate between 256 equally likely possibilities requires eight bits. Each experiment, since it differentiates between two equally likely outcomes (pass and fail), provides one bit of information. Therefore, we need eight such experiments to give us the eight bits we need to determine the faulty optimization.
Is this explanation a little odd?
Each step in a binary search halves the amount of suspects, you need 8 steps because with 8 steps you go from 256 suspects to one.
I can't see it the way the article describes it.
It's just me? Anyone else found the article reasoning for 8 steps a little odd?
- winceschwab 8y agoYeah, I noticed that too. Treating a byte as eight tally marks misses the point about the combinatorialnature of place settings. It's not 100% wrong, because bit shifting and bit packing are real-world applications used in memory all the time. But these are not the only possible values: 00000001 00000010 00000100 00001000 00010000 00100000 01000000 10000000 It's not incorrect to make a decision to limit one's input to those values, but it is incorrect to presume that binary data can only be recorded that way. Treating those 8 place settings as eight lightbulb circuits that each need an individual test isn't the right mindset for someone performing compiler optimization.