7.8 Adaptive and Recursive Monte Carlo Methods 323 di[1+1][j],x1[j][i+2],di[i+2][j]): for (j=1;j<=ndim;++){ Refine the grid.Consult references to understand xo=d[1][j]; the subtlety of this procedure.The refine- xn=d[2][j]; ment is damped,to avoid rapid,destabiliz- d[1][j]=(xo+xn)/2.0; ing changes,and also compressed in range dt[j]=d[1][j]; by the exponent ALPH. for (i=2;i<nd;i++){ rc=xo+xn: http://www.nr Permission is read able files xo=xn; xn=d[i+1][j]; d[i][j]=(rc+xn)/3.0 dt[j]+=d[i][j]; d[nd][j]=(xo+xn)/2.0: dt[j]+d[nd][j]; .com or call 1-800-872- (including this one) granted for 19881992 for (j=1;j<=ndim;j++) rc=0.0; for (i-1;i<=nd;i++){ from NUMERICAL RECIPES IN C: if (d[i][i]TINY)d[i][j]-TINY; r[i]=pow((1.0-d[i][j]/dt[j])/ (log(dt[j])-log(a[i][j])),ALPH); 7423 (North America 电r:1s t by Cambridge University Press. THE rc +=r[i]; rebin(rc/xnd,nd,r,xin,xi[j]); only), 22 Programs void rebin(f1 oat rc,int nd,f1oatr▣，f1 oat xin☐，float xi[]) to dir Utility routine used by vegas,to rebin a vector of densities xi into new bins defined by a vector r. rectcustsen int i,k=0; f1 oat dr=0.0,xm=0.0,xo=0.0 for (i=1;i<nd;i++){ ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) while (rc dr) dr+=r[++k]; v@cambridge.org 1988-1992 by Numerical Recipes 1f(k>1)xo=x1[k-1]; Numerical Recipes books or xn=xi[k]; dr -rc; xin[i]=xn-(xn-xo)*dr/r[k]; y Software. for (i=1;i<nd;i++)xi[i]=xin[i]; xi[nd]=1.0; (outside North America) ying of machine Recursive Stratified Sampling The problem with stratified sampling,we have seen,is that it may not avoid the K explosion inherent in the obvious,Cartesian,tessellation of a d-dimensional volume.A technique called recursive stratified sampling [3]attempts to do this by successive bisections of a volume,not along all d dimensions,but rather along only one dimension at a time7.8 Adaptive and Recursive Monte Carlo Methods 323 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). di[i+1][j],xi[j][i+2],di[i+2][j]); } } } } for (j=1;j<=ndim;j++) { Refine the grid. Consult references to understand the subtlety of this procedure. The refine￾ment is damped, to avoid rapid, destabiliz￾ing changes, and also compressed in range by the exponent ALPH. xo=d[1][j]; xn=d[2][j]; d[1][j]=(xo+xn)/2.0; dt[j]=d[1][j]; for (i=2;i<nd;i++) { rc=xo+xn; xo=xn; xn=d[i+1][j]; d[i][j] = (rc+xn)/3.0; dt[j] += d[i][j]; } d[nd][j]=(xo+xn)/2.0; dt[j] += d[nd][j]; } for (j=1;j<=ndim;j++) { rc=0.0; for (i=1;i<=nd;i++) { if (d[i][j] < TINY) d[i][j]=TINY; r[i]=pow((1.0-d[i][j]/dt[j])/ (log(dt[j])-log(d[i][j])),ALPH); rc += r[i]; } rebin(rc/xnd,nd,r,xin,xi[j]); } } } void rebin(float rc, int nd, float r[], float xin[], float xi[]) Utility routine used by vegas, to rebin a vector of densities xi into new bins defined by a vector r. { int i,k=0; float dr=0.0,xn=0.0,xo=0.0; for (i=1;i<nd;i++) { while (rc > dr) dr += r[++k]; if (k > 1) xo=xi[k-1]; xn=xi[k]; dr -= rc; xin[i]=xn-(xn-xo)*dr/r[k]; } for (i=1;i<nd;i++) xi[i]=xin[i]; xi[nd]=1.0; } Recursive Stratified Sampling The problem with stratified sampling, we have seen, is that it may not avoid the Kd explosion inherent in the obvious, Cartesian, tessellation of a d-dimensional volume. A technique called recursive stratified sampling [3] attempts to do this by successive bisections of a volume, not along all d dimensions, but rather along only one dimension at a time