3 ms·

Fail is an understatement, the ratio between the two volumes is basically (n/2)!(4/pi)^(n/2). Which is also the expected number of tries you'll need. The time d

Fail is an understatement, the ratio between the two volumes is basically (n/2)!(4/pi)^(n/2). Which is also the expected number of tries you'll need. The time doesn't merely grow exponentially it grows faster than exponential. I don't actually know of any useful algorithms with worse asymptomatic behaviour.

zeroonetwothree 3y ago
I doubt that the number of dimensions is the parameter that grows. It’s going to be constant for 99.99% of cases.
ianferrel 3y ago
Sure, but for the most-used real-world geometry, n = 2 or 3. So how fast it grows really doesn't matter. Most maps are 2-dimensional and this is fine.
- ls612 3y ago
  Maybe n=4 if you have a timestamp as another dimension.
  - alanbernstein 3y ago
    Do your timestamps occupy a hypersphere?
    - ls612 3y ago
      A 1-dimensional hypersphere is a line segment so sure.
- throwaway81523 3y ago
  When I saw "n" in the title I assumed they wanted something that worked reasonably for large n. Rejection is no good because of the notorious "curse of dimensionality". So my idea was to choose a suitable distribution on the radius, then draw from it and choose the angles at random (not sure what those angles are called). You might have to delete the point at the center for that to work.
  - Certhas 3y ago
    The article explicitly discusses both. Versions for low dimensions that have favorable properties, and those for high dimensions. The method you propose is not used in high dimensions in practice as it would involve evaluating order n^2 trigonometric functions and is also far harder to implement than the methods discussed in the article.
fjkdlsjflkds 3y ago
> I don't actually know of any useful algorithms with worse asymptomatic behaviour. Note: "asymptomatic" does not mean the same as "asymptotic"
- bee_rider 3y ago
  Most of my code has bad asymptomatic bugs but they never show up in testing because the tests don’t have data sets big enough to show the symptoms!
bee_rider 3y ago
Quibble: I don’t think “fail” is an understatement, it is as strong a word as anything else for something that doesn’t work. Actually, it is an overstatement I think, or something orthogonal; the algorithm is still correct just wildly inefficient. Fail should be reserved for algorithms that produce the wrong result, not ones that produce the right result very slowly, however slowly.

zeroonetwothree 3y ago

I doubt that the number of dimensions is the parameter that grows. It’s going to be constant for 99.99% of cases.

ianferrel 3y ago

Sure, but for the most-used real-world geometry, n = 2 or 3. So how fast it grows really doesn't matter. Most maps are 2-dimensional and this is fine.

ls612 3y ago
Maybe n=4 if you have a timestamp as another dimension.
- alanbernstein 3y ago
  Do your timestamps occupy a hypersphere?
  - ls612 3y ago
    A 1-dimensional hypersphere is a line segment so sure.
throwaway81523 3y ago
When I saw "n" in the title I assumed they wanted something that worked reasonably for large n. Rejection is no good because of the notorious "curse of dimensionality". So my idea was to choose a suitable distribution on the radius, then draw from it and choose the angles at random (not sure what those angles are called). You might have to delete the point at the center for that to work.
- Certhas 3y ago
  The article explicitly discusses both. Versions for low dimensions that have favorable properties, and those for high dimensions. The method you propose is not used in high dimensions in practice as it would involve evaluating order n^2 trigonometric functions and is also far harder to implement than the methods discussed in the article.

fjkdlsjflkds 3y ago

> I don't actually know of any useful algorithms with worse asymptomatic behaviour. Note: "asymptomatic" does not mean the same as "asymptotic"

bee_rider 3y ago
Most of my code has bad asymptomatic bugs but they never show up in testing because the tests don’t have data sets big enough to show the symptoms!

bee_rider 3y ago

Quibble: I don’t think “fail” is an understatement, it is as strong a word as anything else for something that doesn’t work. Actually, it is an overstatement I think, or something orthogonal; the algorithm is still correct just wildly inefficient. Fail should be reserved for algorithms that produce the wrong result, not ones that produce the right result very slowly, however slowly.