mardi 16 juillet 2019

kolmogorov smirnov and chi-square test for LCG

how to make chi-square and kolmogorov_smirnov test for my random number generator? ( LCG - logarithmic skip ahead (and back))

Here is my LCG:

import numpy as np

class LCG(object):

    UZERO: np.uint32 = np.uint32(0)
    UONE : np.uint32 = np.uint32(1)

    def __init__(self, seed: np.uint32, a: np.uint32, c: np.uint32) -> None:
        self._seed: np.uint32 = np.uint32(seed)
        self._a   : np.uint32 = np.uint32(a)
        self._c   : np.uint32 = np.uint32(c)

    def next(self) -> np.uint32:
        self._seed = self._a * self._seed + self._c
        return self._seed

    def seed(self) -> np.uint32:
        return self._seed

    def set_seed(self, seed: np.uint32) -> np.uint32:
        self._seed = seed

    def skip(self, ns: np.int32) -> None:
        """
        Signed argument - skip forward as well as backward

        The algorithm here to determine the parameters used to skip ahead is
        described in the paper F. Brown, "Random Number Generation with Arbitrary Stride,"
        Trans. Am. Nucl. Soc. (Nov. 1994). This algorithm is able to skip ahead in
        O(log2(N)) operations instead of O(N). It computes parameters
        A and C which can then be used to find x_N = A*x_0 + C mod 2^M.
        """

        nskip: np.uint32 = np.uint32(ns)

        a: np.uint32 = self._a
        c: np.uint32 = self._c

        a_next: np.uint32 = LCG.UONE
        c_next: np.uint32 = LCG.UZERO

        while nskip > LCG.UZERO:
            if (nskip & LCG.UONE) != LCG.UZERO:
                a_next = a_next * a
                c_next = c_next * a + c

            c = (a + LCG.UONE) * c
            a = a * a

            nskip = nskip >> LCG.UONE

        self._seed = a_next * self._seed + c_next

np.seterr(over='ignore')

a = np.uint32(1664525)
c = np.uint32(1013904223)
seed = np.uint32(1)

rng = LCG(seed, a, c)

print(rng.next())
print(rng.next())
print(rng.next())

rng.skip(-3) # back by 3
print(rng.next())
print(rng.next())
print(rng.next())

rng.skip(-3) # back by 3
rng.skip(2) # forward by 2
print(rng.next())

#%% 10k
#np.seterr(over='ignore')

#a = np.uint32(1664525)
#c = np.uint32(1013904223)
#seed = np.uint32(1)

#rng = LCG(seed, a, c)
#q = [rng.next() for _ in range(0, 10000)]
#print(q)

below is the code for the kol-smirnov test which I still need to adjust, but I have no idea how to do a chi-square test and a birthday-spacing.

# Step 1:  Rank data from smallest to largest, such that:
# R(1) <= R(2) <= R(3) ... <= R(i)
data_set.sort()

# Step 2: Computer D+ and D-
# D+ = max(i/N - R(i))
d_plus = get_d_plus_value_for_KS_TEST(data_set, num_samples)
print ("D+ VALUE ="+str(d_plus))

# D- = max(R(i) - (i -1)/n)
d_minus = get_d_minus_value_for_KS_TEST(data_set, num_samples)
print ("D- VALUE="+str(d_minus))

# Step 3:  Computer D = max(D+,D-)
d_value = max(d_plus, d_minus)
print ("D VALUE (max): "+str(d_value))

# Step 4: Determine critical value, using table
# Step 5: Accept or reject Null hypothesis
return d_value

What should I do best to test for uniformity and independence?




Aucun commentaire:

Enregistrer un commentaire