3 ms·

The predicate given is monotonic in the range 0.,100.. using the floating point bit representation (with appropriate starting l, r as they have) gives (a) bes

The predicate given is monotonic in the range 0.,100.. using the floating point bit representation (with appropriate starting l, r as they have) gives (a) best possible convergence rate - one bit per iteration. Using floating point math would also have this converge rate, but the halting condition would be interesting. Do you use the smallest epsilon? Alternatively, do you check that the midpoint is one of l,r? Both approaches require you know a little something about floating point numbers, and I'd say it's mostly an esthetic choice, especially since the convergence rate is the same.

moonchild 4y ago
> the halting condition would be interesting For l,r known to be positive: l*(1+(2^-52)) < r. Substitute 2^-23 for single-prec floats. > Using floating point math would also have this converge rate As I said, it does not; using float math has a less predictable convergence rate. With float math, you'd halve the magnitude of the search space every iteration, whereas with integer math, you'd halve the number of floating-point numbers contained in the range.
- henrydark 4y ago
  Both methods give you a bit of information per iteration. The number of distinct floating point numbers between l,r is the same as the number of integers in the reinterpretation of l,r as integers. (assuming starting l,r were appropriate)
  - moonchild 4y ago
    Suppose l=1, r=3. So m=(1+3)/2=2. There are twice as many floating-point numbers between 1 and 2 as between 2 and 3. So if you refine from [1 3] to [1 2], you've only managed to prune 1/3 of your search space, not 1/2. (Also: integer halving breaks when l and r have opposite signs.) Perhaps this will make it clearer: suppose we have l=0 and r=1, and the number we're searching for is the smallest float, 2^-1074. If we use integer halving, we get one bit per iterations; floats have 64 bits, so we should require no more than 64 iterations. But if we use floating-point halving, obviously it will take 1074 iterations to get from [0 1] to [0 2^-1074].
    - henrydark 4y ago
      Oh yeah, nice. Thanks, the example did make it clear.

moonchild 4y ago

> the halting condition would be interesting For l,r known to be positive: l*(1+(2^-52)) < r. Substitute 2^-23 for single-prec floats. > Using floating point math would also have this converge rate As I said, it does not; using float math has a less predictable convergence rate. With float math, you'd halve the magnitude of the search space every iteration, whereas with integer math, you'd halve the number of floating-point numbers contained in the range.

henrydark 4y ago
Both methods give you a bit of information per iteration. The number of distinct floating point numbers between l,r is the same as the number of integers in the reinterpretation of l,r as integers. (assuming starting l,r were appropriate)
- moonchild 4y ago
  Suppose l=1, r=3. So m=(1+3)/2=2. There are twice as many floating-point numbers between 1 and 2 as between 2 and 3. So if you refine from [1 3] to [1 2], you've only managed to prune 1/3 of your search space, not 1/2. (Also: integer halving breaks when l and r have opposite signs.) Perhaps this will make it clearer: suppose we have l=0 and r=1, and the number we're searching for is the smallest float, 2^-1074. If we use integer halving, we get one bit per iterations; floats have 64 bits, so we should require no more than 64 iterations. But if we use floating-point halving, obviously it will take 1074 iterations to get from [0 1] to [0 2^-1074].
  - henrydark 4y ago
    Oh yeah, nice. Thanks, the example did make it clear.