Simple function to generate random number sequence without knowing previous number but know current index (no variable assignment)?

Question

Is there any (simple) random generation function that can work without variable assignment? Most functions I read look like this current = next(current). However currently I have a restriction (from SQLite) that I cannot use any variable at all.

Is there a way to generate a number sequence (for example, from 1 to max) with only n (current number index in the sequence) and seed?

Currently I am using this:

cast(((1103515245 * Seed * ROWID + 12345) % 2147483648) / 2147483648.0 * Max as int) + 1

with max being 47, ROWID being n. However for some seed, the repeat rate is too high (3 unique out of 47).

In my requirements, repetition is ok as long as it's not too much (<50%). Is there any better function that meets my need?

The question has sqlite tag but any language/pseudo-code is ok.

P.s: I have tried using Linear congruential generators with some a/c/m triplets and Seed * ROWID as Seed, but it does not work well, it's even worse.

EDIT: I currently use this one, but I do not know where it's from. The rate looks better than mine:

((((Seed * ROWID) % 79) * 53) % "Max") + 1

Answer 1

What about using good hash function and map result into [1...max] range?

Along the lines (in pseudocode). sha1 was added to SQLite 3.17.

sha1(ROWID) % Max + 1

Or use any external C code for hash (murmur, chacha, ...) as shown here

Answer 2

I am not sure if you still have the same problem but I might have a solution for you. What you could do is use Pseudo Random M-sequence generators based on shifting registers. Where you just have to take high enough order of you primitive polynomial and you don't need to store any variables really. For more info you can check the wiki page

What you would need to code is just the primitive polynomial shifting equation and I have checked in an online editor it should be very easy to do. I think the easiest way for you would be to use Binary base and use PRBS sequences and depending on how many elements you will have you can choose your sequence length. For example this is the implementation for length of 2^15 = 32768 (PRBS15), the primitive polynomial I took from the wiki page (There youcan find the primitive polynomials all the way to PRBS31 what would be 2^31=2.1475e+09) Basically what you need to do is:

SELECT (((ROWID << 1) | (((ROWID >> 14) <> (ROWID >> 13)) & 1)) & 0x7fff)

The beauty of this approach is if you take the sequence of the PRBS with longer period than your ROWID largest value you will have unique random index. Very simple. :)

If you need help with searching for primitive polynomials you can see my github repo which deals exactly with finding primitive polynomials and unique m-sequences. It is currently written in Matlab, but I plan to write it in python in next few days.

Cheers!

Answer 3

A linear congruential generator with appropriately-chosen parameters (a, c, and modulus m) will be a full-period generator, such that it cycles pseudorandomly through every integer in its period before repeating. Although you may have tried this idea before, have you considered that m is equivalent to max in your case? For a list of parameter choices for such generators, see L'Ecuyer, P., "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure", Mathematics of Computation 68(225), January 1999.

Note that there are some practical issues to implementing this in SQLite, especially if your SQLite version supports only 32-bit integers and 64-bit floating-point numbers (with 52 bits of precision). Namely, there may be a risk of—

• overflow if an intermediate multiplication exceeds 32 bits for integers, and
• precision loss if an intermediate multiplication results in a greater-than-52-bit number.

Also, consider why you are creating the random number sequence:

• Is the sequence intended to be unpredictable? In that case, a linear congruential generator alone is not enough, and you should generate unique identifiers by other means, such as by combining unique numbers with cryptographically random numbers.
• Will the numbers generated this way be exposed in any way to end users? If not, there is no need to obfuscate them by "shuffling" them.

Also, depending on the SQLite API you're using (for your programming language), there may be a way to write a custom function to convert the seed and ROWID to a random unique number. The details, however, depend heavily on the specific SQLite API. Another answer shows an example for Perl.