aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorDave Barach <dave@barachs.net>2017-12-12 10:22:27 -0500
committerDave Barach <dave@barachs.net>2017-12-12 10:22:59 -0500
commit0c332a358533ed24e2130b071c9250e3fae9f745 (patch)
treebb51b26418e96f2788728862eef7996feb1b56f1 /src
parent4112e389ea934463fd2160c8f24edaf11bc931b0 (diff)
Add chi-squared test statistic calculator to random.c
Change-Id: I0a0f8c9aad1530d18c70c962e729e84948a074ee Signed-off-by: Dave Barach <dave@barachs.net>
Diffstat (limited to 'src')
-rw-r--r--src/vppinfra/random.c47
-rw-r--r--src/vppinfra/random.h2
-rw-r--r--src/vppinfra/test_random.c60
3 files changed, 108 insertions, 1 deletions
diff --git a/src/vppinfra/random.c b/src/vppinfra/random.c
index fa5bcc8c78a..e54a3bc8c7c 100644
--- a/src/vppinfra/random.c
+++ b/src/vppinfra/random.c
@@ -37,11 +37,56 @@
#include <vppinfra/random.h>
-/* Default random seed for standalone version of library.
+/** \file Random number support
+ */
+
+/** \brief Default random seed for standalone version of library.
Value can be overridden by platform code from e.g.
machine's clock count register. */
u32 standalone_random_default_seed = 1;
+/**
+ * \brief Compute the X2 test statistic for a vector of counts.
+ * Each value element corresponds to a histogram bucket.
+ *
+ * Typical use-case: test the hypothesis that a set of octets
+ * are uniformly distributed (aka random).
+ *
+ * In a 1-dimensional use-case, the result should be compared
+ * with the critical value from chi square tables with
+ * vec_len(values) - 1 degrees of freedom.
+ *
+ * @param[in] values vector of histogram bucket values
+ * @return d - Pearson's X2 test statistic
+ */
+
+f64
+clib_chisquare (u64 * values)
+{
+ int i;
+ f64 d, delta_d, actual_frequency, expected_frequency;
+ u64 n_observations = 0;
+
+ ASSERT (vec_len (values));
+
+ for (i = 0; i < vec_len (values); i++)
+ n_observations += values[i];
+
+ expected_frequency = (1.0 / (f64) vec_len (values)) * (f64) n_observations;
+
+ d = 0.0;
+
+ for (i = 0; i < vec_len (values); i++)
+ {
+ actual_frequency = ((f64) values[i]);
+ delta_d = ((actual_frequency - expected_frequency)
+ * (actual_frequency - expected_frequency))
+ / expected_frequency;
+ d += delta_d;
+ }
+ return d;
+}
+
/*
* fd.io coding-style-patch-verification: ON
*
diff --git a/src/vppinfra/random.h b/src/vppinfra/random.h
index 5c139d05490..bceab419567 100644
--- a/src/vppinfra/random.h
+++ b/src/vppinfra/random.h
@@ -167,6 +167,8 @@ random_string (u32 * seed, uword len)
return s;
}
+f64 clib_chisquare (u64 * values);
+
#endif /* included_random_h */
/*
diff --git a/src/vppinfra/test_random.c b/src/vppinfra/test_random.c
index 49759eacb97..64513d56b57 100644
--- a/src/vppinfra/test_random.c
+++ b/src/vppinfra/test_random.c
@@ -38,6 +38,42 @@
#include <vppinfra/format.h>
#include <vppinfra/bitmap.h>
+static u32 outcome_frequencies[] = {
+ 8, 5, 9, 2, 7, 5,
+};
+
+
+int
+test_chisquare (void)
+{
+ u64 *values = 0;
+ int i;
+ f64 d, delta_d;
+
+ vec_validate (values, 5);
+
+ for (i = 0; i < 6; i++)
+ values[i] = (u64) outcome_frequencies[i];
+
+ d = clib_chisquare (values);
+
+ delta_d = d - 5.333;
+
+ if (delta_d < 0.0)
+ delta_d = -delta_d;
+
+ if (delta_d < 0.001)
+ {
+ fformat (stdout, "chisquare OK...\n");
+ return 0;
+ }
+ else
+ {
+ fformat (stdout, "chisquare BAD, d = %.3f\n", d);
+ return -1;
+ }
+}
+
static u32 known_random_sequence[] = {
0x00000000, 0x3c6ef35f, 0x47502932, 0xd1ccf6e9,
0xaaf95334, 0x6252e503, 0x9f2ec686, 0x57fe6c2d,
@@ -54,6 +90,8 @@ test_random_main (unformat_input_t * input)
uword print;
u32 seed;
u32 *seedp = &seed;
+ u64 *counts = 0;
+ f64 d;
/* first, check known sequence from Numerical Recipes in C, 2nd ed.
page 284 */
@@ -118,6 +156,28 @@ test_random_main (unformat_input_t * input)
continue;
}
+ if (test_chisquare ())
+ return (-1);
+
+ /* Simple randomness tests based on X2 stats */
+ vec_validate (counts, 255);
+
+ for (i = 0; i < 1000000; i++)
+ {
+ u32 random_index;
+ u32 r = random_u32 (&seed);
+
+ random_index = r & 0xFF;
+
+ counts[random_index]++;
+ }
+
+ d = clib_chisquare (counts);
+
+ fformat (stdout, "%d random octets, chisquare stat d = %.3f\n", i, d);
+
+ vec_free (counts);
+
return 0;
}