This is for Project Euler problem #371:
My solution was to generate a huge random pool of numbers between 0 and 999 inclusive, repeatedly ask the question 'How many numbers do I need to pull into a holding area before I get a pair that adds to 1000?', and then average the resulting list(to get the expected number of plates).
The problem is that hand-optimizing my program lets me crunch about 10 million samples of the second step(so a total pool of 400 million random numbers are used), but I'm not even getting 2 digits of accuracy behind the decimal(I'm using exact integer arithmetic):
There could be an error in my program otherwise, but I'm not asking you to debug my program. I'm sure there's a better way to do this in principle than brute-forcing it with the Law of Large Numbers, so I wanted to ask:
Should I be expecting more than 2 digits of precision with my approach?
If someone handed you a huge number of random samples, how would you efficiently compute their expected value to a high precision?