# KS-Statistic in C++

Consider the MCG with parameters: a = 23, M = 10^8 + 1, and let the seed be 47594118. (This is the original MCG proposed by Lehmer in 1948.) Apply the Kolmogorov-Smirnov test to the first 1000 random numbers (including the seed) from this generator. Compute the KS-statistic and find its p-value. What is your conclusion for the generator?

I was able to compute the MCG successfully but I am not sure how to compute the KS-statistic. From the notes I have we use the cumulative distribution function for distribution U(0,1), then computing the KS-statistic D_n (I will post the math here in a picture):

Here is my code:

#include <iostream>
#include <cmath>
#include <math.h>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

double *MCG(int n);
double max_array(int n, double D[]);
void KS(int n, double u[]);

int main(){
int n = 1000;
double *u = new double[n];
u = MCG(n);
KS(n,u);

return 0;
}

double max_array(int n, double D[]){
double arr[n];
arr[0] = 0;
double max;
for(int i = 0; i < n; i++)
{
if(arr[0] < D[i])
arr[0] = D[i];
}
max = arr[0];
return max;
}

double *MCG(int n){
double *x = new double[n];
double a = 23.0;
x[0] = 47594118; // Set seed to 47594118
for(int i = 1; i < n; i++){
x[i] = fmod(a*x[i-1], pow(10.0,8.0) + 1);
//cout << setprecision(10) << x[i] << endl;
}
double *u = new double[n];
for(int i = 0; i < n; i++){
u[i] = x[i]/(pow(10.0,8.0) + 1);
//cout << u[i] << endl;
}
return u;
}

void KS(int n, double u[]){
sort(u,u + n);
double D_plus[n];
double D_minus[n];
double D_N[n];
for(int i = 0; i < n; i++){
for(int k = 1; k <= n; k++){
D_plus[i] = (double)k/n - u[i];
D_minus[i] = u[i] - (double)(k-1)/n;
}
}
for(int i = 0; i < n; i++){
D_N[i] = fmax(D_plus[i],D_minus[i]);
//cout << D_N[i] << endl;
}
cout << max_array(n,D_N) << endl;
}


I get this output:

0.999556


I am not sure if this is the correct way of computing D_N any suggestions are greatly appreciated. A colleague of mine gets this value:

0.999817


The associated p-value for both of these is 0. Although, another colleague of mine got 0.037.

• As it stands I can't compile this due to your (non-pointer)array definitions being non-constant values. Replacing them with 1000 as your n suggests allows it to run but you are leaking memory. – user122352 Feb 8 '17 at 1:47
• @NickA it ran ok with me using Eclipse.. – Scooby Feb 8 '17 at 2:54
• I'm using Visual Studio. – user122352 Feb 8 '17 at 8:38