2d:null 2e:["$","title",null,{"children":"xorwow | Job van der Zwan | Observable"}] 33:T53e,md`# xorwow And yet another cheap prng, this one being a variant of xorshift: > *Marsaglia suggested scrambling the output by combining it with a simple additive counter modulo ${tex`2^{32}`} (which he calls a "Weyl sequence" after Weyl's equidistribution theorem). This also increases the period by a factor of ${tex`2^{32}`}, to ${tex`2^{192} - 2^{32}`}* https://en.wikipedia.org/wiki/Xorshift#xorwow Also, I'll repeat my warning from last time: > *It should be noted that 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, which would give us 54 bits of randomness.* > > *In many situations these 23 bits of randomness are enough, but it's important to be aware of these limitations.* 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) - [xorshift](https://observablehq.com/@jobleonard/xorshift) - [xorshift64](https://observablehq.com/@jobleonard/xorshift64)`34:T4c9,xorwowF32 = { // 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 a float32 value // we can use an integer PRNG and write the lower 23 bits to the // mantissa to get a uniform random distribution. Subtract one and // we get a 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 a = (Math.random() * 0x100000000) | 0, b = 0 | 0, c = 0 | 0, d = 0 | 0, e = 0 | 0, counter = 0 | 0; return function xorwowF32() { let t = e, s = a; e = d; d = c; c = b; b = a; t ^= t >> 2; t ^= t << 1; t ^= s ^ (s << 4); a = t; counter = (counter + 362437) & 0xFFFFFFFF; u[0] = 0b111111100000000000000000000000 | ((t + counter) & 0x7fffff); return f[0] - 1; }; }35:[] 31:{"id":"788c522b34066b57","slug":"xorwow","title":"xorwow","thumbnail":"ce90e6883c278a38e00459da85bf0a8b82b60b16b9c309d15d80f88ff4149423","access_level":"public","create_time":"$D2020-11-05T09:28:56.948Z","update_time":"$D2021-12-17T13:10:42.863Z","view_time":null,"first_public_time":"$D2020-11-05T09:55:07.020Z","has_unpublished_edits":null,"fork":{"id":"4771aa303dc3785d","slug":"xorshift","title":"xorshift","owner":{"id":"3f83172cfde1e56a","login":"jobleonard","name":"Job van der Zwan"}},"stars":1,"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":228,"publish_version":228,"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":1,"collection":null,"type":"notebook","body":{"title":"xorwow","cells":[{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"md`The C version of the algorithm, taken from the Wikipedia article on xorshift linked above:\n\n\\`\\`\\`c\n#include \n\nstruct xorwow_state {\n uint32_t a, b, c, d, e;\n uint32_t counter;\n};\n\n/* The state array must be initialized to not be all zero in the first four words */\nuint32_t xorwow(struct xorwow_state *state)\n{\n /* Algorithm \"xorwow\" from p. 5 of Marsaglia, \"Xorshift RNGs\" */\n uint32_t t = state->e;\n uint32_t s = state->a;\n state->e = state->d;\n state->d = state->c;\n state->c = state->b;\n state->b = s;\n t ^= t >> 2;\n t ^= t << 1;\n t ^= s ^ (s << 4);\n state->a = t;\n state->counter += 362437;\n return t + state->counter;\n}\n\\`\\`\\`\n`","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 }, xorwowF32)","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\nxorwowF32Array = {\n let a = (Math.random() * 0x100000000) | 0,\n b = 0 | 0,\n c = 0 | 0,\n d = 0 | 0,\n e = 0 | 0,\n counter = 0 | 0;\n return function xorwowF32Array(f) {\n const u = new Uint32Array(f.buffer);\n for (let i = 0; i < f.length; i++) {\n let t = e,\n s = a;\n e = d;\n d = c;\n c = b;\n b = a;\n t ^= t >> 2;\n t ^= t << 1;\n t ^= s ^ (s << 4);\n a = t;\n counter = (counter + 362437) & 0xFFFFFFFF;\n u[i] = 0b111111100000000000000000000000 | ((t + counter) & 0x7fffff);\n f[i] -= 1;\n }\n return f;\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":130,"value":"xorwowF32Array(new Float32Array(1000))","pinned":true,"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] = xorwowF32();\n time = (+new Date() - time) / 1000;\n\n return md`${(n / 1e6 / time).toFixed(\n 1\n )} million pseudorandom numbers per second (individual calls)`;\n}","pinned":true,"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 xorwowF32Array(A);\n time = (+new Date() - time) / 1000;\n\n return md`${(n / 1e6 / time).toFixed(\n 1\n )} million pseudorandom numbers per second`;\n}","pinned":true,"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 xorwowF32Array(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"