4 ms·
The approximation holds only for b << 10^k. Then you don't get to take O(10^k) steps to work you way around the unit interval, do you? After the approximation b
by markisus 7y ago
The approximation holds only for b << 10^k. Then you don't get to take O(10^k) steps to work you way around the unit interval, do you? After the approximation breaks down, you don't know that the spacing is approximately uniform anymore.
- SamReidHughes 7y agoYou only need sqrt(2 log(10) 10^k) steps. The spacing is not uniform, it's just bounded by O(1/10^(k/2)). The spacing is, at its greatest, about 1/sqrt(2 log(10) 10^k).
- markisus 7y agoI'm not sure you only need that many steps. As you start out, each step gives you a lot of distance. But log gets flatter and flatter the more steps you take. If you knew the number of steps, I think you could only make a lower bound on spacing, not an upper bound. Since at worst all the steps could be clustered really close, except for the last one. But now I have to think more because it seems like it should actually help the argument that the spacing gets finer and finer as you step, because that is what we want anyway. And is the number of steps actually important to the proof?
- SamReidHughes 7y agoThe distance you cover with step b is about b/(log(10) 10^k). The exact distance is log10((10^k + b)/10^k). That's a funny way of saying fracPart(log10(10^k + b)). The number of steps tells you how big the last step is.
- markisus 7y agoOkay I think I buy it. Great proof, thanks!