# 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

```import math # for sqrt

def isRandom(randomNums, 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." """
#Calculate the number of samples - N
N = len(randomNums)

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

N_r = N / r
chi_square = 0.0

#PART A: Get frequency of randoms
HT = getFrequencies(randomNums)

#PART B: Calculate chi-square - this approach is in Sedgewick
for v in HT.itervalues():
f = v - N_r
chi_square += f * f

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"
return abs(chi_square - r) <= 2 * math.sqrt(r)

def getFrequencies(nums):
""" Gets the frequency of occurrence of a randomly generated array of integers
Output: A dictionary, key being the random number and value its frequency """
freqs = {}

for x in nums:
if x in freqs:
freqs[x] += 1
else:
freqs[x] = 1

return freqs
```