Fractran: Computer architecture based on the multiplication of fractions

https://wiki.xxiivv.com/site/fractran.html

by signa11 • 2 years ago

105 22 2 years ago

$Preview of Fractran: Computer architecture based on the multiplication of fractions$ wiki.xxiivv.com

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.

theamk2• 2 years ago

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)

cvoss• 2 years ago

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.

entaloneralie2• 2 years ago

Because the denumerator is to the left side.

fanf2• 2 years ago

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

tromp2• 2 years ago

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

entaloneralie2• 2 years ago

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

tromp2• 2 years ago

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...

oersted• 2 years ago

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

Someone• 2 years ago

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

westurner• 2 years ago

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

neuroelectron3• 2 years ago

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-...

theamk2• 2 years ago

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.

kragen3• 2 years ago

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

Animats• 2 years ago

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.

eigenket• 2 years ago

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

Unless you divide by zero I guess

cyberax• 2 years ago

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.

SideQuark• 2 years ago

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

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

Fractran: Computer architecture based on the multiplication of fractions

Related Stories