3
\$\begingroup\$

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):

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user122352 Feb 8 '17 at 1:47
  • \$\begingroup\$ @NickA it ran ok with me using Eclipse.. \$\endgroup\$ – Scooby Feb 8 '17 at 2:54
  • \$\begingroup\$ I'm using Visual Studio. \$\endgroup\$ – user122352 Feb 8 '17 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.