// Radix exchange sort; in memory.
// sorts words from b to e inclussive.
#define C const
void rdx(int *b, int *e, unsigned int C bit){
  if(b<e && bit) {int *B = b; int *E = e;
    while(1) {
      while(!(*B & bit)) if(B<E) ++B; else {++E; goto f;}
      while(*E & bit)    if(B<E) --E; else {--B; goto f;}
      {int t = *E; *(E--) = *B; *(B++) = t;}
      if(E<=B) {if(E==B) {if(*E & bit) --B; else ++E;}
         else {--B; ++E;} break;}
    }
f:  rdx(b, B, bit>>1);
    rdx(E, e, bit>>1);
  }
}
#define R double
R sq(R x){return x*x;}
#define ss 10000000
#include <stdio.h>
#include <stdlib.h>
R sqrt(R);
static R v(int j){return j<2 ? j+1 : 3.1415926535897932*v(j-2)*2/j;}
static R fac(int m){return m == 0 ? 1 : m*fac(m-1);}
static R ttmno2(int m){return m < 2 ? (m ? 1/sqrt(2) : 1) : ttmno2(m-2)/2;}
static R pow(R x, int m){return m ? x*pow(x, m-1) : 1;}

int main(){R sc = 1/(R)0x7fffffff;
  int n=25; while(n--) {int in = 0, s = ss;
  R C th = 1+1/(R)n; R C r = sqrt(th/2);
  while (s--){int a[n+2];
  {int j = n; while(j--) a[j+1] = random();}
  rdx(a+1, a+n, 1<<30);
  a[0] = 0; a[n+1] = 0x7fffffff;
  if(1){int j=n+1; while(j--) if(a[j+1]<a[j]) {printf("zz %d\n", j); exit(0);}}
  {float y[n+1];
    float tr2(){R s=sq(1-y[0]); int j; for(j=1; j<n+1; ++j) s+=sq(y[j]);
       return s;}
    {int j=n+1; while(j--) y[j] = (a[j+1] - a[j])*sc;}
    if(tr2() < th) ++in;}}
if(0){printf("sample fraction in %dD-ball = %10.7f\n", n, (R)in/ss);
printf("inscribed ball radius = %10.7f\n", r);
{R V = 1, f = 1/(2*r); int j=n; while(j--) V *= f;
  printf("portion of simplex in ball of r=.5: %12.7e\n", V*in/ss);
  printf("density limit = %12.7e\n", (n+1)*V*in/ss);
  {R cs = ttmno2(n)*sqrt(n+1)/fac(n),
    an = sqrt((1 + (R)1/n)/2),
    cban = pow(r,n)*v(n),
    cbanis = (R)in/ss * cs,
    ann = cbanis/cban,
    alphann = v(n)*n*ann;
    printf("v(n)*n = cn = %10.5e\n", v(n)*n);
    printf("v(n) = %10.5e, ss = %d\n", v(n), ss);
    printf("cs = %10.5e\nan = %9.5f\ncban = %9.5e\n"
      "cbanis = %10.5e\nann = %10.5e\nalphann = %10.5e\n",
      cs, an, cban, cbanis, ann, alphann);}
    }} else
    printf("%d %d\n", n, in);}
return 0;}