1 module mintegrated; 2 3 import std.array : array; 4 import std.conv : to; 5 import std.range : iota, zip; 6 import std.algorithm : all, map, max, reduce, filter; 7 import std.random : uniform; 8 import std.math : pow, round, sqrt; 9 10 import scid.types : Result; 11 import dstats.summary : meanStdev, MeanSD; 12 13 private struct Area(Real) 14 { 15 Real[] lower; 16 Real[] upper; 17 } 18 19 private Real volume(Real)( in Area!Real area ) 20 { 21 /+ 22 D way: fails to compile, so use for loop 23 return zip(area.lower, area.upper) 24 .map((t) => t[1] - t[0]) 25 .reduce!((a,b) => a*b ); 26 +/ 27 Real s = 1; 28 foreach( t; zip(area.lower, area.upper) ) 29 s *= t[1] - t[0]; 30 return s; 31 } 32 33 private size_t dimension(Real)( in Area!Real area ) 34 { 35 return area.lower.length; 36 } 37 38 unittest 39 { 40 assert( volume( Area!double([-1.0,-2.0],[2.0,0.0]) ) == 3.0*2.0 ); 41 } 42 43 private Area!Real[] splitArea(Real)( in Area!Real area, size_t dimension ) 44 { 45 assert( dimension < area.lower.length ); 46 auto div = (area.upper[dimension]-area.lower[dimension]) 47 //*0.5 48 *uniform(0.4,0.6) 49 + area.lower[dimension]; 50 auto newLower = area.lower.dup; 51 newLower[dimension] = div; 52 auto newUpper = area.upper.dup; 53 newUpper[dimension] = div; 54 return [ Area!Real( area.lower.dup, newUpper ), 55 Area!Real( newLower, area.upper.dup ) ]; 56 } 57 58 unittest 59 { 60 auto a = Area!double([-1.0,-2.0],[2.0,0.0]); 61 assert( splitArea(a,0)[0].volume < a.volume ); 62 assert( splitArea(a,1)[0].volume < a.volume ); 63 assert( splitArea(a,0)[1].volume < a.volume ); 64 assert( splitArea(a,1)[1].volume < a.volume ); 65 66 auto splitted = splitArea(a,0); 67 assert( a.volume == splitted[0].volume + splitted[1].volume ); 68 } 69 70 private bool withinArea(Real)( in Real[] point, in Area!Real area ) 71 { 72 return zip(point, area.lower, area.upper).all!( 73 (t) => t[0] >= t[1] && t[0] <= t[2] ); 74 } 75 76 unittest 77 { 78 auto a = Area!double([-1.0,-2.0],[2.0,0.0]); 79 assert( [0.0,0.0].withinArea( a ) ); 80 assert( ![-2.0,0.0].withinArea( a ) ); 81 assert( ![3.0,0.0].withinArea( a ) ); 82 assert( ![0.0,-2.1].withinArea( a ) ); 83 assert( ![0.0,0.1].withinArea( a ) ); 84 } 85 86 /// Perform standard Monte Carlo integration 87 private MeanSD monteCarlo(Func, Real)( scope Func f, in Area!Real area, 88 in size_t npoints ) 89 { 90 auto bounds = area.lower.zip(area.upper); 91 92 MeanSD msd; 93 foreach( i; 0..npoints ) 94 { 95 msd.put( f( 96 bounds 97 .map!( (t) { 98 return uniform!"[]"( t[0], t[1] ).to!Real; 99 } 100 ).array ) ); 101 } 102 return msd; 103 } 104 105 private Result!Real meanAndVariance(Real, MSD : MeanSD)( in MSD msd, in Area!Real area ) 106 { 107 auto v = area.volume; 108 return Result!Real( v*msd.mean().to!Real, 109 pow(v,2)*msd.mse().to!Real ); 110 } 111 112 private Result!Real meanAndVariance(Real, Range)( in Range values, in Area!Real area ) 113 { 114 auto msd = meanStdev( values ); 115 return msd.meanAndVariance!Real( area ); 116 } 117 118 unittest 119 { 120 auto a = Area!double([-1.0,-2.0],[0.0,-1.0]); 121 auto vs = [1.0,2.0,1.5]; 122 auto res = vs.meanAndVariance( a ); 123 assert( res.value == 1.5 ); 124 assert( res.error == 0.5/3 ); 125 126 a = Area!double([-1.0,-2.0],[1.0,-1.0]); 127 res = vs.meanAndVariance( a ); 128 assert( res.value == 2*1.5 ); 129 assert( res.error == 4*0.5/3 ); 130 } 131 132 /// 133 Result!Real integrate(Func, Real)(scope Func f, Real[] a, Real[] b, 134 Real epsRel = cast(Real) 1e-6, Real epsAbs = cast(Real) 0) 135 { 136 auto area = Area!Real( a, b ); 137 auto result = miser(f, area, epsRel, epsAbs, 200000*a.length); 138 return Result!Real( result.value, 139 result.error ); 140 } 141 142 /// The returned error is the expected variance in the result 143 Result!Real miser(Func, Real)(scope Func f, in Area!Real area, 144 Real epsRel = cast(Real) 1e-6, Real epsAbs = cast(Real) 0, 145 size_t npoints = 1000 ) 146 { 147 import std.algorithm : cache; 148 assert( volume(area) > 0, "Size of area is 0" ); 149 auto minPoints = 15*area.dimension; 150 auto dim = max( 0.1*npoints, minPoints ).to!int; 151 auto leftOverPoints = npoints - dim; 152 153 if ( npoints < minPoints ) 154 //|| result.error < epsAbs 155 return monteCarlo(f, area, dim).meanAndVariance(area); 156 157 // Try different subareas 158 Area!Real[] bestAreas; 159 auto bestEst = Real.max; 160 Result!Real[] bestResults; 161 foreach( j; 0..area.dimension ) 162 { 163 auto subAreas = area.splitArea( j ); 164 assert( volume(subAreas[0]) > 0, "Cannot divide the area further" ); 165 166 MeanSD[] msds = new MeanSD[2]; 167 msds[0] = monteCarlo(f, subAreas[0], dim/2); 168 msds[1] = monteCarlo(f, subAreas[1], dim/2); 169 170 auto results = msds.zip(subAreas).map!((msd) => 171 meanAndVariance(msd[0], msd[1]) ).cache; 172 Result!Real[] cacheResults; 173 // Optimize this by first only looking at first. Only if that 174 // is smaller than bestEstimate would we need to calculate second 175 Real runningError = 0; 176 while( !results.empty && runningError < bestEst ) 177 { 178 runningError += results.front.error; 179 cacheResults ~= results.front; 180 results.popFront; 181 } 182 183 if( results.empty && runningError < bestEst ) 184 { 185 bestEst = runningError; 186 bestResults = cacheResults; 187 bestAreas = subAreas; 188 } 189 } 190 assert( bestAreas.length == 2 ); 191 assert( bestResults.length == 2 ); 192 193 auto sdA = sqrt(bestResults[0].error); 194 auto sdB = sqrt(bestResults[1].error); 195 auto sumSd = sdA + sdB; 196 //assert( sumSd > 0, "Sum Errors to small" ); 197 if (sumSd == 0) 198 { 199 auto result = Result!Real( bestResults[0].value+bestResults[1].value, 200 sqrt( bestResults[0].error + bestResults[1].error ) ); 201 202 return result; 203 } 204 205 auto npntsl = round(leftOverPoints*sdA/sumSd).to!int; 206 207 auto rl = miser( f, bestAreas[0], 208 epsRel, epsAbs, npntsl ); 209 auto ru = miser( f, bestAreas[1], 210 epsRel, epsAbs, leftOverPoints-npntsl ); 211 212 auto result = Result!Real( rl.value+ru.value, 213 rl.error+ru.error ); 214 215 return result; 216 } 217 218 /// 219 unittest 220 { 221 import std.math : PI, pow; 222 import std.stdio : writeln; 223 auto func = function( double[] xs ) 224 { 225 if (pow(xs[0],2)+pow(xs[1],2)<= 1.0) 226 return 1.0; 227 return 0.0; 228 }; 229 230 auto result = integrate( func, [-1.0,-1], [1.0,1.0], 1e-5, 0 ); 231 result.writeln; 232 assert( result.value <= PI + 3*sqrt(result.error) ); 233 assert( result.value >= PI - 3*sqrt(result.error) ); 234 } 235 236 // Test precision 237 unittest 238 { 239 import std.math : PI, pow; 240 import std.stdio : writeln; 241 auto func = function( double[] xs ) 242 { 243 if (pow(xs[0],2)+pow(xs[1],2)<= 1.0) 244 return 1.0; 245 return 0.0; 246 }; 247 248 MeanSD msd; 249 250 foreach( i; 0..25 ) 251 { 252 auto result = integrate( func, [-1.0,-1], [1.0,1.0], 1e-5, 0 ); 253 msd.put(result); 254 } 255 "Mean and variance".writeln; 256 msd.mean.writeln; 257 msd.var.writeln; 258 assert( msd.var < 1e-4 ); 259 } 260 /// 261 unittest 262 { 263 import std.stdio : writeln; 264 auto func = function(double[] xs ) 265 { 266 return xs[0]*xs[1]; 267 }; 268 auto result = integrate( func, [0.0,0], [1.0,1] ); 269 result.writeln; 270 assert( result.value <= 0.25 + 3*sqrt(result.error) ); 271 assert( result.value >= 0.25 - 3*sqrt(result.error) ); 272 } 273 274 /// 275 unittest 276 { 277 import std.math : PI, cos; 278 import std.stdio : writeln; 279 auto func = function(real[] xs ) 280 { 281 return 1.0/(pow(PI,3)*(1-cos(xs[0])*cos(xs[1])*cos(xs[2]))); 282 }; 283 auto result = integrate( func, [0,0,0], [PI,PI,PI] ); 284 result.writeln; 285 assert( result.value <= 1.393204 + 3*sqrt(result.error) ); 286 assert( result.value >= 1.393204 - 3*sqrt(result.error) ); 287 }