5 ms·

Xorshift Generators

97 points by tobr 2mo ago

mococa 2mo ago
I’ve replaced Lua’s random by this. I’ve posted about it here https://nullonerror.org/2025/08/02/replacing-lua-s-math-random-module-with-the-xorshift-algorithm/ https://nullonerror.org/2025/08/02/replacing-lua-s-math-rand...
- dchest 2mo ago
  Lua 5.4 and 5.5 use xoshiro256**: https://www.lua.org/manual/5.4/manual.html#pdf-math.random https://www.lua.org/manual/5.4/manual.html#pdf-math.random
  - mococa 2mo ago
    Good to know. I use LuaJIT. But in any case I reverted that, befitting the overhead from my solution to Lua’s native was big.
saithound 2mo ago
Ah yes, Xorshift, the RANDU [1] of the 21st century [2]. There is no real use case for better non-CS generators, as explained by adrian_b back in 2021 [3]. [1] https://en.wikipedia.org/wiki/RANDU https://en.wikipedia.org/wiki/RANDU [2] https://arxiv.org/abs/1908.10020 https://arxiv.org/abs/1908.10020 [3] https://news.ycombinator.com/item?id=28886698 https://news.ycombinator.com/item?id=28886698
- moregrist 2mo ago
  I’m not sure what point you’re trying to make, exactly, but a use case for better non-CS generators has always been stochastic simulation, especially simulation/sampling approaches that are bound by the number and quality of uniform variates per second. As someone who has spent considerable time working in these areas, I still appreciate advances.
  - saithound 2mo ago
    > I’m not sure what point you’re trying to make, Have you skimmed the linked thread? > especially simulation/sampling approaches that are bound by the number and quality of uniform variates per second Sorry, nobody does stochastic simulations where the number of uniform random numbers obtained per second is any sort of bottleneck. If you've spent considerable time on stochastic simulation, you already know this. But even if you insist that you alone are doing some very weird stochastic simulation which is somehow bottlenecked on sourcing random numbers fast enough, the falling in planes phenomenon linked above would make xorshift-type generators a poor choice for most sorts of simulations. It introduces spatial correlations into any sort of lattice dynamics simulation (Ising model, percolation) and every high dimensional Monte Carlo integration. Beyond falling in the planes, since xorshift is linear over GF(2), it is also a particularly bad choice for nondeterministic cellular automata and Boolean dynamical systems which use parity, bit masks, or xors. AES-CTR throughput on a modern CPU is higher than that of xoshiro256++, and much higher quality. No advances in non-CS PRNGs can beat that while maintaining the same quality. If your stochastic simulation is bottlenecked on random bits, CSPRNGs are still the way to go, and they don't interact in nasty ways with any dynamical system you can actually sinulate quickly.
    - dgacmu 2mo ago
      This is a very weird hill to die on. I do a lot of testing and designing of things like hash tables and filters, and having a really fast, non-CS generator is incredibly useful for being able to clearly identify performance bottlenecks in designs. PCG has been spectacularly useful for that purpose for me.
      - saithound 2mo ago
        When was the last time a new PRNG helped you clearly identify a performance bottleneck? As in, you were using state of the art generator X, and you couldn't see the performance bottleneck, but updating to a newer (faster, or same speed but higher quality) generator Y, and could subsequently identify the performance bottleneck? If you're using PCG, not in the last 12 years. (In a parallel comment I suggest trying AES-CTR for this use case)
- mallets 2mo ago
  I don't know about all that, but I use Marsaglias for generating noise samples in MCUs like Pico. It's the fastest option there is for such devices.
  - AlanZucconi 2mo ago
    I agree! For many games (especially the ones running on old devices), xorshifts are pretty good! Not all applications need cryptographically safe generators! And sometimes it's ok to trade complexity for speed! But I agree that if you're building something new aimed for modern devices, Marsaglia's xorshift128 wouldn't be my first choice! But I'd definitely want it in my RNG library for backward compatibility!
    - WalterGillman 1mo ago
      If you are interested in performant retro PRNGs, you can find a link to mine in my profile, if I am not mistaken. The counter is based on xorshift. As of the time of release it passed all tests that could be passed with only a 2^32-1 period. On Z80 it was only about as fast as RC4 which is also a good option in terms of performance and quality but whereas RC4 has a huge state, this one only has a 32bit state, the rest staying in ROM.
- kevin_thibedeau 1mo ago
  > no real use case Yes there is. Not every system has the need or the resources to maintain a secure random sequence. You may also want a reproducible pseudo-random sequence in generative code that logs the seeds. Because of the misguided attitude that nobody needs these features, everyone who does need them has to roll their own now.
  - Dylan16807 1mo ago
    > Not every system has the need or the resources to maintain a secure random sequence. I'm sure there's something, but that category has to be shrinking every year. What does such a system look like this decade, that needs random numbers but can't easily implement something like AES? > You may also want a reproducible pseudo-random sequence in generative code that logs the seeds. Because of the misguided attitude that nobody needs these features, everyone who does need them has to roll their own now. I don't know what difficulty you're referring to. Basically every CSPRNG can be seeded easily and you can log the seed.
AlanZucconi 2mo ago
I'm really curious... How did you manage to post this link before I did?
- tobr 2mo ago
  I have your feed in my RSS reader! This seemed like something HN would be interested in.
  - AlanZucconi 2mo ago
    I should be faster next time then: my entry got tagged as [dupe] ahah! Also: I somehow got 10x the usual amount of traffic today, and my website is sort of on fire!
    - chrisjj 2mo ago
      ... and currently nonresponsive.
      - AlanZucconi 2mo ago
        Try now!
        netvarun 2mo ago
        Still not loading
        netvarun 2mo ago
        https://archive.is/zElcb https://archive.is/zElcb
        AlanZucconi 2mo ago
        Thanks! The traffic has been wild today!
smusamashah 2mo ago
[flagged]
- AlanZucconi 2mo ago
  I understand that a big portion of online content is now 100% AI-generated, and that can be somewhat problematic. But for creators like me, who have been publishing articles and books for over 10 years, this AI witch hunt can be quite demotivating. I worked on this project for over one year. I wrote an entire distributed framework to calculate maximal triplets, and I have 130+ machines running 24/7 for 12 weeks on N=8192. This article is an extended version of the script for the video documentary that will be released before the end of the year. If you look back at my website, I used to publish two small articles a week. I've since reduced to 1 or 2 large pieces a year. And one of the reasons was exactly to rise above the many blogs that post small, fragmented articles, which could be generated in 2 minutes by ChatGPT. If I wanted to continue in that direction, I could be publishing 100 short articles a week with ChatGPT. I started writing practical shader tutorials back in 2014 because there were not enough good, accessible resources online. I'm now focusing on large, in-depth pieces with original research, because that's what's valuable right now that ChatGPT has replaced StackOverflow. If you appreciated this article, I hope you'll appreciate it even more knowing that YES, it was written by a human (it's me, hi!). <3
  - makira 2mo ago
    I enjoyed the article, and thank you for sharing it. Don't be demotivated by the current AI witch hunt, which I see as a form of tribal signaling that will pass.
    - AlanZucconi 2mo ago
      Thanks, I really appreciate it! <3
  - smusamashah 2mo ago
    Then I am very sorry about that, I feel bad and should read more carefully next. I only glanced at first few paragraphs and encountered this line which is a very common LLM trope. I could see that article is long and has lots of images and other stuff but I could see em dashes too. As no one else had said that yet, I did. But I do want to say that this 'witch hunt' is OK. We should keep calling out AI content which is mostly effortless to keep actual effort by humans separate from this flood of content.
YZF 1mo ago
https://en.wikipedia.org/wiki/Linear-feedback_shift_register https://en.wikipedia.org/wiki/Linear-feedback_shift_register
larsbrinkhoff 1mo ago
Xorshift-36 for the PDP-10, with help from Sebastiano Vigna. https://github.com/larsbrinkhoff/xoroshiro-36 https://github.com/larsbrinkhoff/xoroshiro-36
- avadodin 1mo ago
  This is xoroshiro not xorshift. It's right there in the URL.
  - larsbrinkhoff 1mo ago
    It's both.
    - avadodin 1mo ago
      Okay, true. There is an undocumented xorshift implementation in tst.c.
      - larsbrinkhoff 1mo ago
        This is xorshift. https://github.com/larsbrinkhoff/xoroshiro-36/blob/master/xorshi.mid https://github.com/larsbrinkhoff/xoroshiro-36/blob/master/xo...
jabl 1mo ago
A number of years ago I implemented xoshiro256** for the GFortran compiler. Previously it used Marsaglia's KISS generator, which wasn't bad but perhaps no longer state of the art on the TESTU1 etc. tests. Additionally, xoshiro256** can be used in parallel by multiple threads; that took a bit of clever hacking to work around the limitations of the Fortran intrinsics API.

97 points by tobr 2mo ago

I’ve replaced Lua’s random by this. I’ve posted about it here https://nullonerror.org/2025/08/02/replacing-lua-s-math-random-module-with-the-xorshift-algorithm/ https://nullonerror.org/2025/08/02/replacing-lua-s-math-rand...

dchest 2mo ago
Lua 5.4 and 5.5 use xoshiro256**: https://www.lua.org/manual/5.4/manual.html#pdf-math.random https://www.lua.org/manual/5.4/manual.html#pdf-math.random
- mococa 2mo ago
  Good to know. I use LuaJIT. But in any case I reverted that, befitting the overhead from my solution to Lua’s native was big.

saithound 2mo ago

Ah yes, Xorshift, the RANDU [1] of the 21st century [2]. There is no real use case for better non-CS generators, as explained by adrian_b back in 2021 [3]. [1] https://en.wikipedia.org/wiki/RANDU https://en.wikipedia.org/wiki/RANDU [2] https://arxiv.org/abs/1908.10020 https://arxiv.org/abs/1908.10020 [3] https://news.ycombinator.com/item?id=28886698 https://news.ycombinator.com/item?id=28886698

moregrist 2mo ago
I’m not sure what point you’re trying to make, exactly, but a use case for better non-CS generators has always been stochastic simulation, especially simulation/sampling approaches that are bound by the number and quality of uniform variates per second. As someone who has spent considerable time working in these areas, I still appreciate advances.
- saithound 2mo ago
  > I’m not sure what point you’re trying to make, Have you skimmed the linked thread? > especially simulation/sampling approaches that are bound by the number and quality of uniform variates per second Sorry, nobody does stochastic simulations where the number of uniform random numbers obtained per second is any sort of bottleneck. If you've spent considerable time on stochastic simulation, you already know this. But even if you insist that you alone are doing some very weird stochastic simulation which is somehow bottlenecked on sourcing random numbers fast enough, the falling in planes phenomenon linked above would make xorshift-type generators a poor choice for most sorts of simulations. It introduces spatial correlations into any sort of lattice dynamics simulation (Ising model, percolation) and every high dimensional Monte Carlo integration. Beyond falling in the planes, since xorshift is linear over GF(2), it is also a particularly bad choice for nondeterministic cellular automata and Boolean dynamical systems which use parity, bit masks, or xors. AES-CTR throughput on a modern CPU is higher than that of xoshiro256++, and much higher quality. No advances in non-CS PRNGs can beat that while maintaining the same quality. If your stochastic simulation is bottlenecked on random bits, CSPRNGs are still the way to go, and they don't interact in nasty ways with any dynamical system you can actually sinulate quickly.
  - dgacmu 2mo ago
    This is a very weird hill to die on. I do a lot of testing and designing of things like hash tables and filters, and having a really fast, non-CS generator is incredibly useful for being able to clearly identify performance bottlenecks in designs. PCG has been spectacularly useful for that purpose for me.
    - saithound 2mo ago
      When was the last time a new PRNG helped you clearly identify a performance bottleneck? As in, you were using state of the art generator X, and you couldn't see the performance bottleneck, but updating to a newer (faster, or same speed but higher quality) generator Y, and could subsequently identify the performance bottleneck? If you're using PCG, not in the last 12 years. (In a parallel comment I suggest trying AES-CTR for this use case)
mallets 2mo ago
I don't know about all that, but I use Marsaglias for generating noise samples in MCUs like Pico. It's the fastest option there is for such devices.
- AlanZucconi 2mo ago
  I agree! For many games (especially the ones running on old devices), xorshifts are pretty good! Not all applications need cryptographically safe generators! And sometimes it's ok to trade complexity for speed! But I agree that if you're building something new aimed for modern devices, Marsaglia's xorshift128 wouldn't be my first choice! But I'd definitely want it in my RNG library for backward compatibility!
  - WalterGillman 1mo ago
    If you are interested in performant retro PRNGs, you can find a link to mine in my profile, if I am not mistaken. The counter is based on xorshift. As of the time of release it passed all tests that could be passed with only a 2^32-1 period. On Z80 it was only about as fast as RC4 which is also a good option in terms of performance and quality but whereas RC4 has a huge state, this one only has a 32bit state, the rest staying in ROM.
kevin_thibedeau 1mo ago
> no real use case Yes there is. Not every system has the need or the resources to maintain a secure random sequence. You may also want a reproducible pseudo-random sequence in generative code that logs the seeds. Because of the misguided attitude that nobody needs these features, everyone who does need them has to roll their own now.
- Dylan16807 1mo ago
  > Not every system has the need or the resources to maintain a secure random sequence. I'm sure there's something, but that category has to be shrinking every year. What does such a system look like this decade, that needs random numbers but can't easily implement something like AES? > You may also want a reproducible pseudo-random sequence in generative code that logs the seeds. Because of the misguided attitude that nobody needs these features, everyone who does need them has to roll their own now. I don't know what difficulty you're referring to. Basically every CSPRNG can be seeded easily and you can log the seed.

AlanZucconi 2mo ago

I'm really curious... How did you manage to post this link before I did?

tobr 2mo ago
I have your feed in my RSS reader! This seemed like something HN would be interested in.
- AlanZucconi 2mo ago
  I should be faster next time then: my entry got tagged as [dupe] ahah! Also: I somehow got 10x the usual amount of traffic today, and my website is sort of on fire!
  - chrisjj 2mo ago
    ... and currently nonresponsive.
    - AlanZucconi 2mo ago
      Try now!
      - netvarun 2mo ago
        Still not loading
        netvarun 2mo ago
        https://archive.is/zElcb https://archive.is/zElcb
        AlanZucconi 2mo ago
        Thanks! The traffic has been wild today!

smusamashah 2mo ago

[flagged]

AlanZucconi 2mo ago
I understand that a big portion of online content is now 100% AI-generated, and that can be somewhat problematic. But for creators like me, who have been publishing articles and books for over 10 years, this AI witch hunt can be quite demotivating. I worked on this project for over one year. I wrote an entire distributed framework to calculate maximal triplets, and I have 130+ machines running 24/7 for 12 weeks on N=8192. This article is an extended version of the script for the video documentary that will be released before the end of the year. If you look back at my website, I used to publish two small articles a week. I've since reduced to 1 or 2 large pieces a year. And one of the reasons was exactly to rise above the many blogs that post small, fragmented articles, which could be generated in 2 minutes by ChatGPT. If I wanted to continue in that direction, I could be publishing 100 short articles a week with ChatGPT. I started writing practical shader tutorials back in 2014 because there were not enough good, accessible resources online. I'm now focusing on large, in-depth pieces with original research, because that's what's valuable right now that ChatGPT has replaced StackOverflow. If you appreciated this article, I hope you'll appreciate it even more knowing that YES, it was written by a human (it's me, hi!). <3
- makira 2mo ago
  I enjoyed the article, and thank you for sharing it. Don't be demotivated by the current AI witch hunt, which I see as a form of tribal signaling that will pass.
  - AlanZucconi 2mo ago
    Thanks, I really appreciate it! <3
- smusamashah 2mo ago
  Then I am very sorry about that, I feel bad and should read more carefully next. I only glanced at first few paragraphs and encountered this line which is a very common LLM trope. I could see that article is long and has lots of images and other stuff but I could see em dashes too. As no one else had said that yet, I did. But I do want to say that this 'witch hunt' is OK. We should keep calling out AI content which is mostly effortless to keep actual effort by humans separate from this flood of content.

YZF 1mo ago

https://en.wikipedia.org/wiki/Linear-feedback_shift_register https://en.wikipedia.org/wiki/Linear-feedback_shift_register

larsbrinkhoff 1mo ago

Xorshift-36 for the PDP-10, with help from Sebastiano Vigna. https://github.com/larsbrinkhoff/xoroshiro-36 https://github.com/larsbrinkhoff/xoroshiro-36

avadodin 1mo ago
This is xoroshiro not xorshift. It's right there in the URL.
- larsbrinkhoff 1mo ago
  It's both.
  - avadodin 1mo ago
    Okay, true. There is an undocumented xorshift implementation in tst.c.
    - larsbrinkhoff 1mo ago
      This is xorshift. https://github.com/larsbrinkhoff/xoroshiro-36/blob/master/xorshi.mid https://github.com/larsbrinkhoff/xoroshiro-36/blob/master/xo...

jabl 1mo ago

A number of years ago I implemented xoshiro256** for the GFortran compiler. Previously it used Marsaglia's KISS generator, which wasn't bad but perhaps no longer state of the art on the TESTU1 etc. tests. Additionally, xoshiro256** can be used in parallel by multiple threads; that took a bit of clever hacking to work around the limitations of the Fortran intrinsics API.