How to resolve the algorithm Benford's law step by step in the Scheme programming language

Published on 12 May 2024 09:40 PM
#Scheme

How to resolve the algorithm Benford's law step by step in the Scheme programming language

Table of Contents

Problem Statement

Benford's law, also called the first-digit law, refers to the frequency distribution of digits in many (but not all) real-life sources of data. In this distribution, the number 1 occurs as the first digit about 30% of the time, while larger numbers occur in that position less frequently: 9 as the first digit less than 5% of the time. This distribution of first digits is the same as the widths of gridlines on a logarithmic scale. Benford's law also concerns the expected distribution for digits beyond the first, which approach a uniform distribution. This result has been found to apply to a wide variety of data sets, including electricity bills, street addresses, stock prices, population numbers, death rates, lengths of rivers, physical and mathematical constants, and processes described by power laws (which are very common in nature). It tends to be most accurate when values are distributed across multiple orders of magnitude. A set of numbers is said to satisfy Benford's law if the leading digit

d

{\displaystyle d}

(

d ∈ { 1 , … , 9 }

{\displaystyle d\in {1,\ldots ,9}}

) occurs with probability For this task, write (a) routine(s) to calculate the distribution of first significant (non-zero) digits in a collection of numbers, then display the actual vs. expected distribution in the way most convenient for your language (table / graph / histogram / whatever). Use the first 1000 numbers from the Fibonacci sequence as your data set. No need to show how the Fibonacci numbers are obtained. You can generate them or load them from a file; whichever is easiest. Display your actual vs expected distribution.

For extra credit: Show the distribution for one other set of numbers from a page on Wikipedia. State which Wikipedia page it can be obtained from and what the set enumerates. Again, no need to display the actual list of numbers or the code to load them.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Benford's law step by step in the Scheme programming language

Source code in the scheme programming language

; Compute the probability of leading digit d (an integer [1,9]) according to Benford's law.

(define benford-probability
  (lambda (d)
    (- (log (1+ d) 10) (log d 10))))

; Determine the distribution of the leading digit of the sequence provided by the given
; generator.  Return as a vector of 10 elements -- the 0th element will always be 0.

(define leading-digit-distribution
  (lambda (seqgen count)
    (let ((digcounts (make-vector 10 0)))
      (do ((index 0 (1+ index)))
          ((>= index count))
        (let* ((value (seqgen))
               (string (format "~a" value))
               (leadchr (string-ref string 0))
               (leaddig (- (char->integer leadchr) (char->integer #\0))))
          (vector-set! digcounts leaddig (1+ (vector-ref digcounts leaddig)))))
      (vector-map (lambda (digcnt) (/ digcnt count)) digcounts))))

; Create a Fibonacci sequence generator.

(define make-fibgen
  (lambda ()
    (let ((fn-2 0) (fn-1 1))
      (lambda ()
        (let ((fn fn-1))
          (set! fn-1 (+ fn-2 fn-1))
          (set! fn-2 fn)
          fn)))))

; Create a sequence generator that returns elements of the given vector.

(define make-vecgen
  (lambda (vector)
    (let ((index 0))
      (lambda ()
        (set! index (1+ index))
        (vector-ref vector (1- index))))))

; Read all the values in the given file into a list.

(define list-read-file
  (lambda (filenm)
    (call-with-input-file filenm
      (lambda (ip)
        (let accrue ((value (read ip)))
          (if (eof-object? value)
            '()
            (cons value (accrue (read ip)))))))))

; Display a table of digit, Benford's law, sequence distribution, and difference.

(define display-table
  (lambda (seqnam seqgen count)
    (printf "~%~3@a ~11@a ~11@a ~11@a~%" "dig" "Benford's" seqnam "difference")
    (let ((dist (leading-digit-distribution seqgen count)))
      (do ((digit 1 (1+ digit)))
          ((> digit 9))
        (let* ((fraction (vector-ref dist digit))
               (benford (benford-probability digit))
               (diff (- fraction benford)))
          (printf "~3d ~11,5f ~11,5f ~11,5f~%" digit benford fraction diff))))))

; Emit tables of various sequence distributions.

(display-table "Fib/1000" (make-fibgen) 1000)
(display-table "Rnd/1T/1M" (lambda () (1+ (random 1000000000000))) 1000000)
(let ((craters (list->vector (list-read-file "moon_craters.lst"))))
  (display-table "Craters/D" (make-vecgen craters) (vector-length craters)))

You may also check:How to resolve the algorithm RIPEMD-160 step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Assertions step by step in the Z80 Assembly programming language
You may also check:How to resolve the algorithm Strip block comments step by step in the Ada programming language
You may also check:How to resolve the algorithm Vector products step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Factorial step by step in the Wren programming language