A generalized fast algorithm for BDS-type statistics

Abstract

Describimos un algoritmo rápido para caluclar el histograma de m-distancias en que se basan los estadísticos tipo BDS. El algoritmo generaliza uno que implementa LeBaron, calculando el histograma para cualquier conjunto finito de distancias simultáneamente. Reordenando el cálculo apropiadamente, el algoritmo utiliza menos memoria. Los dos algoritmos son comparados utilizando la implementación de LeBaron's en lenguaje C para MSDOS y la nuestra en Delphi (Pascal para Windows). El algoritmo generalizado es más rápido cuando se requieren más de dos valores de epsilon (el parámetro de distancia), y está implementado para calcular 255 distancias utilizando aritmética de enteros cortos.

We provide a fast algorithm to calculate the m-dimensional distance histogram on which 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. By reordering the calculation appropriately, the algorithm also requires less memory. The two algorithms are compared using LeBaron's MSDOS implementation in C and our Delphi (Windows Pascal) program. The generalized algorithm is faster when more than one value of epsilon (the distance parameter) is required, and is set up to calculate up to 255 values using short integer arithmetic.