commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Artem Barger (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (RNG-5) Create API usage demo example application.
Date Wed, 10 Aug 2016 11:06:20 GMT

    [ https://issues.apache.org/jira/browse/RNG-5?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15415122#comment-15415122
] 

Artem Barger commented on RNG-5:
--------------------------------

I was thinking to add Chi-Square test for randomness of different PNRG within the project,
see code below:

{code:java}
/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.commons.rng;

import java.util.HashMap;
import java.util.Map;

/**
 * A demo application to demonstrate the basic usage of commons rng library
 * by showing the computation of chi-square test of randomness of generators
 * provided by in the project.
 * <p>
 * Application to be executed with set of input parameters:
 * - how many numbers to generate
 * - with how many bins we would like to test
 * - reference to the implementation of {@link UniformRandomProvider} interface
 * <p>
 * <p/>
 * The chi-square test published by Karl Pearson and for given sequence of
 * observation is able to approximate the probability of the outcome assuming
 * certain probability distribution.
 * <p/>
 * Test works as following (Knuth vol.2), suppose we have n independent observation
 * (a sequence of random values we generated), each falling into one of k categories.
 * Let Y_i denote the number of observations within given category i and p_i  is the
 * probability of that observed item will fall into category i. So in our case where
 * we assuming the uniform distribution p_i = 1/k. Next we compute the sum:
 * <p>
 * $\sum_{1 \ge i \ge k}\frac{Y_i - np_i}{np_i}$
 * <p>
 * and finally we can compare the value received with "Chi-Square Distribution Table"
 * to identify the likelyhood of given observation for example, where
 * degree of freedom is defined as k - 1. Reasonable PRNG should produce result which
 * leads to probability of chi sqare value between 25% and 75%.
 *
 * @see <a href="https://en.wikipedia.org/wiki/Chi-squared_test">
 * <a href="http://sites.stat.psu.edu/~mga/401/tables/Chi-square-table.pdf" />
 */
public class ChiSquareRandom {

    /**
     * Number of random numbers to generate.
     */
    private int count;

    /**
     * Number of categories to split generated values to.
     */
    private int binsCnt;

    /**
     * Random source provider.
     */
    private UniformRandomProvider provider;

    /**
     * Categories counters.
     */
    private Map<Integer, Integer> bins = new HashMap<Integer, Integer>();

    /**
     * Create Chi-Square test to evaluate PRNG algorithm
     *
     * @param count   - how many numbers to generates
     * @param binsCnt - the number of categories to associate numbers with
     * @param source  - random source {@link RandomSource} to indicate the RNG algorithm
     */
    public ChiSquareRandom(int count, int binsCnt, RandomSource source) {
        this.count = count;
        this.binsCnt = binsCnt;
        this.provider = RandomSource.create(source);
    }

    /**
     * Generates the sequence of random numbers and computes chi square value based on
     * formula: $\sum_{1 \ge i \ge k}\frac{Y_i - np_i}{np_i}$, where n is the length of
     * the random sequence, $p_i$ is the probability of value to fall into category $i$
     * and $Y_i$ is the observed amount of values within category $i$.
     *
     * @return the chi square test value
     */
    public double chiSquare() {
        for (int i = 0; i < count; i++) {
            final int bin = provider.nextInt(Integer.MAX_VALUE) % binsCnt;
            final Integer currentCount = bins.get(bin);
            if (currentCount == null) {
                bins.put(bin, 1);
            } else {
                bins.put(bin, currentCount + 1);
            }
        }

        double result = 0;
        for (Integer each : bins.values()) {
            final double np = (1d * count) / binsCnt;
            final double v = each - np;
            result += (v * v) / np;
        }

        return result;
    }

    public static void main(String[] args) {
        if (args.length != 3) {
            System.out.println("Invalid input parameters, expected input format is: ");
            System.out.println("ChiSquareRandom <count> <bins> <randomSource>");
            System.out.println("<count> - amount of random numbers to generate");
            System.out.println("<bins> - the categories count");
            System.out.println("<randomSource> - random source");

            final StringBuilder allowedSourcesNames = new StringBuilder();
            for (RandomSource source : RandomSource.values()) {
                allowedSourcesNames.append(", ").append(source.name());
            }

            System.out.println("\t\t <randomSource> parameter value could be one of:
"
                    + allowedSourcesNames.toString().replaceFirst(", ", ""));

            System.exit(-1);
        }

        final Integer count = Integer.valueOf(args[0]);
        final Integer bins = Integer.valueOf(args[1]);

        if (count / bins < 10) {
            System.out.println("ERROR: In order to get correct results ration between <count>
" +
                    "parameter and <bins> should be at least greater than 10.");
            System.exit(-1);
        }

        final RandomSource randomSource = RandomSource.valueOf(args[2]);

        final ChiSquareRandom chiSquareTest = new ChiSquareRandom(count, bins, randomSource);
        System.out.println("The Chi-Square value = " + chiSquareTest.chiSquare());
        System.out.println();
        System.out.println();
        System.out.println("Refer to http://sites.stat.psu.edu/~mga/401/tables/Chi-square-table.pdf,"
+
                " to check whenever result is acceptable or not. Good PNRG should produce
results within 25%-75% range.");
    }
}
{code}

Thoughts?

> Create API usage demo example application.
> ------------------------------------------
>
>                 Key: RNG-5
>                 URL: https://issues.apache.org/jira/browse/RNG-5
>             Project: Commons RNG
>          Issue Type: Task
>            Reporter: Artem Barger
>
> Need to create a demo application for user guide to demonstrate how to use the API and
show possible application.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message