4 ms·

In general, there shouldn't be a rule like 3n bits. For random functions, 1 in 8^n values should require more than 3n bits. Since n bit inputs give 2^n possible

In general, there shouldn't be a rule like 3n bits. For random functions, 1 in 8^n values should require more than 3n bits. Since n bit inputs give 2^n possible values, this implies that for bit length n, there is a 4^-n chance that any given function will require more than 3n bits.

bsder 5y ago
Except that this isn't the case. We know empirically because we have enumerated the single precision space completely. So, the problem isn't bounded by simple probabilities. There are other properties involved that cause it to diverge from the "naive" probabilistic estimates. What those properties are we don't know yet. The "rounding" problem is called the "Table Maker's Dilemma" and it descends into some pretty fundamental transcendental number theory. This is not an "easy" problem. Proof that PI was transcendental is relatively modern (1885).
- adgjlsfhk1 5y ago
  This doesn't contradict what I said. I said that the odds of a function needing more than 3n digits was 4^-n. For single precision, that means you would expect almost all functions to be OK with 3n bits (1 in 2^46 wouldn't be).
  - vyodaiken 5y ago
    if it was a randomly selected function, which it is not.
    - stephencanon 5y ago
      In practice the low-order bits of transcendental functions are pretty much indistinguishable from random for _most_ inputs. You do have to be very careful close to especially nice values though, because this falls apart catastrophically there (e.g. logarithms close to 1)--it should be pretty obvious from the Taylor expansions why this happens. The good news is that when this does happen, almost by construction you usually don't end up very close to an exact halfway point for rounding.
      - klyrs 5y ago
        > In practice the low-order bits of transcendental functions are pretty much indistinguishable from random for _most_ inputs. In my experience, low order bits of transcendental functions make terrible rng sources (even discounting their runtime). Your example of the logarithm is great -- for large inputs, you need large changes to flip even low order bits.
- tmyklebu 5y ago
  If you're just looking for hard-to-round inputs, you can also enumerate the double precision space completely with some cleverness and modest patience. Elkies [0] computes a piecewise linear approximation to his (number-theoretic) function of interest and does a lattice reduction on each piece to filter out the vast majority of the space. The same approach, works almost everywhere on all of the transcendental functions I've tried, and I believe the CRlibm group uses it. [0] https://arxiv.org/pdf/math/0005139.pdf https://arxiv.org/pdf/math/0005139.pdf
  - bsder 5y ago
    Oooh, that's an interesting take.

bsder 5y ago

Except that this isn't the case. We know empirically because we have enumerated the single precision space completely. So, the problem isn't bounded by simple probabilities. There are other properties involved that cause it to diverge from the "naive" probabilistic estimates. What those properties are we don't know yet. The "rounding" problem is called the "Table Maker's Dilemma" and it descends into some pretty fundamental transcendental number theory. This is not an "easy" problem. Proof that PI was transcendental is relatively modern (1885).

adgjlsfhk1 5y ago
This doesn't contradict what I said. I said that the odds of a function needing more than 3n digits was 4^-n. For single precision, that means you would expect almost all functions to be OK with 3n bits (1 in 2^46 wouldn't be).
- vyodaiken 5y ago
  if it was a randomly selected function, which it is not.
  - stephencanon 5y ago
    In practice the low-order bits of transcendental functions are pretty much indistinguishable from random for _most_ inputs. You do have to be very careful close to especially nice values though, because this falls apart catastrophically there (e.g. logarithms close to 1)--it should be pretty obvious from the Taylor expansions why this happens. The good news is that when this does happen, almost by construction you usually don't end up very close to an exact halfway point for rounding.
    - klyrs 5y ago
      > In practice the low-order bits of transcendental functions are pretty much indistinguishable from random for _most_ inputs. In my experience, low order bits of transcendental functions make terrible rng sources (even discounting their runtime). Your example of the logarithm is great -- for large inputs, you need large changes to flip even low order bits.
tmyklebu 5y ago
If you're just looking for hard-to-round inputs, you can also enumerate the double precision space completely with some cleverness and modest patience. Elkies [0] computes a piecewise linear approximation to his (number-theoretic) function of interest and does a lattice reduction on each piece to filter out the vast majority of the space. The same approach, works almost everywhere on all of the transcendental functions I've tried, and I believe the CRlibm group uses it. [0] https://arxiv.org/pdf/math/0005139.pdf https://arxiv.org/pdf/math/0005139.pdf
- bsder 5y ago
  Oooh, that's an interesting take.