This is a library that implements the FRACTRAN esoteric programming language,
invented by John Conway, in Rust. It supplies a basic way of running programs in
FRACTRAN and additionally implements a custom numeric type that is better suited
for the language than traditional types like u64.
This is a low-level crate: as you’ll see below, there’s a lot of boilerplate involved in actually running a program. Stay tuned for a crate that wraps this and provides a simple CLI for running FRACTRAN programs.
This is one of Conway’s original programs, used to generate the prime numbers. They appear as the exponents of the powers of 2 that the program produces.
```rust
// make the list of fractions
let nums: Vec
// Fraction is generic because it can use types other than u64, as we'll see shortly
// this is probably the easiest way to make a big list of fractio
let fracs: Vec
// create the program from that list let prog = Program::new(fracs); let mut primes = vec![];
// lazyexec() returns an iterator that runs as long as the program does, which in this case is forever // we fix that by stopping early using take() // note also that we feed in 2 for out in prog.lazyexec(2).take(2000) { // Rust's integer methods are pretty neat! if out.ispoweroftwo() { primes.push(out.trailingzeros()); } } assert_eq!(primes, vec![2, 3, 5, 7]); ```
You might notice that this only prints out 4 primes in 2000 executions. As it
turns out, when you can only use a single instruction, programs run long!
Additionally, the numbers can get big really quickly. u64 will overflow before
you can output 11: try replacing .take(2000) with a larger number to see what I
mean.
To fix the overflow issue, this crate has a PrimeBasis type that behaves like
u64 in the ways that FRACTRAN needs, but stores the prime factorization of each
number instead of the actual value. Because of the way FRACTRAN works, it’s very
rare to use large primes, and so in practice this is a huge space improvement.
We can modify the above program pretty easily to use PrimeBasis, which lets us
compute as many primes as we like.
```rust
let nums: Vec
// we have to now create a PrimeBasis, which adds a little more boilerplate here
// trynew() returns a Result because there's a fixed number of primes that the program uses
// any number that requires a factor not in our list of primes can't be represented
// this is almost never an issue because it's very rare you want to use very large prime factors
let fracs: Vec
let prog = Program::new(fracs); let mut primes = vec![];
// now can run the program for a lot longer: 100,000 iterations is pretty fast on my machine still // note that we need to feed in a PrimeBasis because that's the type our program is in for outpb in prog.lazyexec(PrimeBasis::trynew(2).unwrap()) .take(100000) { // we no longer have the integer methods, so we directly work with the list of exponents if outpb.exps[1..].iter().all(|&exp| exp == 0) { primes.push(outpb.exps[0]); } } // we have a lot more primes now! assert_eq!(primes, vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]); ```
PrimeBasis. Each operation is essentially doing some very simple iteration
over the number of prime factors being used. For programs where the largest
prime factor is small, which is most programs, a single operation is going to
be on the order of 10-20 basic operations.PrimeBasis is exported as MAX_REGS. It’s
currently 1000, which is a lot. (The name is because it’s easiest to think of
each prime exponent as a register in a more traditional program: this is the
number of registers.)PrimeBasis, in order, is exported as PRIMES: it’s
generated at compile time using MAX_REGS and a basic sieve. Use this and
MAX_REGS instead of hardcoding if it’s necessary.PrimeBasis doesn’t store extra trailing zeroes in its list of
exponents, so there’s no space cost if you aren’t using the extra register
space. The reason I don’t let you use a million registers is because that
would adversely affect compilation time.