A simple empirical formula for categorizing computing operations

摘要

We propose a simple empirical formula for categorizing computing operations using nested loops.In essence, we want to test the hypothesis that two computing operations are the same (in some statistical sense). To test this hypothesis, we would construct a function of the computing times required for each called revised differences di’s defined as [(Xi −Yi)/{(Xi + Yi)/2}] and then construct a t-statistic based on the sample mean and sample mean square of these di’s. If the data are approximately normal, then the t-statistic will have an approximate Student’s-t distribution. We next propose some alternative tests as robustness against the normality assumption. To combat idiosyncrasies of computer clocks, the operations are kept inside a nested loop and observed for input size sufficiently large for reliable run time measurements. The formula we provide here is however more effective for comparing “compound operations” (that is, a group of operations taken as a whole) and we caution the reader against the dangerous practice of trying to isolate individual operations from a compound one while using this formula. As the formula helps us in deciding whether a group of operations is likely to be efficient or inefficient if implemented in a larger code, we propose to use it in conjunction with the philosophy of measurement and tuning which is a practical method of improving the efficiency of actual running programs.