Commits

Kenneth Jørgensen committed 1ea7cc3 Draft

Implemented linear congruential generator with tests.

Comments (0)

Files changed (7)

 
 	grunt.registerTask("jessie", "Runs Jasmine specs through Jessie.", function() {
 		done = this.async();
-		command = "./node_modules/jessie/bin/jessie spec"
+		command = "./node_modules/jessie/bin/jessie build/spec"
 		exec(command, function(err, stdout, stderr) {
 			console.log(stdout);
 			if (err) {
 {
 	"fullname": "tovikov",
 	"name": "tovikov",
-	"version": "0.0.1-dev",
+	"version": "0.1.0",
 	"description": "Random library.",
 	"keywords": [
-		"random", "prng"
+		"random", "prng",
+		"lcg", "linear-congruential"
 	],
 	"homepage": "https://bitbucket.org/kennethjor/tovikov",
 	"bugs": "https://bitbucket.org/kennethjor/tovikov/issues",
 		"coffee-script": "~ 1.4.0",
 		"grunt-contrib-coffee": "~ 0.3.2",
 		"jessie": "~ 0.4.2",
-		"sinon": "~ 1.5.2"
+		"sinon": "~ 1.5.2",
+		"underscore": "~ 1.4.3"
 	}
 }

spec/GeneratorSpec.coffee

-sinon = require "sinon"
-Route = require "../src/Generator"
+_ = require "underscore"
 
-describe "Generator", ->
-	it "should work", ->
-	expect(true).toBe true
+Generator = require "../src/Generator"
+generators = require "../src/generators"
+
+SEED_INT = 42
+SEED_STRING = "MGtR70PzwoHNx2id70cjM9VQMKof7W3y4lvpfYZQbs"
+nextMethods = []
+for own name, func of Generator.prototype
+	unless name.substring(0, 4) is "next" then continue
+	nextMethods.push name
+
+describe "generators -", ->
+	for own name, generator of generators
+		describe name, ->
+#			gen = new generator()
+#			for i in [0..100]
+#				console.log gen.nextDouble()
+#				console.log gen.nextIntegerRange(0, 100)
+
+			it "should extend Generator", ->
+				gen = new generator()
+				expect(gen instanceof Generator).toBeTruthy()
+
+			it "should should accept integer seeds and generate different numbers", ->
+				gen = new generator(SEED_INT)
+				expect(gen.nextDouble()).not.toBe gen.nextDouble()
+
+			#			it "should should accept string seeds and generate different numbers", ->
+			#				gen = new generator(SEED_STRING)
+			#				expect(gen.nextDouble()).not.toBe gen.nextDouble()
+
+			it "nextDouble() should return number inside bounds", ->
+				gen = new generator()
+				for i in [0..1000]
+					v = gen.nextDouble()
+					expect(v).toBeLessThan 1
+					expect(v).toBeGreaterThan 0
+
+			it "nextDoubleRange() should return number inside bounds", ->
+				gen = new generator()
+				for i in [0..1000]
+					v = gen.nextDoubleRange 10, 20
+					expect(v).toBeLessThan 20
+					expect(v).toBeGreaterThan 10
+
+			it "nextIntegerRange() should return number inside bounds and have decent coverage", ->
+				gen = new generator()
+				vals = []
+				for i in [0..1000]
+					v = gen.nextIntegerRange 10, 20
+					vals.push v
+					expect(v).toBeLessThan 20+1
+					expect(v).toBeGreaterThan 10-1
+				vals = _.uniq vals
+#				console.log name, "nextBool", vals.join ","
+				expect(vals.length).toBe 11
+
+			it "nextArray() should return elements", ->
+				gen = new generator()
+				expect(gen.nextArray ["test"]).toBe "test"
+
+			it "nextBool() should return booleans", ->
+				gen = new generator()
+				bools = [0,0]
+				for i in [0..1000]
+					v = gen.nextBool()
+					expect(_.isBoolean(v)).toBeTruthy()
+					if v is true
+						bools[0]++
+					else
+						bools[1]++
+				expect(bools[0]).not.toBe 0
+				expect(bools[1]).not.toBe 0
+#				console.log name, "nextBool", bools.join ","
+
+			it "should produce repeatable sequences in serial, to ensure no state is left over", ->
+				gen1 = new generator()
+				seq1 = ""
+				for i in [0..100]
+					seq1 += gen1.nextIntegerRange 0, 9
+				gen2 = new generator()
+				seq2 = ""
+				for i in [0..100]
+					seq2 += gen2.nextIntegerRange 0, 9
+				expect(seq1).toBe seq2
+
+			it "should produce repeatable sequences in serial, to ensure no state is shared", ->
+				gen1 = new generator()
+				gen2 = new generator()
+				seq1 = ""
+				seq2 = ""
+				for i in [0..100]
+					seq1 += gen1.nextIntegerRange 0, 9
+					seq2 += gen2.nextIntegerRange 0, 9
+				expect(seq1).toBe seq2
+
+			it "should produce repeatable sequences after a reseed, to ensure all state is reset", ->
+				gen = new generator SEED_INT
+				seq1 = ""
+				for i in [0..100]
+					seq1 += gen.nextIntegerRange 0, 9
+				gen.setSeed SEED_INT
+				seq2 = ""
+				for i in [0..100]
+					seq2 += gen.nextIntegerRange 0, 9
+				expect(seq1).toBe seq2

src/Generator.coffee

 	# When `prng` is called it should create an object with a `nextDouble()` method.
 	# This method should return random doubles between 0 and 1 based on the supplied seed.
 	# If a different method is required, a simple wrapper can be written.
-	constructor: (@prng, seed) ->
+	constructor: (@prng, seed=1) ->
 		@setSeed seed
 
 	# Reseeds the generator.
 		return (max - min) * @nextDouble() + min
 
 	# Returns a random integer between `min` and `max`.
-	nextIntegerRange: ->
-		return round(@nextDoubleRange min, max)
+	nextIntegerRange: (min, max) ->
+		return round @nextDoubleRange(min, max)
 
 	# Returns a random element from an array.
 	nextArray: (arr) ->
 
 	# Return either true or false.
 	nextBool: ->
-		return true if @nextDouble < 0.5
+		return true if @nextDouble() < 0.5
 		return false

src/generators/LinearCongruential.coffee

+Generator = require "../Generator"
+
+# Linear congruential PRNG.
+# http://en.wikipedia.org/wiki/Linear_congruential_generator
+# LCGs provide good randomness, but they are not suited for crypto.
+
+# glibc
+M = 0x80000000
+A = 1103515245
+C = 12345
+
+module.exports = class LinearCongruential extends Generator
+	constructor: (seed) ->
+		super undefined, seed
+
+	setSeed: (seed) ->
+		# Convert to int
+		# Ensure positive
+		seed = seed & 0x7fffffff
+		# Create nextDouble()
+		@nextDouble = do (seed) ->
+			return ->
+				seed = (A * ( seed ) + C) % M
+				return seed / M
+		# Init
+		for i in [0..99]
+			@nextDouble()

src/generators/index.coffee

+module.exports =
+	LinearCongruential: require "./LinearCongruential"
 	"fullname": "namesrandom",
 	"name": "namedrandom",
 	"private": true,
-	"version": "0.0.1-dev",
+	"version": "0.1.0",
 	"description": "Random library.",
 	"keywords": [],
 	"homepage": "https://bitbucket.org/kennethjor/namedrandom",