A Generalized Fast Algorithm for BDS-Type Statistics

We provide a fast algorithm to calculate the m-dimensional distance histogram on which Brock, Dechert, and Sheinkman's (1987) BDS-type statistics are based. The algorithm generalizes a fast algorithm due to LeBaron by calculating the histogram for any finite set of distances simultaneously, and also using induction in m. By reordering the calculation appropriately, the algorithm also requires less memory and time. The two algorithms are compared using LeBaron's MS-DOS implementation in C and our Delphi (Windows Pascal) program. The generalized algorithm is faster when more than a few values of m and M (the distance parameter) are required, and is set up to calculate up to 255 values using short-integer arithmetic.