Fractran: Computer architecture based on the multiplication of fractions | Hacker News Reader

Fractran: Computer architecture based on the multiplication of fractions

wiki.xxiivv.com

105 pointssigna1122 comments

I like Raganwald’s ode to Fractran which relates it to Minsky’s register machines and (surprisingly) the Collatz conjecture. https://raganwald.com/2020/05/03/fractran.html

This was a bit hard to read, requiring some note taking and some factorizating to check the correspondence between variable names and primes.

> You can get the product of two registers(x*y) by keeping an intermediate result and state register. Keeping the resulting product, by naming the first register for the result, prevents the accumulator grow too much in size:

    :: r acc x y
    :: iter acc > x iter
    :: iter >
    :: x y > r acc y 
    :: y > iter
    :: x > 

    AC 8575 x^2 y^2
    .. r^6

This one is harder to figure out. The first line reserves primes 2,3,5,7 for variables r, acc, x, y. The unreserved iter should then be assigned prime 11. The accumulator AC starts at value 8575 = 5^2 * 7^3, so the y^2 has a typo and should be y^3. Which matches the desired end result of 2*3 = 6. But how exactly does it get there?

Btw, the corresponding FRACTRAN program would be

    5*11  1   2*3*7  11  1
    ----  --  -----  --  -
    3*11  11   5*7    7  5

Reduction steps from the example: https://git.sr.ht/~rabbits/fractran/tree/main/item/examples

  :: 55/33 acc.3 iter.11 > x.5 iter.11 
  :: 1/11 iter.11 > 
  :: 42/35 x.5 y.7 > r.2 acc.3 y.7 
  :: 11/7 y.7 > iter.11 
  :: 1/5 x.5 > 

  AC x x y y y 
  02 42/35 r acc x y y y 
  02 42/35 r r acc acc y y y 
  03 11/7 r r acc acc y y iter 
  00 55/33 r r acc x y y iter 
  00 55/33 r r x x y y iter 
  01 1/11 r r x x y y 
  02 42/35 r r r acc x y y 
  02 42/35 r r r r acc acc y y 
  03 11/7 r r r r acc acc y iter 
  00 55/33 r r r r acc x y iter 
  00 55/33 r r r r x x y iter 
  01 1/11 r r r r x x y 
  02 42/35 r r r r r acc x y 
  02 42/35 r r r r r r acc acc y 
  03 11/7 r r r r r r acc acc iter 
  00 55/33 r r r r r r acc x iter 
  00 55/33 r r r r r r x x iter 
  01 1/11 r r r r r r x x 
  04 1/5 r r r r r r x 
  04 1/5 r r r r r r 

  r r r r r r

Even looking at this, I find it still very hard to see how it's computing x*y for arbitrary values of x and y...

Some of the choices there make things harder to read.

For example, this machine takes two numbers and they are the numerator and denominator. Why on earth use ">" for the separator? That already has a mathematical meaning.

I assume you'd prefer to use "/" or "÷" instead?

">" is not a division, it's a rewrite operator, and in the page, it's only used with symbolic representation. I would not call "y div1 /" better than "y div1 >", it's special notation either way. And having special symbol makes it easier to understand when are we talking about regular math vs rewrite rules.

(Alternatively, if you meant "why not some other Unicode symbol": I am guessing author wants something easy to type, I can relate)

Because the fraction represents a rewrite rule, which is the fundamental unit of computation in this language. Instances of the denominator factors are replaced with instances of the numerator factors.

Some people read x/y as a rewrite already (like programming language nerds). Others don't, and it makes sense to me to use a more intuitive, directed symbol to denote the action.

FWIW, `>` has not one but many meanings across programming languages.

Because the denumerator is to the left side.

I think this site, along with the 100r.co sister site, are my favourite places on the Internet. Digital Garden indeed!

I think the Wikipedia page (https://en.wikipedia.org/wiki/FRACTRAN) is easier for understanding Fractan.

By Church-Turing, is Fractran sufficient to host a Hilbert logic? https://en.wikipedia.org/wiki/Hilbert_system

It reminds me of the https://en.wikipedia.org/wiki/Residue_number_system , it was actually used in a Russian computer system called "Duga" ("Curve") that needed fast multiplications.

It's still used for some niche purposes.

FRACTRAN interpreter in FRACTRAN, explaining how to write programs in FRACTRAN.

http://lomont.org/posts/2017/fractran/

Rational arithmetic machines have their uses. SAT solvers tend to have one inside. That's because rational arithmetic is closed under addition, subtraction, multiplication and division.

> That's because rational arithmetic is closed under addition, subtraction, multiplication and division.

Unless you divide by zero I guess

The reason to do this would to create a quantum computer emulator. I was looking into this myself recently. I believe Iran was doing the same things but on FPGAs:

https://www.tomshardware.com/news/iran-quantum-computer-arm-...

Why would anyone outside of quantum computer research want a quantum computer emulator? On classical machines, classical algorithms beat emulated quantum ones by a very large margin. And Iran apparently claimed "detecting surface vessels using the quantum algorithms", which makes very little sense as there are no high-performance quantum image detection algorithms known, so this is highly likely just some Iranian researchers fooling their government, and making a laughing stock of themselves in the process.

presumably you would want it in order to do research on quantum algorithms, but i don't see what that has to do with fractran

To record the state of a qubit you need fractions and to do quantum math it's mostly multiplying fractions.

someone has a major confusion of levels here. have they ever tried asking gpt-4 to multiply some matrices, i wonder?

I'm guessing that's a joke. The benefit of hardware support for fractions is eliminating rounding errors you get with today's machines. You can do it with libs like PyMath but ultimately you need to do build it from the ground up to completely eliminate type and class abstractions messing up the accuracy, so why not start at the hardware level so potential future chips are automatically supported? Then you can get today's performance without the overhead of legacy software.

it's not a joke. writing a program in fractran to multiply input fractions that are part of the input data is no easier than writing a program in other turing-tarpit esolangs with no built-in arithmetic support, like the λ-calculus. try it. or check out https://stackoverflow.com/questions/1749905/code-golf-fractr... which has a couple of unusably inefficient fractran interpreters in fractran

Reply on news.ycombinator.com