Fork me on GitHub

Categories


Tags



Xorshift based pseudo random

This paper Xorshift RNGs, July 2003, Marsaglia, George was inspire me to create another kind of Xorshift based without static initial.

The basic concept is:

Implementation

Implement in Python

import random

seed = random.randint(0x55555555, 0xffffffff)


def rnd():
    global seed
    x = 0
    for i in range(32):
        if (seed >> i) & 1:
            x ^= seed >> i
        else:
            x ^= seed << i
    x = 0xffffffff & x
    seed = x
    return x


for i in range(1000):
    print rnd()

Implement in JavaScript:

const crypto = require('crypto');

//Generate seed randomBytes
var seed = crypto.randomBytes(4).readUInt32LE(0);

//XorShift based PRNG
function rnd(){
    var x = 0, i;
    for(i = 0; i < 32; i++){
        //Shift right if [i th] bit is equal to 1, otherwise shift letf
        x ^= ((seed >> i) & 1) ? seed >> i : seed << i;
    }
    return seed = x >>> 0;
}

for(let i = 0; i < 1000; i++){
  process.stdout.write(`${i}\n`)
}

Implement in C

#include <stdio.h>
#include <time.h>

unsigned int seed;

unsigned int rnd(){
    unsigned int x = 0, i;
    for(i = 0; i < 32; i++){
        x ^= ((seed >> i) & 1) ? seed >> i : seed << i;
    }
    return seed = x;
}

int main(){
    time_t tsec;
    int i = 0;
    tsec = time(NULL);
    seed = (unsigned int)tsec;
    for(;i < 1000; i++) printf("%u\n", rnd());
    return 0;
}

Test:

gcc test.c -o test && chmod a+x test && ./test

I++ and I-- which is faster with array operator?

My friend gave me a link to video on Youtube why i-- for loop is faster than i++ with arrays in JavaScript. The guy who was create this video is some kind of dumb ass. He's not event know how does Node.JS or Javascript work.

Let repeat his experiment

I wrote a simple code with i++ then append i in to an Array:

let a = [];
let s = Date.now()
for (let i = 0; i < 10000000; i++) {
  a.push(i);
}
console.log('I++ cost:', Date.now() - s, 'μs');

Result:

I++ cost: 175 μs

Let try the same with i--:

let b = [];
let c = Date.now()
for (let i = 10000000; i > 0; i--) {
  b.push(i);
}
console.log('I-- cost:', Date.now() - c, 'μs');

Result:

I-- cost: 175 μs

Wow, it's the same, why the hell it happened?.

Let repeat the dumb ass experiment

let b = [];
let c = Date.now()
for (let i = 10000000; i > 0; i--) {
  b.push(i);
}
console.log('I-- cost:', Date.now() - c, 'μs');

let a = [];
let s = Date.now()
for (let i = 0; i < 10000000; i++) {
  a.push(i);
}
console.log('I++ cost:', Date.now() - s, 'μs');

Result:

I-- cost: 197 μs
I++ cost: 202 μs

The result shown, I-- quite faster than I++ when I let it on the top then let do in reverse.

let a = [];
let s = Date.now()
for (let i = 0; i < 10000000; i++) {
  a.push(i);
}
console.log('I++ cost:', Date.now() - s, 'μs');

let b = [];
let c = Date.now()
for (let i = 10000000; i > 0; i--) {
  b.push(i);
}
console.log('I-- cost:', Date.now() - c, 'μs');

Result:

I++ cost: 195 μs
I-- cost: 205 μs

Oh! see, V8 Engine have some kind pre-processing for initial code on the top. That's why this dumb ass orbserve and do stupid experiment.