XXIIVV

Arithmetics is the study of numbers, especially the properties of the traditional operations on them.

Some mathematicians are of the opinion that the doing of mathematics is closer to discovery than invention.

Primes

Multiplying two numbers is the same as adding the counts of each prime factors, and division is the same as subtracting the counts. To experiment with primes, have a look at Fractran. For example, using numbers made up of the 3 first primes(2, 3, 5), 2250 is equal to 2^1 x 3^2 x 5^3.

6 * 375 = 2250
6(1,1,0)375(0,1,3)2250(1,2,3)

To find the prime factorization of a number, start by dividing the number by the first prime number 2 and continue dividing by 2 until you get a decimal or remainder. Then divide by 3, 5, 7, etc. until the only numbers left are prime numbers.

Peasant Multiplication

In the first column, divide the first number by 2, dropping the remainder if any, until 1 is reached. In the second column, write the numbers obtained by successive multiplication by 2. The answer is found by adding the numbers in the doubling column with odd numbers in their first column.

64 x 61
6461
32122
16244
8488
4976
21952
13904+3904
Result: 3904
61 x 64
6164+64
30128
15256+256
7512+512
31024+1024
12048+2048
Result: 3904

Addition of 5

When adding 5 to a digit greater than 5, it is easier to first subtract 5 and then add 10.

7 + 5 = 12.
Also 7 - 5 = 2; 2 + 10 = 12.

Subtraction of 5

When subtracting 5 from a number ending with a a digit smaller than 5, it is easier to first add 5 and then subtract 10.

23 - 5 = 18.
Also 23 + 5 = 28; 28 - 10 = 18.

Division by 5

Similarly, it's often more convenient instead to multiply first by 2 and then divide by 10.

1375/5 = 2750/10 = 275.

Multiplication by 5

It's often more convenient instead of multiplying by 5 to multiply first by 10 and then divide by 2.

137×5 = 1370/2 = 685.

Division by 5

Similarly, it's often more convenient instead to multiply first by 2 and then divide by 10.

1375/5 = 2750/10 = 275.

Division/multiplication by 4

Replace either with a repeated operation by 2.

124/4 = 62/2 = 31. Also,
124×4 = 248×2 = 496.

Division/multiplication by 25

Use operations with 4 instead.

37×25 = 3700/4 = 1850/2 = 925.

Division/multiplication by 8

Replace either with a repeated operation by 2.

124×8 = 248×4 = 496×2 = 992.

Division/multiplication by 125

Use operations with 8 instead.

37×125 = 37000/8 = 18500/4 = 9250/2 = 4625.

Misc

binary

Binary numbers are a base 2 numeral system.

A binary number is a number expressed in the base-2 numeral system, which uses only two symbols: 0 and 1. Each digit is referred to as a bit. Because of its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used by almost all modern computers and computer-based devices.

 
—Two of Leibniz's binary calculation examples

To explore binary logic, see Noton or Der Papiercomputer.

reverse polish

In Reverse Polish Notation, the operators follow their operands.

In RPN calculators, no equals key is required to force computation to occur. To learn more about a programming language using RPN at its core, see Forth. To find a simple RPN implementation and playground, see Firth.

fractran

Fractran is insanely difficult to program in, but based on one of the most bizarrely elegant concepts of computation.

A Fractran program is an ordered list of positive fractions together with an initial positive integer input. The program is run by updating the accumulator.

 
—The Book of Numbers, John Conway

Any number that can't be divided by any other number, apart from itself and one, is prime. Since primes can't be divided, we can think of them as the DNA of other numbers. In Fractran, each prime is a register and their exponent is their value.

The Accumulator

The state of the accumulator is held as a single number, whose prime factorization holds these registers(2, 3, 5, 7, 11, 13, 17, ..). If the state of the accumulator is 1008(2⁴ × 3² × 7), r2 has the value 4, r3 has the value 2, r7 has the value 1, and all other registers are unassigned.

accumulatorregisters
r2r3r5r7
611
1812
1008421
54022501234

The Operators

A fractran operation is a positive fraction, each fraction represents an instruction that tests one or more registers, represented by the prime factors of its denominator. The Fractran computer goes through each fraction in order, in terms of our current accumulator value.

18(21 × 32) 2/3 = 8(23) addition r2+r3->r2

To run the adder operation(2/3), we will take the state of the accumulator. If multiplying it by this fraction will give us an integer, we will do so and start again at the beginning of the program. Otherwise, we will stop and consider the program complete. We will do this repeatedly until we can no longer produce an integer with this method.

stepsstateregisters
r2r3
1181218 × 2/3 = 12/1INT, RESTART
2122112 × 2/3 = 8/1INT, RESTART
3838 × 2/3 = 16/3NOT INT, END

To add the values 1 and 2, we will store the values in registers 2 and 3, our starting state is therefore 18(21 × 32).

For each step of the program, we will multiply our state with the program(18 × 2/3 = 12, 12 × 2/3 = 8, ..) until our our working value cannot be reduced to a whole number(16/3), we have exhausted the program. Alternatively, the program 3/2 will do the same operation but store the result in the register 3.

576(26 × 32) 1/6 = 16(24) subtraction r2-r3->r2

Operations become more readable when broken down into their primes. We can think of every prime number as having a register which can take on non-negative integer values. Each fraction is an instruction that operates on some of the registers.

2/3 15/256 21/20
(21)/(31) (31 × 51)/(26) (31 × 71)/(22 × 51)
if(r3 >= 1){ 
	r3 -= 1;
	r2 += 1;
	return;
}
if(r2 >= 6){ 
	r2 -= 6;
	r3 += 1;
	r5 += 1;
	return;
}
if(r2 >= 2 && r5 >= 1){ 
	r2 -= 2; 
	r5 -= 1; 
	r3 += 1; 
	r7 += 1;
	return;
}

You can interpret a fraction as saying if the current value of each register is greater than or equal to the the value specified by the denominator, you subtract from the registers all of the values in the denominator, add all the values specified in the numerator, and then jump back to the first instruction. Otherwise, if any register is less than the value specified in the denominator, continue to the next fraction.

The Programs

A Fractran program is a list of fractions together with an initial positive integer input n. The program is run by updating the integer n as follows:

Let's put together an adder program similar from the one above(2/3) but which writes to a third register. The following program first moves the content in r2 to r3, and then the content of r3 to r5.

18(21 × 32) 3/2 5/3 = 125(53) addition r2+r3->r5(9 steps)

Alternatively, a faster way to do this would be to directly move powers of 2 over to 5, then powers of 3.

18(21 × 32) 5/2 5/3 = 125(53) addition r2+r3->r5(7 steps)

Each of the 7 steps of this last program looks like:

18 5/2 5/3           [18]  r2=01 r3=02
------------------   -----------------
18 × 5/2 = 45/1      [45]  r3=02 r5=01
45 × 5/2 = 225/2 
45 × 5/3 = 75/1      [75]  r3=01 r5=02
75 × 5/2 = 375/2 
75 × 5/3 = 125/1     [125] r5=03
125 × 5/2 = 625/2 
125 × 5/3 = 625/3    [125] r5=03

Both of these programs are destructive, meaning that they drain the registers of their original values. We can make (2/3) less destructive with (10/3) by storing a copy of r3 in r5. And we can create a non-destructive adder but this requires coming in with the program with the flag r7 set:

126(21 × 32 × 71) 7/11 715/14 935/21 1/7 2/13 3/17 = 2250(21 × 32 × 53)

As an extra demonstration, let us consider the following programs representing all the logic gates:

Program07142142
AND Gate5/42 1/21 1/14 1/71115
OR Gate5/42 5/21 5/14 1/71555
XOR Gate1/42 5/21 5/14 1/71551
NAND Gate1/42 5/21 5/14 5/75551
NOR Gate1/42 1/21 1/14 5/75111
XNOR Gate5/42 1/21 1/14 5/75115
— Submit an edit to fractran_guide.htm(137 lines)

Interpreter

A simple Fractran interpreter, written in ANSI C, showing the value in the registers as it steps through the program.

#include <stdio.h>

/* 
Copyright (c) 2020 Devine Lu Linvega

Permission to use, copy, modify, and distribute this software for any
purpose with or without fee is hereby granted, provided that the above
copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE.
*/

typedef struct Fraction {
	unsigned int num, den;
} Fraction;

typedef struct Machine {
	int len;
	Fraction acc, program[256];
} Machine;

int
gcd(int a, int b)
{
	if(b == 0)
		return a;
	return gcd(b, a % b);
}

Fraction
Frac(unsigned int num, unsigned int den)
{
	Fraction f;
	unsigned int d = gcd(num, den);
	f.num = num / d;
	f.den = den / d;
	return f;
}

void
printstate(Machine *m)
{
	unsigned int fac = 2, num = m->acc.num;
	printf("[%d] ", num);
	while(num > 1) {
		if(num % fac == 0) {
			unsigned int pow = 1;
			printf("r%02u=", fac);
			num /= fac;
			while(!(num % fac)) {
				num /= fac;
				pow++;
			}
			printf("%02u", pow);
			if(num != 1)
				putchar(' ');
		} else
			fac++;
	}
	putchar('\n');
}

void
run(Machine *m)
{
	int i = 0, steps = 0;
	while(i < m->len && m->acc.num) {
		Fraction res, *f = &m->program[i++];
		res = Frac(m->acc.num * f->num, m->acc.den * f->den);
		printf("%u × %u/%u = %u/%u \n",
			m->acc.num,
			f->num,
			f->den,
			res.num,
			res.den);
		if(res.den == 1) {
			m->acc = res;
			printstate(m);
			i = 0;
		}
		steps++;
	}
	if(steps) {
		printstate(m);
		printf("Completed in %d steps.\n", steps);
	}
}

void
push(Machine *m, char *w)
{
	Fraction f;
	if(!m->acc.den) {
		if(sscanf(w, "%u", &m->acc.num) > 0)
			m->acc.den = 1;
		return;
	}
	if(sscanf(w, "%u/%u", &f.num, &f.den) > 0)
		m->program[m->len++] = f;
}

Machine m;

int
main(void)
{
	int len = 0;
	char c, word[64];
	while((c = fgetc(stdin)) != EOF) {
		if(c == ' ' || c == '\n') {
			word[len] = '\0';
			len = 0;
			push(&m, word);
		} else
			word[len++] = c;
		if(c == '\n')
			break;
	}
	printstate(&m);
	run(&m);
	return 0;
}
— Submit an edit to fractran.c.txt(123 lines)
A common man marvels at uncommon things; a wise man marvels at the commonplace.
—Confucius

incoming(3): firth fractran language