/* Copyright 2010 Aaron J. Radke Licensed 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 cc.drx import com.github.KdotJPG.OpenSimplexNoise //TODO sometime this would be fun to re-write as scala, if available to scala then it would have access to scala-js, scala-native and no deps object Rand{ implicit val defaultDrxRand:Rand = Rand(0) //look here inside the Rand object for an implicit Rand if non is provided } case class Rand(seed:Long=scala.util.Random.nextLong()){ //--seeds private val r = new scala.util.Random(seed) //this seed is based on Java's LCG //--distributions def uniform(a:Double,b:Double) = a + (b-a)*r.nextDouble() def uniform = r.nextDouble() def uniform(a:Double) = a*r.nextDouble() def uniform(a:Int):Int = r.nextInt(a+1) def uniform(a:Int,b:Int):Int = a + r.nextInt(b+1-a) def normal:Double = r.nextGaussian() def normal(m:Double):Double = m + r.nextGaussian() def normal(m:Double,s:Double):Double = m + s*r.nextGaussian() //--tests /** if( rand(1 outOf 100) )*/ def apply(rat:Ratio):Boolean = uniform(0d,1d) < rat.toDouble //--types def double:Double = r.nextDouble() def long:Long = r.nextLong() def int:Int = r.nextInt() def bool:Boolean = r.nextBoolean() // def flip:Boolean = r.nextBoolean //--noise private lazy val openSimplexNoise = new OpenSimplexNoise(seed) //this requires a java src file that would be nice if ported to scala def noise(x:Double,y:Double):Double = openSimplexNoise.eval(x,y) def noise(x:Double,y:Double,z:Double):Double = openSimplexNoise.eval(x,y,z) def noise(x:Double,y:Double,z:Double,w:Double):Double = openSimplexNoise.eval(x,y,z,w) def noise(v:Vec):Double = openSimplexNoise.eval(v.x,v.y,v.z) def noise(v:Vec,w:Double):Double = openSimplexNoise.eval(v.x,v.y,v.z,w) //--array sampling def apply[A](xs:IndexedSeq[A]):A = xs(r nextInt xs.size) //TODO test def get[A](xs:IndexedSeq[A]):Option[A] = if(xs.isEmpty) None else Some(apply(xs)) //--array iteration without repeat def iterate[A](xs:IndexedSeq[A]):Iterator[A] = new LSFRIterator(xs,r nextInt xs.size) //TODO test the lsfr iterator //--in memory array shuffling //import scala.language.higherKinds //import scala.collection.generic.CanBuildFrom ////note this could be an IterableOnce to be more generic since the builder does some work //def shuffle[T, CC[X] <: Iterable[X]](xs: CC[T])(implicit bf: CanBuildFrom[CC[T], T, CC[T]]): CC[T] = r shuffle xs // def shuffle[A](xs: Array[A]): Array[A] = java.util.Random.shuffle(xs) def shuffle[A](xs: Iterable[A]): Iterable[A] = r.shuffle(xs) } /** See LSFR for linear feedback shift register is a pretty sweet non-repeating random number generator*/ class LSFRIterable[A](xs:IndexedSeq[A],i0:Int) extends Iterable[A]{ def iterator:Iterator[A] = new LSFRIterator(xs,i0) } /** See LSFR for linear feedback shift register is a pretty sweet non-repeating random number generator*/ class LSFRIterator[A](xs:IndexedSeq[A],i0:Int) extends Iterator[A]{ private val N = xs.size private var i = 0 //note lsfr is 1 based so need to subtract this 1 for scala indexes val lsfr = LSFR(xs.size,i0+1) def hasNext:Boolean = i < N def next():A = { i = i + 1 xs(lsfr.next() - 1) } } //---------------- /**linear feedback shift register is a pretty sweet non-repeating random number generator * https://www.wikiwand.com/en/Linear-feedback_shift_register * */ object LSFR{ /**feedback polynomial taps * https://www.wikiwand.com/en/Linear-feedback_shift_register * http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf * */ private lazy val tap32 = "0;0;2,1;3,2;4,3;5,3;6,5;7,6;8,6,5,4;9,5;10,7;11,9;12,6,4,1;13,4,3,1;14,5,3,1;15,14;16,15,13,4;17,14;18,11;19,6,2,1;20,17;21,19;22,21;23,18;24,23,22,17;25,22;26,6,2,1;27,5,2,1;28,25;29,27;30,6,4,1;31,28;32,22,2,1" private lazy val tap64 = "33,20;34,27,2,1;35,33;36,25;37,5,4,3,2,1;38,6,5,1;39,35;40,38,21,19;41,38;42,41,20,19;43,42,38,37;44,43,18,17;45,44,42,41;46,45,26,25;47,42;48,47,21,20;49,40;50,49,24,23;51,50,36,35;52,49;53,52,38,37;54,53,18,17;55,31;56,55,35,34;57,50;58,39;59,58,38,37;60,59;61,60,46,45;62,61,6,5;63,62;64,63,61,60;65,47" //believe it or not but the embedded string version compiles to a much smaller than a pre-built syntax tree private def tapParse(spec:String):Array[Array[Int]] = spec.split(';').map{taps => taps split ',' map {_.toInt} } private lazy val tapLookup32:Array[Array[Int]] = tapParse(tap32) private lazy val tapLookup64:Array[Array[Int]] = tapLookup32 ++ tapParse(tap64) // def tapLookup(nBit:Int):Array[Int] = if(nBit <= 32) tapLookup32(nBit) else tapLookup64(nBit) // def nBit(period:Int):Int = (period+1).log(2).ceil.toInt /**construct a unique LSFR for the range of n*/ //TODO consider unsigned integer effects def apply(n:Int, x0:Int=1):LSFR[Int] = { // val x0 = 1 //TODO use random starting seed val nBit = (n+1).log(2).ceil.toInt val taps = tapLookup32(nBit) // Macro.pp(nBit,taps.toList,n) new LSFR32(x0, taps, nBit,n) } } trait LSFR[A]{ def next():A } class LSFR32(x0:Int, taps:Array[Int], nBit:Int, n:Int) extends LSFR[Int]{ //note: these require checks are only evaluated on construction (not generation) require(x0 != 0, "seed can not be zero in an LSFR") require(taps.size >= 0, "feedback polynomial taps not defiend") require(nBit > 1, "more bits required to provide shifts") private var x = x0 @tailrec final def next():Int = { //Fibonacci form val b = taps.foldLeft(0){case (a,i) => a ^ (x >>> (nBit-i))} & 1 //xor phase x = (x >>> 1) | (b << (nBit-1)) if(x <= n) x else next() //index here is 1 based since LSFR does not work for zero } } /**the capability of a 64bit LSFR is here but most indexes on the JVM are 32bit*/ class LSFR64(x0:Long, taps:Array[Long], nBit:Int, n:Long) extends LSFR[Long]{ //note: these require checks are only evaluated on construction (not generation) require(x0 != 0, "seed can not be zero in an LSFR") require(taps.size >= 0, "feedback polynomial taps not defiend") require(nBit > 1, "more bits required to provide shifts") private var x = x0 @tailrec final def next():Long = { //Fibonacci form val b = taps.foldLeft(0L){case (a,i) => a ^ (x >>> (nBit-i))} & 1 //xor phase x = (x >>> 1) | (b << (nBit-1)) if(x <= n) x else next() //index here is 1 based since LSFR does not work for zero } } object Marsaglia32{ def apply(x0:Int=Date.ms.toInt):Marsaglia32 = new Marsaglia32(Array.fill(6){x0}) } // https://github.com/non/spire/blob/master/core/shared/src/main/scala/spire/random/rng/Marsaglia32a6.scala class Marsaglia32(x0:Array[Int]){ require(x0.size == 6, "this marsaglia requires a total of 6 integers") private val x:Array[Int] = x0 def next():Int = { val t = x(0) ^ (x(0) >>> 2) //xor x(0) = x(1); x(1) = x(2); x(2) = x(3); x(3) = x(4) //shifts x(4) = x(4) ^ (x(4) << 4) ^ (t ^ (t << 1)) //xor shifts x(5) = x(5) + 362437 //d += x(4) + x(5) //d + v } } //---------------- // https://www.wikiwand.com/en/Linear_congruential_generator trait LCG //linear congruent generator //java & posix rand48 case class Rand48(x0:Long) extends LCG { //--constants val m:Long = 2**48 - 1 //modulus val a:Long = 25214903917L //multiplier val c:Long = 11 //increment //--vars private var x:Long = (x0 ^ a) & m //seed masked with multiplier //--methods def next():Int = { x = (a*x + c) & m //for the special case of m=111111111111b, & is faster and the same as % (x >>> 16).toInt //output 32bits from 48 to 16 } }