Full cycle

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For the record label, see Full Cycle Recordings.

A full cycle is a mathematical term that represents a traversal over a set of non-random numbers. A full cycle implies that every number in the set was chosen exactly once before repeating.

Full cycles are useful in pseudorandom number generators.

Example 1 (in C++)[edit]

Given a random number seed that is greater or equal to zero. Given a total sample size greater than 1. Given a prime number that cannot be evenly divided into the total sample size.

A full cycle can be generated with the following logic. Each number in the sample_size should occur once.

unsigned int random_seed = 0;
unsigned int sample_size = 3000;
unsigned int generated_number = random_seed % sample_size;
unsigned int prime_number = 7;
unsigned int increment = prime_number;
for(unsigned int iterator = 0; iterator < sample_size; ++iterator)
{
   generated_number = (generated_number + increment) % sample_size;
}

Example 1 (in python)[edit]

# generator that goes through a full cycle
def cycle(seed, sample_size, prime):
    nb = seed
    for i in xrange(sample_size):
        nb = (nb + prime) % sample_size
        yield nb
 
# example values
seed = 17
sample_size = 100
prime = 13
 
# print all the numbers
for nb in cycle(seed, sample_size, prime):
    print nb
 
# verify that all numbers were generated correctly
assert sorted(cycle(seed, sample_size, prime)) == range(sample_size)
 
# compare shifted cycles
c1 = list(cycle(seed, sample_size, prime))
c2 = list(cycle(seed + prime, sample_size, prime))
assert c2[:-1] == c1[1:]
assert c2[-1] == c1[0]

Example 2 (in C++)[edit]

#include <stdio.h>
 
int main(int argc, char* argv[])
{
	unsigned int random_seed = 0;
	const unsigned int sample_size = 3000;
	unsigned int generated_number = random_seed % sample_size;
	unsigned int prime_number = 1;
	unsigned int increment = prime_number;
 
	bool test[sample_size] = {0};
 
	for(unsigned int iterator = 0; iterator < sample_size; ++iterator)
	{
		generated_number = (generated_number + increment) % sample_size;
		test[generated_number] = true;
 
		static bool displayOnce = true;
		if (displayOnce)
		{
			printf("Predictable Random Numbers:\n");
			displayOnce = false;
		}
 
		printf("%d ", generated_number);
	}
 
	for(unsigned int iterator = 0; iterator < sample_size; ++iterator)
	{
		if (!test[iterator])
		{
			static bool displayOnce = true;
			if (displayOnce)
			{
				printf("\nYou must have not used a prime number [ERROR]\n");
				displayOnce = false;
			}
			printf("%d ", iterator);
		}
	}
}

Example 2 (in C#)[edit]

using System;
using System.Collections.Generic;
using System.Text;
 
namespace PseudoRandomTest1
{
    class Program
    {
        static Boolean m_DisplayOnce = false;
 
        static void Main(string[] args)
        {
            const UInt32 random_seed = 0;
            const UInt32 sample_size = 3000;
            UInt32 generated_number = random_seed % sample_size;
            const UInt32 prime_number = 751;
            const UInt32 increment = prime_number;
 
            Boolean[] test = new Boolean[sample_size];
 
            m_DisplayOnce = true;
            for(UInt32 iterator = 0; iterator < sample_size; ++iterator)
            {
                generated_number = (generated_number + increment) % sample_size;
                test[generated_number] = true;
 
                if (m_DisplayOnce)
                {
                        Console.WriteLine("Predictable Random Numbers:");
                        m_DisplayOnce = false;
                }
 
                Console.Write("{0} ", generated_number);
            }
 
            m_DisplayOnce = true;
            for(UInt32 iterator = 0; iterator < sample_size; ++iterator)
            {
                if (!test[iterator])
                {
                    if (m_DisplayOnce)
                    {
                        Console.WriteLine();
                        Console.WriteLine("You must have not used a prime number [ERROR]");
                        m_DisplayOnce = false;
                    }
                    Console.Write("{0} ", iterator);
                }
            }
        }
    }
}

See also[edit]