HiveBrain v1.2.0
Get Started
← Back to all entries
debugMinor

Probability of overflow in a summation of fixed-size signed integers

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
overflowsizefixedprobabilitysummationsignedintegers

Problem

How can I estimate the probability that the sum $S_n$ of $n$ uniform random 48-bit signed integers overflows a 64-bit signed integer?

Edit: the overflow can occur at any step, not only on the final result.

Since this is a normal distribution, I guess that the cumulative sums more or less oscillate around zero, and that the probability that they ever exceed 64 bits is vanishingly small. I would like to formalise this intuition.

Solution

Calculate the average and variance of choosing a single signed 48 bit variable. Multiply by n to get the average and variance of choosing n 48 bit variables. The standard variation is roughly the square root of the variance.

Calculate how many standard deviations away from the average you need to be for an overflow. The probability of being more than k standard deviations away from the mean is about exp(-k^2).

Now that is the probability of overflow after summing n numbers. It ignores the possibility that the sum might overflow and then become smaller again. So the probability of overflow at some point within n steps is higher.

Context

StackExchange Computer Science Q#165363, answer score: 7

Revisions (0)

No revisions yet.