Skip to content

Instantly share code, notes, and snippets.

@cogmission

cogmission/UniversalRandom.java

Last active September 21, 2016 15:54
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save cogmission/c4cb8feaba19595dae8ff964e18b05d0 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save cogmission/c4cb8feaba19595dae8ff964e18b05d0 to your computer and use it in GitHub Desktop.
Download ZIP
UniversalRandom Using George Marsaglia's elegant Xorshift (In Python and Java)
Raw
universal_random.py
'''
Created on Jul 31, 2016
@author: cogmission
'''
import numpy
import unittest
class UniversalRandom(object):
'''
classdocs
'''
def __init__(self, seed):
'''
Constructor
'''
self.seed = seed
self.uintType = "uint32"
def setSeed(self, seed):
self.seed = seed
def getSeed(self):
return self.seed
def rshift(self, val, n):
return val>>n if val >= 0 else (val+0x100000000)>>n
def _private_sampleWithPrintouts(self, choices, selectedIndices, collectedRandoms):
"""
Private method which is identical to the sample() method of this class.
This method is meant for testing of identical behavior with the Java
method of the same class.
Normal use would entail calling sample() instead of this method
"""
temp = set()
sampleSize = int(selectedIndices.size)
upperBound = len(choices)
for i in xrange(sampleSize):
randomIdx = self.nextInt(upperBound)
print "randomIdx: " + str(randomIdx)
collectedRandoms.append(randomIdx)
while(choices[randomIdx] in temp):
randomIdx = self.nextInt(upperBound)
print "randomIdx2: " + str(randomIdx)
collectedRandoms.append(randomIdx)
temp.add(choices[randomIdx])
selectedIndices.itemset(i, choices[randomIdx])
selectedIndices.sort()
return selectedIndices;
def sample(self, choices, selectedIndices):
"""
Returns a random, sorted, and unique list of the specified sample size of
selections from the specified list of choices.
"""
temp = set()
sampleSize = int(selectedIndices.size)
upperBound = len(choices)
for i in xrange(sampleSize):
randomIdx = self.nextInt(upperBound)
while(choices[randomIdx] in temp):
randomIdx = self.nextInt(upperBound)
temp.add(choices[randomIdx])
selectedIndices.itemset(i, choices[randomIdx])
selectedIndices.sort()
return selectedIndices;
def nextDouble(self):
nd = self.nextInt(10000)
retVal = nd * .0001
return retVal
def nextIntNB(self):
"""
Next int - no bounds.
"""
return self.next(32)
def nextInt(self, bound):
''' doc '''
if bound <= 0:
raise ValueError('bound must be positive')
r = self.next(31)
m = bound - 1
if (bound & m) == 0:
r = (bound * r) >> 31
else:
u = r
r = u % bound
while u - r + m < 0:
u = self.next(31)
return r
def next(self, nbits):
''' doc '''
x = self.seed & 0xffffffffffffffff #Preserve 64 bits
x ^= (x << 21) & 0xffffffffffffffff
x ^= self.rshift(x, 35) & 0xffffffffffffffff
x ^= (x << 4) & 0xffffffffffffffff
self.seed = x
x &= ((1 << nbits) - 1) & 0xffffffff #Preserve the integer bits
return x
if __name__ == '__main__':
random = UniversalRandom(42)
s = 2858730232218250
e = random.rshift(s, 35)
print "e = " + str(e)
x = random.nextInt(50)
print "x = " + str(x)
x = random.nextInt(50)
print "x = " + str(x)
x = random.nextInt(50)
print "x = " + str(x)
x = random.nextInt(50)
print "x = " + str(x)
x = random.nextInt(50)
print "x = " + str(x)
for i in xrange(0, 10):
o = random.nextInt(50)
print "x = " + str(o)
######################################
## Values Seen in Java ##
######################################
random = UniversalRandom(42)
for i in range(10):
o = random.nextDouble()
print "d = " + str(o)
'''
e = 83200
x = 0
x = 26
x = 14
x = 15
x = 38
x = 47
x = 13
x = 9
x = 15
x = 31
x = 6
x = 3
x = 0
x = 21
x = 45
d = 0.945
d = 0.2426
d = 0.5214
d = 0.0815
d = 0.0988
d = 0.5497
d = 0.4013
d = 0.4559
d = 0.5415
d = 0.2381
'''
# The "expected" values are the same as produced in Java
random = UniversalRandom(42)
choices = [1,2,3,4,5,6,7,8,9]
sampleSize = 6
selectedIndices = numpy.empty(sampleSize, dtype="uint32")
collectedRandoms = []
expectedSample = [1,4,6,7,8,9]
expectedRandoms = [0,0,0,5,7,3,0,6,3,6,5,7,8]
retVal = random._private_sampleWithPrintouts(choices, selectedIndices, collectedRandoms)
print "samples are equal ? " + str(retVal == expectedSample)
print "used randoms are equal ? " + str(collectedRandoms == expectedRandoms)
Raw
UniversalRandom.java
package org.numenta.nupic.util;
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import gnu.trove.list.array.TIntArrayList;
import gnu.trove.set.hash.TIntHashSet;
public class UniversalRandom extends Random {
/** serial version */
private static final long serialVersionUID = 1L;
private static final MathContext MATH_CONTEXT = new MathContext(9);
long seed;
static final String BadBound = "bound must be positive";
public UniversalRandom(long seed) {
this.seed = seed;
}
/**
* Sets the long value used as the initial seed
*
* @param seed the value with which to be initialized
*/
@Override
public void setSeed(long seed) {
this.seed = seed;
}
/**
* Returns the long value used as the initial seed
*
* @return the initial seed value
*/
public long getSeed() {
return seed;
}
private int[] sampleWithPrintout(TIntArrayList choices, int[] selectedIndices, List<Integer> collectedRandoms) {
TIntHashSet temp = new TIntHashSet();
int upperBound = choices.size();
for (int i = 0; i < selectedIndices.length; i++) {
int randomIdx = nextInt(upperBound);
System.out.println("randomIdx: " + randomIdx);
collectedRandoms.add(randomIdx);
while (temp.contains(choices.get(randomIdx))) {
randomIdx = nextInt(upperBound);
System.out.println("randomIdx2: " + randomIdx);
collectedRandoms.add(randomIdx);
}
temp.add(selectedIndices[i] = (choices.get(randomIdx)));
}
Arrays.sort(selectedIndices);
return selectedIndices;
}
public int[] sample(TIntArrayList choices, int[] selectedIndices) {
TIntHashSet temp = new TIntHashSet();
int upperBound = choices.size();
for (int i = 0; i < selectedIndices.length; i++) {
int randomIdx = nextInt(upperBound);
while (temp.contains(choices.get(randomIdx))) {
randomIdx = nextInt(upperBound);
}
temp.add(selectedIndices[i] = (choices.get(randomIdx)));
}
Arrays.sort(selectedIndices);
return selectedIndices;
}
@Override
public double nextDouble() {
int nd = nextInt(10000);
double retVal = new BigDecimal(nd * .0001d, MATH_CONTEXT).doubleValue();
return retVal;
}
@Override
public int nextInt() {
return next(32);
}
@Override
public int nextInt(int bound) {
if (bound <= 0)
throw new IllegalArgumentException(BadBound);
int r = next(31);
int m = bound - 1;
if ((bound & m) == 0) // i.e., bound is a power of 2
r = (int)((bound * (long)r) >> 31);
else {
for (int u = r;
u - (r = u % bound) + m < 0;
u = next(31))
;
}
return r;
}
/**
* Implementation of George Marsaglia's elegant Xorshift random generator
* 30% faster and better quality than the built-in java.util.random see also
* see http://www.javamex.com/tutorials/random_numbers/xorshift.shtml
*/
protected int next(int nbits) {
long x = seed;
x ^= (x << 21);
x ^= (x >>> 35);
x ^= (x << 4);
seed = x;
x &= ((1L << nbits) - 1);
return (int) x;
}
public static void main(String[] args) {
UniversalRandom random = new UniversalRandom(42);
long s = 2858730232218250L;
long e = (s >>> 35);
System.out.println("e = " + e);
int x = random.nextInt(50);
System.out.println("x = " + x);
x = random.nextInt(50);
System.out.println("x = " + x);
x = random.nextInt(50);
System.out.println("x = " + x);
x = random.nextInt(50);
System.out.println("x = " + x);
x = random.nextInt(50);
System.out.println("x = " + x);
for(int i = 0;i < 10;i++) {
int o = random.nextInt(50);
System.out.println("x = " + o);
}
random = new UniversalRandom(42);
for(int i = 0;i < 10;i++) {
double o = random.nextDouble();
System.out.println("d = " + o);
}
///////////////////////////////////
// Values Seen in Python //
///////////////////////////////////
/*
* e = 83200
x = 0
x = 26
x = 14
x = 15
x = 38
x = 47
x = 13
x = 9
x = 15
x = 31
x = 6
x = 3
x = 0
x = 21
x = 45
d = 0.945
d = 0.2426
d = 0.5214
d = 0.0815
d = 0.0988
d = 0.5497
d = 0.4013
d = 0.4559
d = 0.5415
d = 0.2381
*/
random = new UniversalRandom(42);
TIntArrayList choices = new TIntArrayList(new int[] { 1,2,3,4,5,6,7,8,9 });
int sampleSize = 6;
int[] selectedIndices = new int[sampleSize];
List<Integer> collectedRandoms = new ArrayList<>();
int[] expectedSample = {1,4,6,7,8,9};
List<Integer> expectedRandoms = Arrays.stream(new int[] {0,0,0,5,7,3,0,6,3,6,5,7,8}).boxed().collect(Collectors.toList());
random.sampleWithPrintout(choices, selectedIndices, collectedRandoms);
System.out.println("samples are equal ? " + Arrays.equals(expectedSample, selectedIndices));
System.out.println("used randoms are equal ? " + collectedRandoms.equals(expectedRandoms));
}
}
@cogmission
Copy link
Author

cogmission commented Aug 4, 2016

Added ability to set the seed value after construction.

@cogmission
Copy link
Author

cogmission commented Aug 5, 2016

Added universal nextDouble() method to both

@cogmission
Copy link
Author

cogmission commented Aug 10, 2016

  • Added universal sample() method to both
  • Changed Java version of compatibility with the "fast" mode of Python via nextX()
  • Added Optional mode compatibility_mode argument to the Python UniversalRandom constructor which will then afford the option of using the fastest mode (compatibility_mode == False), or the compatible mode (compatibility_mode == True) which calls a different method which emulates Java overflows so that their outputs are identical.

@cogmission
Copy link
Author

cogmission commented Aug 11, 2016

Added tweak to plain java: nextInt(), python: nextIntNB() calls to internally call the bounded method with Java's maximum integer value.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment