Where can I find 16-bit multipliers with good spectral scores?

[osobliwy nick]

In papers I know, the authors give 32-bit multipliers and bigger. But I need 16-bit multipliers to built some toy-PRNGs for research purposes .

Are there any sources where you can find them?  If someone had ready-to-use code to test a given multiplier, in Python, ultimately in c++, it would also be useful - I would find such multipliers myself.

[ratm...@gmail.com]

In the classical paper TABLES OF LINEAR CONGRUENTIAL GENERATORS

OF DIFFERENT SIZES AND GOOD LATTICE STRUCTURE by PIERRE L'ECUYER i find three Multiplicative LCGs with modulus 2^16 - 15 and multiplication constants 17364, 33285, and 2469.

But I cannot remember seing any power-of-two based ones on the form a*x + c

Cheers

/ Raimo Niskanen

[Sebastiano Vigna]

Can you be more specific? Prime modulus or power-of-two modulus?

On April 14, 2022 1:48:04 PM GMT+02:00, osobliwy nick <osobli...@gmail.com> wrote:

In papers I know, the authors give 32-bit multipliers and bigger. But I need 16-bit multipliers to built some toy-PRNGs for research purposes .

Are there any sources where you can find them?  If someone had ready-to-use code to test a given multiplier, in Python, ultimately in c++, it would also be useful - I would find such multipliers myself.

--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

[Sebastiano Vigna]

> On 14 Apr 2022, at 21:29, ratm...@gmail.com <ratm...@gmail.com> wrote:
>
> In the classical paper TABLES OF LINEAR CONGRUENTIAL GENERATORS
> OF DIFFERENT SIZES AND GOOD LATTICE STRUCTURE by PIERRE L'ECUYER i find three Multiplicative LCGs with modulus 2^16 - 15 and multiplication constants 17364, 33285, and 2469.
>
> But I cannot remember seing any power-of-two based ones on the form a*x + c
>

I think he really means generators with 16 bits of state.

If he really means 16-bit multipliers for modulues 2^32, they can be found here: https://onlinelibrary.wiley.com/doi/10.1002/spe.3030

Ciao,

seba

[Sebastiano Vigna]

> On 14 Apr 2022, at 22:14, Sebastiano Vigna <sebastia...@unimi.it> wrote:
>
> I think he really means generators with 16 bits of state.

BTW, for modulus 2^16 these are the only 16-bit multipliers with spectral scores at least 0.70 up to dimension 8:

0.705113 0.769212 43317 0xa935 0.761498 0.858664 0.705113 0.760345 0.732234 0.714710 0.790569
0.735784 0.814865 47989 0xbb75 0.890863 0.782499 0.735784 0.790569 0.752299 0.746490 0.790569
0.735784 0.814865 64733 0xfcdd 0.890863 0.782499 0.735784 0.790569 0.752299 0.746490 0.790569

Ciao,

seba

[Sebastiano Vigna]

Oops, I forgot the inverse of the first one (which is smaller than 2^15, so our search too wouldn't look for it).

0.705113 0.769212 8477 0x211d 0.761498 0.858664 0.705113 0.760345 0.732234 0.714710 0.790569

Ciao,

seba

[osobliwy nick]

I was thinking about LCG generators with modulus 2^16 (16 bits of state). I know that good multipliers for 32-bit (and bigger) LCGs can be found in  L'ecuyer and Vigna's papers.

So we got: 43317, 47989, 64733, 8477, right? By the way can you give me an example of bad ones? I know that 3 and 5 would be bad, but I need less obvious examples. I should probably say that they should have a high Kolmogorov complexity, but I can't precisely define it - so let's say I'm looking for bad ones, that look random (although I know that this is a imprecise criterion).

By the  way I was thinking also about golden ratio (times 2^16), I read somewhere that such a multiplier is good for hashing, is it reasonable to assume that it will have a good spectral score for LCG mod 2^n (I mean golden ratio times 2^n as a multiplier). In case of 16-bit LCG it would be 40503.

[Sebastiano Vigna]

You can easily analyze or list all such multipliers using the code at https://github.com/vigna/CPRNG

Edit the threshold constant in search.c to get all multipliers. Note that you have to try all bit sizes.

[osobliwy nick]

Ok, I will try it. Thank you!

[Sebastiano Vigna]

> On 14 Apr 2022, at 23:06, osobliwy nick <osobli...@gmail.com> wrote:
>
> So we got: 43317, 47989, 64733, 8477, right? By the way can you give me an example of bad ones? I know that 3 and 5 would be bad, but I need less obvious examples. I should probably say that they should have a high Kolmogorov complexity, but I can't precisely define it - so let's say I'm looking for bad ones, that look random

BTW, 3 does not give full period (the multiplier minus one must be divisible by 4).

Ciao,

seba

[osobliwy nick]

Yes, I forgot about the period (Hull–Dobell theorem).