The tail of a dice sum

dynamic programming counting numerical precision estimation

In a board game n ordinary six-sided dice are thrown. A prize is given if the sum of points is at least s. The organiser wants to print the probability of winning on the box, for each variant of the rules. Some variants are almost hopeless: with a hundred dice and s = 600 all of them must come up six. Probabilities go below 10⁻²⁰⁰, so it was decided to print them as a decimal logarithm.

Input

The first line holds the number of variants q (1 ≤ q ≤ 10,000). Each of the next q lines holds integers n and s (1 ≤ n ≤ 300, n ≤ s ≤ 6n).

Output

For each variant, the decimal logarithm of the probability that the sum of n dice is at least s. The answer is accepted with an absolute or relative error of 10⁻⁶.

Examples

Example 1

Input

Output

-0.778151250
-1.556302501
-0.270554628
-77.815125038

Limits

Time · Python: 5000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 5 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

The first thought is to play out the throws many times and count the share of successes. How many throws are needed to see a hundred sixes in a row even once, if the probability of that is 6⁻¹⁰⁰ ≈ 10⁻⁷⁸?

2Hint 2

The second thought is that the sum of many dice is almost normally distributed, and the tail can be taken from the normal law. This is true near the middle, but with what relative accuracy in the tail?

3The idea

Neither simulation nor the normal approximation will do here: the relative error of Monte Carlo for a probability p is about 1/√(np), and the normal approximation’s error in a distant tail is dozens of orders of magnitude. The number of outcomes can be computed exactly. Let ways[t] be the number of ways k dice give the sum t. Add one more die: a new sum t comes from an old t − 1, …, t − 6. This is dynamic programming over the number of dice, and the probability needed is the sum of the tail ways[s] + … + ways[6n] divided by 6ⁿ.

4Walkthrough

In Python the numbers of ways can be kept as integers: 6³⁰⁰ is a number of 234 digits, big-integer arithmetic copes, and the answer comes out without a single rounding error. The logarithm is taken of integers: math.log10(tail) - n * math.log10(6), since log10 works with integers of any length. A new layer is computed with a window of six: the window’s sum shifts by one cell by adding one number and subtracting another.

In Go probabilities in float64 are more convenient: 6⁻³⁰⁰ ≈ 10⁻²³⁴ still fits in a double. But there is a trap here. A sliding window in floating point, add one and subtract another, in a distant tail subtracts almost the same 0.1 from 0.1 and leaves garbage of order 10⁻¹⁷ instead of 10⁻²⁰⁰, or even a negative number, of which the logarithm gives NaN. So the six terms are added directly, and the tail is summed from large t to small ones: small numbers are added to small ones.

The solution builds the layers for all n up to the largest in the queries once and answers each query from the ready tails.

4+Solution

5Complexity

300 layers, each with up to 1800 sums of 6 terms: about three million operations. In Python with big integers this takes a fraction of a second. For thousands of dice the layer can be raised to a power by convolution with the fast Fourier transform.

6Common mistakes

Monte Carlo. A million throws of a hundred dice will never show the sum 600: the estimate is zero, and its logarithm minus infinity.
The normal law. For a hundred dice and s = 600 it gives 10⁻⁴⁸ instead of 10⁻⁷⁸, an error of 10³⁰ times. Even near the middle it does not have 10⁻⁶ accuracy.
A sliding window in float. Cancellation of close numbers, as in the solution: the tail gets zeros and negative probabilities.
6ⁿ in Go integers. Already 6²⁵ does not fit in 64 bits.

Algorithms behind it

NUM~ Algorithm The Monte Carlo method Estimating a number by a random experiment: an error of 1/√n in any dimension, an honest confidence interval. O(n) trials, error ~ σ/√n 2 problems DP Technique Dynamic programming Reduce a problem to subproblems, solve each once and keep the answers in a table. states × transitions 2 problems TEC Technique Prefix sums The sum of any segment in O(1) after one pass; the two-dimensional version gives the sum of any rectangle of a picture. O(n) to build, O(1) per query 2 problems