13 ms·

A 32-bit LFSR generates a sequence of bits with period 2^32-1; what you really want is a Lehmer-like generator using arithmetic in GF(2^32).

by pbsd 13y ago

tptacek 13y ago
You mathematicians, with your... understanding of the basic mathematics behind things we developers already use every day, you all think you're better than us, don't you? DON'T YOU?! Can't I just be left to be impressed by a direct use of the math behind a crappy textbook random number generator in peace? -.-
- pbsd 13y ago
  I'm not 100% sure if that was tongue-in-cheek or not, so I'll clarify: I was disagreeing with aortega. This is not a typical PRNG, where the seed generally marks the initial point of the same sequence. Choosing a random generator matters, because we want a different permutation every time, not simply a different starting point. It is akin to running a block cipher in OFB mode with a different key each time. What they are doing modulo 2^32 + 15 is IMO the simplest way to achieve that goal. Yes, you could do it without overflowing 2^32 using a binary field; you could also cook your own mini block-cipher. But that increases the complexity of the code and is not really faster everywhere.
  - tptacek 13y ago
    It was 100% tongue-in-cheek, but I'm happy to be extracting even more information from you by having my poor attempts at humor misconstrued. :)
  - aortega 13y ago
    >Choosing a random generator matters, because we want a different permutation every time, not simply a different starting point. Ah thanks, now it makes more sense, I knew I was missing something. What about choosing different prime polys for a galois lfsr? I believe you will get the same result.
    - aortega 13y ago
      Also you could XOR the LFSR output with any number to get a different permutation each time.
tga_d 13y ago
What does "GF(2^32)" mean in this context?
- pbsd 13y ago
  It's the finite field with 2^32 elements. There are several equivalent representations, but we typically work with it as the polynomials with coefficients modulo 2 modulo an irreducible polynomial of degree 32, e.g., x^32 + x^7 + x^3 + x^2 + 1. For more, see [1]. [1] https://en.wikipedia.org/wiki/Finite_field_arithmetic https://en.wikipedia.org/wiki/Finite_field_arithmetic

A 32-bit LFSR generates a sequence of bits with period 2^32-1; what you really want is a Lehmer-like generator using arithmetic in GF(2^32).

by pbsd 13y ago

A 32-bit LFSR generates a sequence of bits with period 2^32-1; what you really want is a Lehmer-like generator using arithmetic in GF(2^32).

tptacek 13y ago

You mathematicians, with your... understanding of the basic mathematics behind things we developers already use every day, you all think you're better than us, don't you? DON'T YOU?! Can't I just be left to be impressed by a direct use of the math behind a crappy textbook random number generator in peace? -.-

pbsd 13y ago
I'm not 100% sure if that was tongue-in-cheek or not, so I'll clarify: I was disagreeing with aortega. This is not a typical PRNG, where the seed generally marks the initial point of the same sequence. Choosing a random generator matters, because we want a different permutation every time, not simply a different starting point. It is akin to running a block cipher in OFB mode with a different key each time. What they are doing modulo 2^32 + 15 is IMO the simplest way to achieve that goal. Yes, you could do it without overflowing 2^32 using a binary field; you could also cook your own mini block-cipher. But that increases the complexity of the code and is not really faster everywhere.
- tptacek 13y ago
  It was 100% tongue-in-cheek, but I'm happy to be extracting even more information from you by having my poor attempts at humor misconstrued. :)
- aortega 13y ago
  >Choosing a random generator matters, because we want a different permutation every time, not simply a different starting point. Ah thanks, now it makes more sense, I knew I was missing something. What about choosing different prime polys for a galois lfsr? I believe you will get the same result.
  - aortega 13y ago
    Also you could XOR the LFSR output with any number to get a different permutation each time.

tga_d 13y ago

What does "GF(2^32)" mean in this context?

pbsd 13y ago
It's the finite field with 2^32 elements. There are several equivalent representations, but we typically work with it as the polynomials with coefficients modulo 2 modulo an irreducible polynomial of degree 32, e.g., x^32 + x^7 + x^3 + x^2 + 1. For more, see [1]. [1] https://en.wikipedia.org/wiki/Finite_field_arithmetic https://en.wikipedia.org/wiki/Finite_field_arithmetic