31:[] 2f:{"title":"Shift-Register-Generator","cells":[{"id":0,"value":"# Shift-Register-Generator","pinned":false,"hidden":false,"mode":"md"},{"id":271,"value":"### A lightweight example of a pseudo-random numbers generator","pinned":false,"hidden":false,"mode":"md"},{"id":274,"value":"Starting with a seed (in our example 1010101010) we then shift the bits as following: ${tex`x_{k}=x_{k-p}`} XOR ${tex`x_{k-p+q}`} with ${tex`p=10`} and ${tex`q=3`}.","pinned":false,"hidden":false,"mode":"md"},{"id":217,"value":"viewof numberOfPoints = Inputs.range([100, 100000], {label: \"How many points should be generatet?\", value: 2046, step: 2})","pinned":false,"hidden":false,"mode":"ojs"},{"id":203,"value":"Shift-Register-Generator samples (${numPointsPlot})","pinned":false,"hidden":false,"mode":"md"},{"id":139,"value":"Plot.plot({\n grid: true,\n marks: [\n Plot.dot(plotPoints, {x: (num) => num[0], y: (num) => num[1], stroke: \"orange\"}),\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":205,"value":"Mersenne-Twister-Generator samples (${numPointsPlot})","pinned":false,"hidden":false,"mode":"md"},{"id":199,"value":"Plot.plot({\n grid: true,\n marks: [\n Plot.dot(randomPoints, {x: (num) => num[0], y: (num) => num[1], stroke: \"orange\"}),\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":250,"value":"Generate the next ${numberOfPoints} bits","pinned":false,"hidden":false,"mode":"md"},{"id":84,"value":"bits = {\n const allBits = initialBits.slice();\n const newBits = [];\n for (let i=initialBits.length-1; i < numberOfPoints; i++) {\n allBits.push(nextBit(i, allBits));\n newBits.push(nextBit(i, allBits));\n }\n return allBits\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":75,"value":"nextBit = (k, bits) => {\n return bits[k-p] ^ bits[k-p+q]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":276,"value":"// just a try with bit shifting...\ngenerateBits = (numBits, p=10, q=3, initialState=0b1010101010) => {\n let state = initialState;\n let bits = [];\n for (let i = 0; i < numBits; i++) {\n let nextBit = ((state >> (p-1)) ^ (state >> (p-q))) & 1;\n state = ((state << 1) | nextBit) & ((1 << p) - 1);\n bits.push(nextBit);\n }\n return bits;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"Convert these bits to 10-bit integers:","pinned":false,"hidden":false,"mode":"md"},{"id":121,"value":"naturalNumbers = {\n const naturalNumbers = [];\n for (let i=initialBits.length-1; i < bits.length; i++) {\n let naturalNumber = 0;\n for (let j=0; j < 10; j++) {\n naturalNumber += bits[i-j]*2**j\n }\n naturalNumbers.push(naturalNumber)\n }\n return naturalNumbers\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":255,"value":"And these integers to real numbers of range [0, 1)...","pinned":false,"hidden":false,"mode":"md"},{"id":128,"value":"rationalNumbers = naturalNumbers.map((num) => num/2**10)","pinned":true,"hidden":false,"mode":"ojs"},{"id":131,"value":"rationalRange = [d3.min(rationalNumbers), d3.max(rationalNumbers)]","pinned":true,"hidden":false,"mode":"ojs"},{"id":259,"value":"For this example with the initial binary 1010101010 (682) we get a period of 2046","pinned":false,"hidden":false,"mode":"md"},{"id":109,"value":"findPeriod(bits).split(\",\").length","pinned":true,"hidden":false,"mode":"ojs"},{"id":261,"value":"Create here some other pseudo-random numbers with the Mersenne-Twister-Generator to compare these two. Above you can see how much better this one is... ","pinned":false,"hidden":false,"mode":"md"},{"id":183,"value":"randomBits = {\n const rnd = new mt.default(parseInt(1010101010, 2));\n const generated = [];\n for (let i = 0; i < numberOfPoints-9; i++) generated.push(rnd.random() % 360);\n return generated;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":263,"value":"## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":142,"value":"// generating points for plot \nplotPoints = {\n const points = [];\n for(let i=0; i {\n let str = arr.join(',');\n let Z = calculateZArray(str);\n for (let i = 1; i < Z.length; ++i) {\n if (Z[i] + i === str.length) return arr.slice(0, i).join(',');\n }\n return null;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":156,"value":"calculateZArray = (str) => {\n let Z = Array(str.length).fill(0);\n let L = 0, R = 0;\n for (let i = 1; i < str.length; ++i) {\n if (i > R) {\n L = R = i;\n while (R < str.length && str[R - L] === str[R]) R++;\n Z[i] = R - L;\n R--;\n } else {\n let k = i - L;\n if (Z[k] < R - i + 1) Z[i] = Z[k];\n else {\n L = i;\n while (R < str.length && str[R - L] === str[R]) R++;\n Z[i] = R - L;\n R--;\n }\n }\n }\n return Z;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"q = 3","pinned":true,"hidden":false,"mode":"ojs"},{"id":28,"value":"p = 9","pinned":true,"hidden":false,"mode":"ojs"},{"id":68,"value":"initialBits = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0]","pinned":true,"hidden":false,"mode":"ojs"},{"id":193,"value":"randomPoints = {\n const points = [];\n for(let i=0; i