path: root/std/Number.bruijn

# MIT License, Copyright (c) 2022 Marvin Borner
# Heavily inspired by the works of T.Æ. Mogensen (see refs in README)

:import std/Combinator .

:import std/Pair .

:import std/Logic .

# negative trit indicating coeffecient of (-1)
trit-neg [[[2]]]

# returns whether a trit is negative
trit-neg? [0 true false false]

# positive trit indicating coeffecient of (+1)
trit-pos [[[1]]]

# returns whether a trit is positive
trit-pos? [0 false true false]

# zero trit indicating coeffecient of 0
trit-zero [[[0]]]

# returns whether a trit is zero
trit-zero? [0 false false true]

:test (trit-neg? trit-neg) (true)
:test (trit-neg? trit-pos) (false)
:test (trit-neg? trit-zero) (false)
:test (trit-pos? trit-neg) (false)
:test (trit-pos? trit-pos) (true)
:test (trit-pos? trit-zero) (false)
:test (trit-zero? trit-neg) (false)
:test (trit-zero? trit-pos) (false)
:test (trit-zero? trit-zero) (true)

# shifts a negative trit into a balanced ternary number
up-neg [[[[[2 (4 3 2 1 0)]]]]]

^<( up-neg

:test (^<(+0)) ((-1))
:test (^<(-1)) ((-4))
:test (^<(+42)) ((+125))

# shifts a positive trit into a balanced ternary number
up-pos [[[[[1 (4 3 2 1 0)]]]]]

^>( up-pos

:test (^>(+0)) ((+1))
:test (^>(-1)) ((-2))
:test (^>(+42)) ((+127))

# shifts a zero trit into a balanced ternary number
up-zero [[[[[0 (4 3 2 1 0)]]]]]

^=( up-zero

:test (^=(+0)) ([[[[0 3]]]])
:test (^=(+1)) ((+3))
:test (^=(+42)) ((+126))

# shifts a specified trit into a balanced ternary number
up [[[[[[5 2 1 0 (4 3 2 1 0)]]]]]]

:test (up trit-neg (+42)) (^<(+42))
:test (up trit-pos (+42)) (^>(+42))
:test (up trit-zero (+42)) (^=(+42))

# shifts the least significant trit out - basically div by 3
down [snd (0 z neg pos zero)]
	z (+0) : (+0)
	neg [0 [[(^<1) : 1]]]
	pos [0 [[(^>1) : 1]]]
	zero [0 [[(^=1) : 1]]]

# negates a balanced ternary number
negate [[[[[4 3 1 2 0]]]]]

-( negate

:test (-(+0)) ((+0))
:test (-(-1)) ((+1))
:test (-(+42)) ((-42))

# converts a balanced ternary number to a list of trits
list! [0 z neg pos zero]
	z [[0]]
	neg [trit-neg : 0]
	pos [trit-pos : 0]
	zero [trit-zero : 0]

# TODO: Tests!

# strips leading 0s from balanced ternary number
strip [fst (0 z neg pos zero)]
	z (+0) : true
	neg [0 [[(^<1) : false]]]
	pos [0 [[(^>1) : false]]]
	zero [0 [[(0 (+0) (^=1)) : 0]]]

~( strip

:test (~[[[[0 3]]]]) ((+0))
:test (~[[[[2 (0 (0 (0 (0 3))))]]]]) ((-1))
:test (~(+42)) ((+42))

# extracts least significant trit from balanced ternary numbers
lst [0 trit-zero [trit-neg] [trit-pos] [trit-zero]]

:test (lst (+0)) (trit-zero)
:test (lst (-1)) (trit-neg)
:test (lst (+1)) (trit-pos)
:test (lst (+42)) (trit-zero)

# extracts most significant trit from balanced ternary numbers
# TODO: Find a more elegant way to do this (and resolve list import loop?)
mst [fix (last (list! (~0)))]
	last Z [[empty? 0 [false] [empty? (snd 1) (fst 1) (2 (snd 1))] I]]
		empty? [0 [[[false]]] true]
	fix [((trit-neg? 0) || ((trit-pos? 0) || (trit-zero? 0))) 0 trit-zero]

:test (mst (+0)) (trit-zero)
:test (mst (-1)) (trit-neg)
:test (mst (+1)) (trit-pos)
:test (mst (+42)) (trit-pos)

# returns whether balanced ternary number is negative
negative? [trit-neg? (mst 0)]

<?( negative?

:test (<?(+0)) (false)
:test (<?(-1)) (true)
:test (<?(+1)) (false)
:test (<?(+42)) (false)

# returns whether balanced ternary number is positive
positive? [trit-pos? (mst 0)]

>?( positive?

:test (>?(+0)) (false)
:test (>?(-1)) (false)
:test (>?(+1)) (true)
:test (>?(+42)) (true)

# checks whether balanced ternary number is zero
zero? [0 true [false] [false] I]

=?( zero?

:test (=?(+0)) (true)
:test (=?(-1)) (false)
:test (=?(+1)) (false)
:test (=?(+42)) (false)

# converts the normal balanced ternary representation into abstract
# -> the abstract representation is used in add/sub/mul
abstract! [0 z neg pos zero]
	z (+0)
	neg [[[[[2 4]]]]]
	pos [[[[[1 4]]]]]
	zero [[[[[0 4]]]]]

:test (abstract! (-3)) ([[[[0 [[[[2 [[[[3]]]]]]]]]]]])
:test (abstract! (+0)) ([[[[3]]]])
:test (abstract! (+3)) ([[[[0 [[[[1 [[[[3]]]]]]]]]]]])

# converts the abstracted balanced ternary representation back to normal
# using ω to solve recursion
normal! ω rec
	rec [[0 (+0) [^<([3 3 0] 0)] [^>([3 3 0] 0)] [^=([3 3 0] 0)]]]

:test (normal! [[[[3]]]]) ((+0))
:test (normal! (abstract! (+42))) ((+42))
:test (normal! (abstract! (-42))) ((-42))

# checks whether two balanced ternary numbers are equal
# smaller numbers should be second argument (performance)
# -> ignores leading 0s!
eq? [[abs 1 (abstract! 0)]]
	abs [0 z neg pos zero]
		z [zero? (normal! 0)]
		neg [[0 false [2 0] [false] [false]]]
		pos [[0 false [false] [2 0] [false]]]
		zero [[0 (1 0) [false] [false] [2 0]]]

(=?) eq?

:test ((-42) =? (-42)) (true)
:test ((-1) =? (-1)) (true)
:test ((-1) =? (+0)) (false)
:test ((+0) =? (+0)) (true)
:test ((+1) =? (+0)) (false)
:test ((+1) =? (+1)) (true)
:test ((+42) =? (+42)) (true)
:test ([[[[(1 (0 (0 (0 (0 3)))))]]]] =? (+1)) (true)

# I believe Mogensen's Paper has an error in its inc/dec/add/mul/eq definitions.
# They use 3 instead of 2 abstractions in the functions, also we use switched
# +/0 in comparison to their implementation, yet the order of neg/pos/zero is
# the same. Something's weird.

# adds (+1) to a balanced ternary number (can introduce leading 0s)
inc [snd (0 z neg pos zero)]
	z (+0) : (+1)
	neg [0 [[(^<1) : (^=1)]]]
	zero [0 [[(^=1) : (^>1)]]]
	pos [0 [[(^>1) : (^<0)]]]

++( inc

# adds (+1) to a balanced ternary number and strips leading 0s
ssinc strip . inc

:test ((++(-42)) =? (-41)) (true)
:test ((++(-1)) =? (+0)) (true)
:test ((++(+0)) =? (+1)) (true)
:test ((++(++(++(++(++(+0)))))) =? (+5)) (true)
:test ((++(+42)) =? (+43)) (true)

# subs (+1) from a balanced ternary number (can introduce leading 0s)
dec [snd (0 dec-z dec-neg dec-pos dec-zero)]
	dec-z (+0) : (-1)
	dec-neg [0 [[(^<1) : (^>0)]]]
	dec-zero [0 [[(^=1) : (^<1)]]]
	dec-pos [0 [[(^>1) : (^=1)]]]

--( dec

# subs (+1) from a balanced ternary number and strips leading 0s
sdec strip . dec

:test ((--(-42)) =? (-43)) (true)
:test ((--(+0)) =? (-1)) (true)
:test ((--(--(--(--(--(+5)))))) =? (+0)) (true)
:test ((--(+1)) =? (+0)) (true)
:test ((--(+42)) =? (+41)) (true)

# adds two balanced ternary numbers (can introduce leading 0s)
# smaller numbers should be second argument (performance)
add [[abs 1 (abstract! 0)]]
	abs [c (0 z a-neg a-pos a-zero)]
		b-neg [1 (^>(3 0 trit-neg)) (^=(3 0 trit-zero)) (^<(3 0 trit-zero))]
		b-zero [up 1 (3 0 trit-zero)]
		b-pos [1 (^=(3 0 trit-zero)) (^<(3 0 trit-pos)) (^>(3 0 trit-zero))]
		a-neg [[[1 (b-neg 1) b-neg' b-zero b-neg]]]
			b-neg' [1 (^=(3 0 trit-neg)) (^<(3 0 trit-zero)) (^>(3 0 trit-neg))]
		a-pos [[[1 (b-pos 1) b-zero b-pos' b-pos]]]
			b-pos' [1 (^>(3 0 trit-zero)) (^=(3 0 trit-pos)) (^<(3 0 trit-pos))]
		a-zero [[[1 (b-zero 1) b-neg b-pos b-zero]]]
		z [[0 (--(normal! 1)) (++(normal! 1)) (normal! 1)]]
		c [[1 0 trit-zero]]

(+) add

# adds two balanced ternary numbers and strips leading 0s
sadd strip ... add

:test (((-42) + (-1)) =? (-43)) (true)
:test (((-5) + (+6)) =? (+1)) (true)
:test (((-1) + (+0)) =? (-1)) (true)
:test (((+0) + (+0)) =? (+0)) (true)
:test (((+1) + (+2)) =? (+3)) (true)
:test (((+42) + (+1)) =? (+43)) (true)

# subs two balanced ternary numbers (can introduce leading 0s)
# smaller numbers should be second argument (performance)
sub [[1 + -0]]

(-) sub

# subs two balanced ternary numbers and strips leading 0s
ssub strip ... sub

:test (((-42) - (-1)) =? (-41)) (true)
:test (((-5) - (+6)) =? (-11)) (true)
:test (((-1) - (+0)) =? (-1)) (true)
:test (((+0) - (+0)) =? (+0)) (true)
:test (((+1) - (+2)) =? (-1)) (true)
:test (((+42) - (+1)) =? (+41)) (true)

# returns whether number is greater than other number
# smaller numbers should be second argument (performance)
gre? [[positive? (sub 1 0)]]

(>?) gre?

:test ((+1) >? (+2)) (false)
:test ((+2) >? (+2)) (false)
:test ((+3) >? (+2)) (true)

# returns whether number is less than other number
# smaller numbers should be second argument (performance)
les? [[negative? (sub 1 0)]]

(<?) les?

:test ((+1) <? (+2)) (true)
:test ((+2) <? (+2)) (false)
:test ((+3) <? (+2)) (false)

# returns whether number is less than or equal to other number
# smaller numbers should be second argument (performance)
leq? [[not (gre? 1 0)]]

(<=?) leq?

:test ((+1) <=? (+2)) (true)
:test ((+2) <=? (+2)) (true)
:test ((+3) <=? (+2)) (false)

# returns whether number is greater than or equal to other number
# smaller numbers should be second argument (performance)
geq? [[not (les? 1 0)]]

(>=?) geq?

:test ((+1) >=? (+2)) (false)
:test ((+2) >=? (+2)) (true)
:test ((+3) >=? (+2)) (true)

# muls two balanced ternary numbers (can introduce leading 0s)
mul [[1 (+0) neg pos zero]]
	neg [(^=0) - 1]
	pos [(^=0) + 1]
	zero [^=0]

(*) mul

smul strip ... mul

:test (((+42) * (+0)) =? (+0)) (true)
:test (((-1) * (+42)) =? (-42)) (true)
:test (((+3) * (+11)) =? (+33)) (true)
:test (((+42) * (-4)) =? (-168)) (true)

# factorial function
fac Z [[(0 <? (+2)) (+1) (0 * (1 --0))]]

:test ((fac (+3)) =? (+6)) (true)

# fibonacci sequence
fib Z [[(0 <? (+2)) 0 ((1 (0 - (+1))) + (1 (0 - (+2))))]]

# tests too slow but works :P