68–95–99.7 rule for binomial distribution? What I want to calculate is the probability that the size $k'$ of an intersection of two subgroups with sizes $n$ and $K$ that have been randomly selected from a group with size $N$ that is smaller than $k$. 
This is described by the cumulative hypergeometric probability. Because I have to calculate this probability for millions of cases and $N>>n,K$, I decided to use the binomial distribution as an approximation. 
So, there are $N$ elements, I choose n randomly and each one of them belongs to subgroup2 with $p=\frac{K}{N}$. 
Calculating the cumulative binomial probability is still too slow. But if the binomial distribution would be the normal distribution I could apply the 68-95-99.7 rule. As I understand it, this would tell me for example that a three $\sigma$ distance from the mean only happens with $probability=0.3\%$.
But the binomial distribution is skewed and I'm only interested in the probability of a positive deviation from the mean, so my question is whether there is some formula for that.
As evidenced by this question I don't know anything about statistics, so a good answer would take my lack of general statistics knowledge into account.
 A: As already mentioned by others, Demoivre-Laplace Theorem says that binomial distribution can be approximated using normal distribution and law of small numbers says that it can be approximated using Poisson distribution. With $p$ near to the boundaries, normal approximation does not work well.
As you can see from the following example, the actual coverage of mean $\pm$ one (first plot), two (second plot), or three standard deviations from the mean depend on $n$ (colors) and $p$ (x-axis) parameters. The coverage expected from the normal distribution is shown using the dotted line. In many cases the binomial coverage is close (especially in $\pm3$ SD case), but there are cases when it is far from what normal distribution tells us.

So in your case, you should ask yourself two questions: (1) how good/bad is normal approximation is for the range of parameters that can be seen in your data, (2) how precise do you want to be (you'd be already introducing the second layer of approximation!).

As a side-note: why the computation is slow? Computation in general should not be that slow. Moreover, if you have fixed parameters, then what you can do is first to compute probabilities for each $k$ in $1,\dots,N$ and then simply read the probabilities from the per-computed table. Since there are recursive algorithms for calculating the binomial probabilities, this should be computationally very fast (computation time depends on $N$ and is independent of how many samples do you have). Moreover, you possibly can use the symmetries of hypergeometric distribution to speed things up.
