14
\$\begingroup\$

An easy way to understand the unit n-dimensional hypercube is to consider the region of space in n dimensions that you can get if every coordinate component lies in [0, 1]. So for one dimension it's the line segment from 0 to 1, for two dimensions it's the square with corners (0, 0) and (1, 1), etc.

Write a program or function that given n returns the average Euclidean distance of two points uniformly random selected from the unit n-dimension hypercube. Your answer must be within 10-6 of the actual value. It's ok if your answer overflows your language's native floating point type for big n.

Randomly selecting a 'big' number of points and calculating the average does not guarantee such accuracy.

Examples:

1 → 0.3333333333...
2 → 0.5214054331...
3 → 0.6617071822...
4 → 0.7776656535...
5 → 0.8785309152...
6 → 0.9689420830...
7 → 1.0515838734...
8 → 1.1281653402...

Data acquired from MathWorld.

This is , lowest byte-count wins.

\$\endgroup\$
19
  • \$\begingroup\$ Reiterated winning criterion in an edit. \$\endgroup\$ Feb 1, 2017 at 20:54
  • \$\begingroup\$ Just to be clear: distance refers to the Euclidean distance, yes? \$\endgroup\$
    – Dennis
    Feb 1, 2017 at 20:56
  • 3
    \$\begingroup\$ @carusocomputing What's the point of the challenge if you want me to solve it for you? \$\endgroup\$
    – orlp
    Feb 1, 2017 at 21:39
  • 4
    \$\begingroup\$ @orlp registering my objection to a challenge that is a math puzzle until someone figures out the math, then it becomes a programming puzzle when everyone copies the formula in different languages. I need to ask a meta question about this. \$\endgroup\$
    – Sparr
    Feb 1, 2017 at 22:22
  • 1
    \$\begingroup\$ When you say 5 digits of accuracy, do you mean to within 1e-5, or would an estimate of 1.500000000000001 be wrong when the output should be 1.499999999999999? \$\endgroup\$
    – xnor
    Feb 1, 2017 at 22:49

1 Answer 1

6
\$\begingroup\$

Mathematica, 68 bytes

NIntegrate[(1-((E^-u^2+u*Erf@u√π-1)/u^2)^#)/u^2,{u,0,∞}]/√π&

Implementation of the formula using NIntegrate to approximate its value.

Image

\$\endgroup\$
4
  • \$\begingroup\$ Beat me by 58 seconds :( \$\endgroup\$ Feb 1, 2017 at 23:30
  • \$\begingroup\$ Where did you find the formula? \$\endgroup\$
    – feersum
    Feb 2, 2017 at 22:58
  • \$\begingroup\$ @feersum It's formula (8) from Hypercube Line Picking. (10) is a typo and shouldn't have the double integral or du. \$\endgroup\$
    – miles
    Feb 2, 2017 at 23:03
  • \$\begingroup\$ If you actually input this as text it parses u√π as one token, so you need a space between u and . \$\endgroup\$
    – feersum
    Feb 2, 2017 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.