Paste P1415

# (An Untitled Masterwork)ActivePublicActions

Authored by seirl on Aug 4 2022, 11:44 PM.
Tags
None
Subscribers
None
 package org.softwareheritage.graph.utils; import it.unimi.dsi.big.webgraph.LazyLongIterator; import java.util.Random; /** A Linear Feedback Shift Register * * Generates a random uniform permutation of [0, n] as a *stream* that takes O(1) space. * Because the entire state is a single long integer, the order for a given number of bits is deterministic. * * https://en.wikipedia.org/wiki/Linear-feedback_shift_register * https://stackoverflow.com/a/32193751 * https://www.uobabylon.edu.iq/eprints/paper_1_17528_649.pdf * http://users.ece.cmu.edu/~koopman/lfsr/ * https://docs.xilinx.com/v/u/en-US/xapp052 */ public class LinearFeedbackShiftRegister implements LazyLongIterator { private final long n; private long state; private final int numBits; public LinearFeedbackShiftRegister(long n, long seed) { if (n <= 0) { throw new IllegalArgumentException("n must be >= 0"); } this.n = n; this.state = (seed % n) + 1; this.numBits = ((int) (Math.log(n) / Math.log(2))) + 1; } public LinearFeedbackShiftRegister(long n) { this(n, (new Random()).nextLong()); } @Override public long nextLong() { do { long bits = state; for (int s : SHIFT_AMT[numBits]) { bits ^= (state >> s); } state = ((state >> 1) | ((bits & 1) << (numBits - 1))); } while (state > n); return state - 1; } @Override public long skip(long l) { long i = 0; while (i < l && nextLong() != -1) i++; return i; } /** Maximal Length LFSR Feedback Terms (coefficients of primitive polynomials) for each bit length */ private static final int[][] SHIFT_AMT = new int[][] { // Taps taken from https://docs.xilinx.com/v/u/en-US/xapp052 // For each k, numBits - k is the coefficient of the primitive polynomial. numBits is also a coefficient. // Example: for numBits = 16, the array contains 1, 3, 12, which means the coefficients are: // {16, 16 - 1, 16 - 3, 16 - 12} = {16, 15, 13, 4} // // p = [l.strip().split() for l in open('lol').readlines()] // p = [(int(l[0]), list(map(int, l[1].split(',')))) for l in p] // p = [[l[0] - x for x in l[1]] for l in p] new int[]{}, new int[]{1}, new int[]{1}, new int[]{1}, new int[]{1}, new int[]{2}, new int[]{1}, new int[]{1}, new int[]{2, 3, 4}, new int[]{4}, new int[]{3}, new int[]{2}, new int[]{6, 8, 11}, new int[]{9, 10, 12}, new int[]{9, 11, 13}, new int[]{1}, new int[]{1, 3, 12}, new int[]{3}, new int[]{7}, new int[]{13, 17, 18}, new int[]{3}, new int[]{2}, new int[]{1}, new int[]{5}, new int[]{1, 2, 7}, new int[]{3}, new int[]{20, 24, 25}, new int[]{22, 25, 26}, new int[]{3}, new int[]{2}, new int[]{24, 26, 29}, new int[]{3}, new int[]{10, 30, 31}, new int[]{13}, new int[]{7, 32, 33}, new int[]{2}, new int[]{11}, new int[]{32, 33, 34, 35, 36}, new int[]{32, 33, 37}, new int[]{4}, new int[]{2, 19, 21}, new int[]{3}, new int[]{1, 22, 23}, new int[]{1, 5, 6}, new int[]{1, 26, 27}, new int[]{1, 3, 4}, new int[]{1, 20, 21}, new int[]{5}, new int[]{1, 27, 28}, new int[]{9}, new int[]{1, 26, 27}, new int[]{1, 15, 16}, new int[]{3}, new int[]{1, 15, 16}, new int[]{1, 36, 37}, new int[]{24}, new int[]{1, 21, 22}, new int[]{7}, new int[]{19}, new int[]{1, 21, 22}, new int[]{1}, new int[]{1, 15, 16}, new int[]{1, 56, 57}, new int[]{1}, new int[]{1, 3, 4}, }; }