Preprint. APES Research Report, 2001.
ISSN/ISBN: Not available at this time. DOI: Not available at this time.
There are no links available at this time.
Abstract: Benfordís Law predicts the frequency of the leading digit in numbers met in a wide range of naturally occurring phenomena. In data following Benfordís Law, numbers start with a small leading digit more often those with a large leading digit. Here we demonstrate that Benfordís Law also describes a wide range of computational phenomena. In particular, we show that a number of different statistics associated with computation like space and runtime often follow Benfordís Law. We also show that search cost on input data that follows Benfordís Law is often very different to that on more uniform data. These results could be used to improve algorithm performance (for example, for load balancing or disk de-fragmentation), as well as to help model algorithm performance. Benfordís Law can also be used to generate data for benchmarking algorithms that may be more realistic than purely random data
Not available at this time.
Reference Type: Preprint
Subject Area(s): Computer Science