This repository contains several PRNGs (Pseudo Random Number Generators) written in 6502 assembly. Because I was not happy with the quality of the available generators, I wrote a few more modern ones. The code was written for the Atari 8-bit with Mad-Assembler, but should be easy to port to other 6502 based systems. Or add opt h- to suppress Atari 8-bit headers, and output raw binary data. See the generic emulation based test code that makes use of that.
Generator | Bits | Size | ZP | Speed | Quality | Notes | |||
---|---|---|---|---|---|---|---|---|---|
Seed | Generate | ||||||||
Min | Max | Avg | |||||||
single_eor | 8 | 17 | 1 | 15 | 23 | 28 | 27 | ❌ | |
four_taps_eor | 8 | 37 | 1 | 15 | 56 | 60 | 58 | ❌ | |
sfc16 | 16 | 180 | 10 | 2432 | 27 | 243 | 132 | ⭐⭐ | smallest |
sfc32 | 32 | 296 | 20 | 5845 | 29 | 394 | 116 | ⭐⭐⭐ | |
chacha20(8) | 32 | 2101 | 64 | 708 | 29 | 15945 | 277 | ⭐⭐⭐⭐⭐ | crypto, random access |
chacha20(12) | 32 | 2101 | 64 | 708 | 29 | 23450 | 393 | ⭐⭐⭐⭐⭐ | |
chacha20(20) | 32 | 2101 | 64 | 708 | 29 | 38376 | 627 | ⭐⭐⭐⭐⭐ | |
jsf32 | 32 | 337 | 20 | 7332 | 29 | 376 | 115 | ⭐⭐⭐ | fastest |
arbee | 64 | 614 | 56 | 13480 | 29 | 1143 | 164 | ⭐⭐⭐⭐ | entropy pooling |
This is the internal word size. Each generator outputs bytes. Larger word sizes are buffered and returned as bytes. The most significant byte first, down to the least significant one, after which a new word is calculated on the next call.
This is the size of all 6502 code, including variables or constant data that is not in zero page. Algorithms with large tables, like efiix or hc256, are avoided.
The amount of bytes needed in zero page. Most of the time this is the internal state, sometimes combined with space for a few temporary variables for speed during calculation.
Times are in clock cycles. This includes the calling JSR instruction and the returning RTS instruction.
single_eor and four_taps_eor are pretty bad. They fail every single test suite.
sfc16, sfc32, chacha20, jsf32, and arbee are all very good. The star rating is relative to eachother. They all pass TestU01's Alphabit, Rabbit, FIPS 140-2, SmallCrush, Crush, and BigCrush. They also pass PractRand's RNG_test (>1TB, chacha20 >4TB), gjrand's mcp, and the old dieharder test suite. See https://pracrand.sourceforge.net/RNG_engines.txt for a detailed description and analysis, and https://pracrand.sourceforge.net/Tests_results.txt for test results.
In short, chacha20 is the best of the generators in this repo, then arbee (which basically is jsf64 with a counter), then jsf32 and sfc32, and finally sfc16. In terms of speed, ignoring the bad PRNGs, jsf32 is the fastest. In terms of code size and ZP usage, sfc16 wins.
The 6502 was launched in September 1975. An unmodified Atari 8-bit with a 6502 clocked at ±1.8Mhz, display DMA disabled, and VBI enabled for the timer, needs ± 31317 hours to generate 1TB of data (3 years, 209 days and 21 hours) with the jsf32 generator. For perspective, my x86_64 machine (Octacore AMD FX-8320 3.5GHz, launched October 2012) does that in about an hour on a single core.
6502 implementations of sfc16, chacha20, jsf32, and arbee are Copyright © 2023 by Ivo van Poorten. License is BSD-2-Clause.
sfc16, chacha20, jsf32, and arbee based on C++ code Copyright © by Chris Doty-Humphrey.
jsf32's C++ code is mostly by Robert Jenkins.
All are public domain. See https://pracrand.sourceforge.net/
single_eor is Copyright © by White Flame, https://codebase64.org/doku.php?id=base:small_fast_8-bit_prng
four_taps_eor is Copyright © 2002 by Lee E. Davison, https://philpem.me.uk/leeedavison/6502/prng/index.html
MCS6502 emulator is Copyright (c) 2019 by Ben Zotto, MIT License.