2d:null 2e:["$","title",null,{"children":"xorshift | Job van der Zwan | Observable"}] 33:T81c,md`# xorshift Yet another cheap prng https://en.wikipedia.org/wiki/Xorshift Commonly xorshift is used for integer randomness, but with either division or a bit of typed array trickery it can be used for floating point as well. It is reasonably fast, compared to the other options. On Firefox \`Math.random()\` is still faster, but on Chrome it \`xorshift\` manages to beat it by a *tiny* margin (on my machine at least - tested on Linux and an Android phone). Meanwhile, the typed array version is a *lot* faster in Chrome (\`Math.random()\` still wins on Firefox). Also worth noting: Chrome is almost ten times slower than Firefox here, so *if* your source of randomness is a bottleneck, then optimizing for the worst bottleneck (Chrome) might be worth it. Do proper measurements before doing premature optimizations though! Also, in this notebook I'm using a \`Float32Array\`, and only randomize the mantissa of this \`float32\` value. That means we have only 23 "bits of randomness". To compare, \`Math.random()\` returns a double, so a \`float64\` with a mantissa of 54 bits. In many situations those 23 bits of randomness are enough, but it's important to be aware of these limitations. For the sake of being "complete" I also wrote a [Float64Array version](https://observablehq.com/@jobleonard/xorshift64), but that appears slower than \`Math.random()\` under all circumnstances so far. Also it only works on [little endian platforms](https://observablehq.com/@jobleonard/endianness) for now (so if it produces gibberish on your mobile phone, it's probably due to it having a big endian processor). Others in this series: - [Linear Congruential Generator](https://observablehq.com/@fil/linear-congruential-generator), by [\`@fil\`](https://observablehq.com/@fil) - [Permuted Congruential Generator](https://observablehq.com/@jrus/permuted-congruential-generator), the fixed version of my port by [\`@jrus\`](https://observablehq.com/@jrus) - [xorwow](https://observablehq.com/@jobleonard/xorwow) - [xorshift64](https://observablehq.com/@jobleonard/xorshift64)`34:T449,xorShiftF32Cast = { // Try this out in the console: // const u = new Uint32Array(2); // const f = new Float32Array(u.buffer); // u[0] = 0b0111111100000000000000000000000; // u[1] = 0b1000000000000000000000000000000; // return { u, f }; // // --> Object { // u: Uint32Array(2) [1065353216, 1073741824] // f: Float32Array(2) [1, 2] // } // In other words: in the range [1.0, 2.0) of Float32 // we can use xorshift on the lower 23 bits to get // a uniform random distribution. Subtract one and we // get an fast approximation of uniform random in range [0, 1.0) // We use a typed array to "cast" between Uint32 and Float32 const u = new Uint32Array(1); const f = new Float32Array(u.buffer); let x = (Math.random() * 0x100000000) | 0; return function xorShiftF32() { // closures never inline captured variables, // hence this local variable to fix that let _x = x; _x ^= _x << 13; _x ^= _x >> 17; _x ^= _x << 5; u[0] = 0b111111100000000000000000000000 | (_x & 0x7fffff); x = _x; return f[0] - 1; }; }35:[] 31:{"id":"4771aa303dc3785d","slug":"xorshift","title":"xorshift","thumbnail":"698363f5425d787984081bd2b8a5d2fad2802addd29464d3d2aa1edddba23f9e","access_level":"public","create_time":"$D2020-11-04T22:25:45.867Z","update_time":"$D2021-12-17T13:23:52.501Z","view_time":null,"first_public_time":"$D2020-11-04T22:36:05.284Z","has_unpublished_edits":null,"fork":{"id":"9650a189d238d85c","slug":"linear-congruential-generator","title":"Linear congruential generator","owner":{"id":"da2a32154638c457","login":"fil","name":"Fil"}},"stars":2,"starred":false,"owner":{"type":"team","id":"3f83172cfde1e56a","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":"starter_2024"},"version":324,"publish_version":324,"role":null,"authored":false,"authors":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}],"members":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"xorshift","cells":[{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":146,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"Array.from({ length: 1000 }, xorShiftF32Cast)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"xorShiftF32Mul = {\n const eps = Math.pow(2, -32);\n const div = Math.pow(2, 32);\n let x = (Math.random() * 0x100000000) | 0;\n return function xorShiftMul() {\n // closures never inline captured variables,\n // hence this local variable to fix that\n let _x = x;\n _x ^= _x << 13;\n _x ^= _x >> 17;\n _x ^= _x << 5;\n x = _x;\n return (x >>> 0) * eps;\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":261,"value":"Array.from({ length: 1000 }, xorShiftF32Mul)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"// Since we're probably want to have lots of random values in typed arrays,\n// we might as well operate directly on said arrays\nxorShiftF32CastArray = {\n let x = (Math.random() * 0x100000000) | 0;\n return function xorShiftF32Array(f) {\n const u = new Uint32Array(f.buffer);\n let _x = x;\n for (let i = 0; i < f.length; i++) {\n _x ^= _x << 13;\n _x ^= _x >> 17;\n _x ^= _x << 5;\n u[i] = (_x & 0x7fffff) | 0b111111100000000000000000000000;\n f[i] -= 1;\n }\n x = _x;\n return f;\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":130,"value":"xorShiftF32CastArray(new Float32Array(1000))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":294,"value":"// Since we're probably want to have lots of random values in typed arrays,\n// we might as well operate directly on said arrays\nxorShiftF32MulArray = {\n const eps = Math.pow(2, -32);\n let x = (Math.random() * 0x100000000) | 0;\n return function xorShiftF32Array(f) {\n let _x = x;\n for (let i = 0; i < f.length; i++) {\n _x ^= _x << 13;\n _x ^= _x >> 17;\n _x ^= _x << 5;\n f[i] = (_x >>> 0) * eps;\n }\n x = _x;\n return f;\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":304,"value":"xorShiftF32MulArray(new Float32Array(1000))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":286,"value":"md`## Fill an array one element at a time`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":218,"value":"{\n const n = 1e7;\n const A = new Array(n).fill(0);\n let time = +new Date();\n for (let i = 0; i < n; i++) A[i] = Math.random();\n time = (+new Date() - time) / 1000;\n\n return md`${(n / 1e6 / time).toFixed(\n 1\n )} million pseudorandom numbers per second (individual calls to \\`Math.random\\`)`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"{\n const n = 1e7;\n const A = new Array(n).fill(0);\n\n let time = +new Date();\n for (let i = 0; i < n; i++) A[i] = xorShiftF32Cast();\n time = (+new Date() - time) / 1000;\n\n return md` ${(n / 1e6 / time).toFixed(\n 1\n )} million pseudorandom numbers per second (individual calls to \\`xorShiftF32Cast\\`)`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":267,"value":"{\n const n = 1e7;\n const A = new Array(n).fill(0);\n\n let time = +new Date();\n for (let i = 0; i < n; i++) A[i] = xorShiftF32Mul();\n time = (+new Date() - time) / 1000;\n\n return md` ${(n / 1e6 / time).toFixed(\n 1\n )} million pseudorandom numbers per second (individual calls to \\`xorShiftF32Mul\\`)`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":283,"value":"md`## Fill a typed array \"directly\"`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":246,"value":"{\n const n = 1e7;\n const A = new Float32Array(n);\n let time = +new Date();\n for (let i = 0; i < n; i++) A[i] = Math.random();\n time = (+new Date() - time) / 1000;\n\n return md`${(n / 1e6 / time).toFixed(\n 1\n )} million pseudorandom numbers per second (fill \\`Float32Array\\` with individual calls to \\`Math.random\\`)`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"{\n const n = 1e7;\n const A = new Float32Array(n);\n\n let time = +new Date();\n xorShiftF32CastArray(A);\n time = (+new Date() - time) / 1000;\n\n return md` ${(n / 1e6 / time).toFixed(\n 1\n )} million pseudorandom numbers per second (apply \\`xorShiftF32CastArray\\` to \\`Float32Array\\`)`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":300,"value":"{\n const n = 1e7;\n const A = new Float32Array(n);\n\n let time = +new Date();\n xorShiftF32MulArray(A);\n time = (+new Date() - time) / 1000;\n\n return md` ${(n / 1e6 / time).toFixed(\n 1\n )} million pseudorandom numbers per second (apply \\`xorShiftF32MulArray\\` to \\`Float32Array\\`)`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":314,"value":"{\n const n = 1e7;\n const A = [];\n for (let i = 0; i < n; i++) A[i] = 0;\n\n let time = +new Date();\n xorShiftF32MulArray(A);\n time = (+new Date() - time) / 1000;\n\n return md` ${(n / 1e6 / time).toFixed(\n 1\n )} million pseudorandom numbers per second (apply \\`xorShiftF32MulArray\\` to an Array)`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"{\n const height = 500,\n context = DOM.context2d(width, height);\n\n const randomVals = new Float32Array(width * 2);\n do {\n context.fillStyle = \"rgba(255,255,255,0.01)\";\n context.fillRect(0, 0, width, height);\n context.fillStyle = \"#000\";\n xorShiftF32CastArray(randomVals);\n for (let i = 0; i < width; i++)\n context.fillRect(\n width * randomVals[i * 2],\n height * randomVals[i * 2 + 1],\n 1,\n 1\n );\n yield context.canvas;\n } while (true);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"