fast approximation of degree of normality, given order statistics In a software application, I have access to the order statistics (without any extra computational cost) of a collection of $N$ samples (where $N$ can vary and is often quite large, usually on the order of $10^4$). I would like to quickly determine a rough and approximate degree of normality for the samples, without incurring a huge computational overhead. Note that I do not need a formal boolean test of normality; quantitative confidence or p-values are not important here. I only need some metric or test statistic that will approximately vary along with the degree of normality of the current collection of samples.
I have looked at some options in the literature and fear they may incur too much processing time (and be overkill for my needs, as I only need something loosely approximate). For example, the Anderson–Darling test statistic involves repeated ln() and erf() calls (please correct me if I'm wrong), which are not very cheap for large $N$. The Shapiro–Wilk test statistic seems somewhat promising, but I am unclear on how much is involved in calculating the coefficients $\alpha_i$. It looks like it could be complex (or involve a very large lookup table?)--and would these coefficients need to be recalculated completely if $N$ changes (which can happen frequently in my application)?
The Shapiro-Francia test seems powerful and simple, but there is no closed-form analytic expression for the values of $m_{i:n}$ required by the test. Is there a good, computationally cheap approximation for the $i^{th}$ mean of the order statistics for large $N$?
Maybe the Kolmogorov-Smirnov test statistic is my best bet, because the only "expensive" function needed is erf() and there may be ways to cheaply scale/interpolate these normal CDF values for changing $N$. For example, maybe I can precompute it for a very large $N$ and then downscale/interpolate quickly to any smaller $N$.
Is there any computationally cheap test statistic I can calculate, maybe even just using empirical z-scores or something? Any help is appreciated.

Here is a sketch of a possible methodology.

*

*Set up $2k+1$ bins of equal probability from inverse cumulative normal distribution.


*Estimate the mean $\hat{\mu}$ and variance $\hat{\sigma}$.


*Standardize the sample points, $z_i = \frac{x_i-\hat{\mu}}{\hat{\sigma}}$


*Count the number of standardized sample points $z_i$ in each bin $j$ to get empirical probability distribution by bin, accumulate bin probability $P_j$ with $\frac{1}{N}$ increment per data point in bin $j$.


*Use the discrete KL-divergence measure as your statistic. KL-divergence is asymmetric, use empirical distribution for $P_j$, $\frac{1}{2k+1}$ for $Q_j$.


*$D_\text{KL}(P \parallel Q)  = \sum\limits_{j=1}^{2k+1} P_j \log\left(\frac{P_j}{Q_j}\right) ~.$
You can set up the bins once (small constant overhead), the other operations are proportional to the number of data points, so your $O(N)$ requirement should be realized. I would not worry about computational costs of functions like log() for $2k+1$ bins.
