# Algorithm Implementation/Pseudorandom Numbers/Chi-Square Test

## VB.NET

The following is a program to calculate the chi-square value for N positive integers less than r.

```    'Calculates the chi-square value for N positive integers less than r
'Source: "Algorithms in C" - Robert Sedgewick - pp. 517
'NB: Sedgewick recommends: "...to be sure, the test should be tried a few times,
'since it could be wrong in about one out of ten times."
Public Function IsChiRandom(ByVal randomNums() As Integer, ByVal r As Integer) As Boolean

'Calculate the number of samples - N
Dim N As Integer = randomNums.Length

'According to Sedgewick: "This is valid if N is greater than about 10r"
If N <= (10 * r) Then
Return False
End If

Dim N_r As Double = N / r
Dim HT As Hashtable
Dim chi_square As Double = 0

'PART A: Get frequency of randoms
HT = Me.RandomFrequency(randomNums)

'PART B: Calculate chi-square - this approach is in Sedgewick
Dim f As Integer
For Each Item As DictionaryEntry In HT
f = Integer.Parse(Item.Value) - N_r
chi_square += Math.Pow(f, 2)
Next
chi_square = chi_square / N_r

'PART C: According to Sedgewick: "The statistic should be within 2(r)^1/2 of r
'This is valid if N is greater than about 10r"

If (r - 2 * Math.Sqrt(r) <= chi_square) And (r + 2 * Math.Sqrt(r) >= chi_square) Then
Return True
Else
Return False
End If

End Function

'Gets the frequency of occurrence of a randomly generated array of integers
'Output: A hashtable, key being the random number and value its frequency
Private Function RandomFrequency(ByVal randomNums() As Integer) As Hashtable

Dim HT As New Hashtable
Dim N As Integer = randomNums.Length

Dim count As Integer = 0
For i As Integer = 0 To N - 1
If HT.ContainsKey(randomNums(i)) Then
HT.Item(randomNums(i)) = HT.Item(randomNums(i)) + 1
Else
End If
Next

Return HT

End Function
```

## C#

```	// Calculates the chi-square value for N positive integers less than r
// Source: "Algorithms in C" - Robert Sedgewick - pp. 517
// NB: Sedgewick recommends: "...to be sure, the test should be tried a few times,
// since it could be wrong in about one out of ten times."
public bool IsRandom(int[] randomNums, int r)
{
//Calculate the number of samples - N
int N = randomNums.Length;

//According to Sedgewick: "This is valid if N is greater than about 10r"
if (N <= 10*r)
return false;

double N_r = N / r;
double chi_square = 0;
Hashtable HT;

//PART A: Get frequency of randoms
HT = this.RandomFrequency (randomNums);

//PART B: Calculate chi-square - this approach is in Sedgewick
double f;
foreach (DictionaryEntry Item in HT)
{
f = (int)(Item.Value) - N_r;
chi_square += Math.Pow(f, 2);
}
chi_square = chi_square / N_r;

//PART C: According to Swdgewick: "The statistic should be within 2(r)^1/2 of r
//This is valid if N is greater than about 10r"
if((r - 2 * Math.Sqrt (r) <= chi_square) &  (r + 2 * Math.Sqrt (r) >= chi_square))
return true;
else
return false;
}

//Gets the frequency of occurrence of a randomly generated array of integers
//Output: A hashtable, key being the random number and value its frequency
private Hashtable RandomFrequency(int[] randomNums)
{
Hashtable HT = new Hashtable();
int N = randomNums.Length;

for(int i = 0; i <= N-1; i++)
{
if (HT.ContainsKey(randomNums[i]))
HT[randomNums[i]] = (int) HT[randomNums[i]] + 1;
else
HT[randomNums[i]] = 1;
}

return HT;
}
```

## Java

```	/**
* Calculates the chi-square value for N positive integers less than r
* Source: "Algorithms in C" - Robert Sedgewick - pp. 517
* NB: Sedgewick recommends: "...to be sure, the test should be tried a few times,
* since it could be wrong in about one out of ten times."
* @param  randomNums  a uniformly-randomly-generated array of integers
* @param  r           upper bound for the random range
* @return             whether it is likely to be uniformly randomly generated
*/
public static boolean isRandom(int[] randomNums, int r)
{
//According to Sedgewick: "This is valid if N is greater than about 10r"
if (randomNums.length <= 10 * r)
return false;

//PART A: Get frequency of randoms
Map<Integer,Integer> ht = getFrequencies(randomNums);

//PART B: Calculate chi-square - this approach is in Sedgewick
double n_r = (double)randomNums.length / r;
double chiSquare = 0;

for (int v : ht.values())
{
double f = v - n_r;
chiSquare += f * f;
}
chiSquare /= n_r;

//PART C: According to Swdgewick: "The statistic should be within 2(r)^1/2 of r
//This is valid if N is greater than about 10r"
return Math.abs(chiSquare - r) <= 2 * Math.sqrt(r);
}

/**
* @param  nums  an array of integers
* @return       a Map, key being the number and value its frequency
*/
private static Map<Integer,Integer> getFrequencies(int[] nums)
{
Map<Integer,Integer> freqs = new HashMap<Integer,Integer>();

for (int x : nums)
{
if (freqs.containsKey(x))
freqs.put(x, freqs.get(x) + 1);
else
freqs.put(x, 1);
}

return freqs;
}
```

## Python

```from math import sqrt
from collections import Counter

def is_random(random_nums, r: int):
"""Calculates the chi-square value for n positive integers less than r

Arguments:
- random_nums: list of uniformly-randomly generated integers
- r: int, upper bound for the random range

Source: "Algorithms in C" - Robert Sedgewick - pp. 517

NB: Sedgewick recommends:

...to be sure, the test should be tried a few times, since it could be
wrong in about one out of ten times.

Example:

>>> import os
>>> r = 256
>>> sample = os.urandom(r * 11)
>>> is_random(sample, r)
True

"""
# Calculate the number of samples - n
n = len(random_nums)

# According to Sedgewick:
# This is valid if n is greater than about 10r
if n <= 10 * r:
return False

n_r = n / r

# PART A: Get frequency of randoms
ht = Counter(random_nums)

# PART B: Calculate chi-square - this approach is in Sedgewick
chi_square = sum((v - n_r)**2 for v in ht.values()) / n_r

# PART C: According to Sedgewick:
# The statistic should be within 2(r)^1/2 of r
# This is valid if N is greater than about 10r
return abs(chi_square - r) <= 2 * sqrt(r)
```