diff options
Diffstat (limited to 'std/Number.bruijn')
| -rw-r--r-- | std/Number.bruijn | 143 |
1 files changed, 76 insertions, 67 deletions
diff --git a/std/Number.bruijn b/std/Number.bruijn index ae4a3ac..3a2efe9 100644 --- a/std/Number.bruijn +++ b/std/Number.bruijn @@ -8,22 +8,22 @@ :import std/Logic . # negative trit indicating coeffecient of (-1) -t⁻ [[[2]]] +t⁻ [[[2]]] ⧗ Trit # returns true if a trit is negative -t⁻? [0 true false false] +t⁻? [0 true false false] ⧗ Trit → Boolean # positive trit indicating coeffecient of (+1) -t⁺ [[[1]]] +t⁺ [[[1]]] ⧗ Trit # returns true if a trit is positive -t⁺? [0 false true false] +t⁺? [0 false true false] ⧗ Trit → Boolean # zero trit indicating coeffecient of 0 -t⁰ [[[0]]] +t⁰ [[[0]]] ⧗ Trit # returns true if a trit is zero -t⁰? [0 false false true] +t⁰? [0 false false true] ⧗ Trit → Boolean :test (t⁻? t⁻) (true) :test (t⁻? t⁺) (false) @@ -36,28 +36,28 @@ t⁰? [0 false false true] :test (t⁰? t⁰) (true) # shifts a negative trit into a balanced ternary number -↑⁻‣ [[[[[2 (4 3 2 1 0)]]]]] +↑⁻‣ [[[[[2 (4 3 2 1 0)]]]]] ⧗ Number → Number :test (↑⁻(+0)) ((-1)) :test (↑⁻(-1)) ((-4)) :test (↑⁻(+42)) ((+125)) # shifts a positive trit into a balanced ternary number -↑⁺‣ [[[[[1 (4 3 2 1 0)]]]]] +↑⁺‣ [[[[[1 (4 3 2 1 0)]]]]] ⧗ Number → Number :test (↑⁺(+0)) ((+1)) :test (↑⁺(-1)) ((-2)) :test (↑⁺(+42)) ((+127)) # shifts a zero trit into a balanced ternary number -↑⁰‣ [[[[[0 (4 3 2 1 0)]]]]] +↑⁰‣ [[[[[0 (4 3 2 1 0)]]]]] ⧗ Number → Number :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)]]]]]] +up [[[[[[5 2 1 0 (4 3 2 1 0)]]]]]] ⧗ Trit → Number → Number :test (up t⁻ (+42)) (↑⁻(+42)) :test (up t⁺ (+42)) (↑⁺(+42)) @@ -65,10 +65,10 @@ up [[[[[[5 2 1 0 (4 3 2 1 0)]]]]]] # infinity # WARNING: using this mostly results in undefined behavior! (TODO?) -infty z [[[[[1 (4 1)]]]]] +infty z [[[[[1 (4 1)]]]]] ⧗ Number # negates a balanced ternary number -negate [[[[[4 3 1 2 0]]]]] +negate [[[[[4 3 1 2 0]]]]] ⧗ Number → Number -‣ negate @@ -77,7 +77,7 @@ negate [[[[[4 3 1 2 0]]]]] :test (-(+42)) ((-42)) # converts a balanced ternary number to a list of trits -list! [0 z a⁻ a⁺ a⁰] +list! [0 z a⁻ a⁺ a⁰] ⧗ Number → List z [[0]] a⁻ [t⁻ : 0] a⁺ [t⁺ : 0] @@ -86,7 +86,7 @@ list! [0 z a⁻ a⁺ a⁰] # TODO: Tests! # strips leading 0s from balanced ternary number -strip [^(0 z a⁻ a⁺ a⁰)] +strip [^(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number z (+0) : true a⁻ [0 [[↑⁻1 : false]]] a⁺ [0 [[↑⁺1 : false]]] @@ -99,15 +99,15 @@ strip [^(0 z a⁻ a⁺ a⁰)] :test (%(+42)) ((+42)) # extracts least significant trit from balanced ternary numbers -lst [0 t⁰ [t⁻] [t⁺] [t⁰]] +lst [0 t⁰ [t⁻] [t⁺] [t⁰]] ⧗ Number → Trit :test (lst (-1)) (t⁻) :test (lst (+0)) (t⁰) :test (lst (+1)) (t⁺) :test (lst (+42)) (t⁰) -# checks true if balanced ternary number is zero -zero? [0 true [false] [false] i] +# returns true if balanced ternary number is zero +zero? [0 true [false] [false] i] ⧗ Number → Boolean =?‣ zero? @@ -116,11 +116,21 @@ zero? [0 true [false] [false] i] :test (=?(+1)) (false) :test (=?(+42)) (false) +# returns true if balanced ternary number is not +not-zero? [0 false [true] [true] i] ⧗ Number → Boolean + +≠?‣ not-zero? + +:test (≠?(+0)) (false) +:test (≠?(-1)) (true) +:test (≠?(+1)) (true) +:test (≠?(+42)) (true) + # extracts most significant trit from balanced ternary numbers # <~>/<>? are hardcoded because list import would be recursive (TODO?) # while this looks incredibly inefficient it's actually fairly fast because laziness # TODO: find way of removing requirement of stripping first -mst [=?0 t⁰ ^(<~>(list! %0))] +mst [=?0 t⁰ ^(<~>(list! %0))] ⧗ Number → Trit <~>‣ z [[[[<>?0 1 (3 2 (2 1 ^0) ~0)]]]] f false <>?‣ [0 [[[false]]] true] @@ -130,7 +140,7 @@ mst [=?0 t⁰ ^(<~>(list! %0))] :test (mst (+42)) (t⁺) # returns true if balanced ternary number is negative -negative? [t⁻? (mst 0)] +negative? [t⁻? (mst 0)] ⧗ Number → Boolean <?‣ negative? @@ -140,7 +150,7 @@ negative? [t⁻? (mst 0)] :test (<?(+42)) (false) # returns true if balanced ternary number is positive -positive? [t⁺? (mst 0)] +positive? [t⁺? (mst 0)] ⧗ Number → Boolean >?‣ positive? @@ -152,7 +162,7 @@ positive? [t⁺? (mst 0)] # converts the normal balanced ternary representation into abstract # infinity can't be abstracted in finite time # → the abstract representation is used in eq?/add/sub/mul -abstract! [0 z a⁻ a⁺ a⁰] +abstract! [0 z a⁻ a⁺ a⁰] ⧗ Number → AbstractNumber z (+0) a⁻ [[[[[2 4]]]]] a⁺ [[[[[1 4]]]]] @@ -165,7 +175,7 @@ abstract! [0 z a⁻ a⁺ a⁰] :test (→^(+3)) ([[[[0 [[[[1 [[[[3]]]]]]]]]]]]) # converts the abstracted balanced ternary representation back to normal -normal! ω [[0 z a⁻ a⁺ a⁰]] +normal! ω [[0 z a⁻ a⁺ a⁰]] ⧗ AbstractNumber → Number z (+0) a⁻ [↑⁻([3 3 0] 0)] a⁺ [↑⁺([3 3 0] 0)] @@ -177,10 +187,10 @@ normal! ω [[0 z a⁻ a⁺ a⁰]] :test (→_(→^(+42))) ((+42)) :test (→_(→^(-42))) ((-42)) -# checks whether two balanced ternary numbers are equal +# returns true if two balanced ternary numbers are equal # larger numbers should be second argument (performance) # → ignores leading 0s! -eq? [[abs 1 →^0]] +eq? [[abs 1 →^0]] ⧗ Number → Number → Boolean abs [0 z a⁻ a⁺ a⁰] z [=?(→_0)] a⁻ [[0 false [2 0] [false] [false]]] @@ -189,9 +199,9 @@ eq? [[abs 1 →^0]] …=?… eq? -neq? not! ∘∘ eq? +not-eq? not! ∘∘ eq? ⧗ Number → Number → Boolean -…/=?… neq? +…≠?… not-eq? :test ((-42) =? (-42)) (true) :test ((-1) =? (-1)) (true) @@ -201,8 +211,8 @@ neq? not! ∘∘ eq? :test ((+1) =? (+1)) (true) :test ((+42) =? (+42)) (true) :test ([[[[(1 (0 (0 (0 (0 3)))))]]]] =? (+1)) (true) -:test ((+1) /=? (+0)) (true) -:test ((-42) /=? (+42)) (true) +:test ((+1) ≠? (+0)) (true) +:test ((-42) ≠? (+42)) (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 @@ -210,7 +220,7 @@ neq? not! ∘∘ eq? # the same. Something's weird. # adds (+1) to a balanced ternary number (can introduce leading 0s) -inc [~(0 z a⁻ a⁺ a⁰)] +inc [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number z (+0) : (+1) a⁻ [0 [[↑⁻1 : ↑⁰1]]] a⁺ [0 [[↑⁺1 : ↑⁻0]]] @@ -218,9 +228,6 @@ inc [~(0 z a⁻ a⁺ a⁰)] ++‣ 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) @@ -228,7 +235,7 @@ ssinc strip ∘ inc :test ((++(+42)) =? (+43)) (true) # subs (+1) from a balanced ternary number (can introduce leading 0s) -dec [~(0 z a⁻ a⁺ a⁰)] +dec [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number z (+0) : (-1) a⁻ [0 [[↑⁻1 : ↑⁺0]]] a⁺ [0 [[↑⁺1 : ↑⁰1]]] @@ -236,9 +243,6 @@ dec [~(0 z a⁻ a⁺ a⁰)] --‣ 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) @@ -247,7 +251,7 @@ sdec strip ∘ dec # adds two balanced ternary numbers (can introduce leading 0s) # second argument gets abstracted (performance) -add [[abs 1 →^0]] +add [[abs 1 →^0]] ⧗ Number → Number → Number abs [c (0 z a⁻ a⁺ a⁰)] b⁻ [1 ↑⁺(3 0 t⁻) ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁰)] b⁰ [up 1 (3 0 t⁰)] @@ -262,9 +266,6 @@ add [[abs 1 →^0]] …+… 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) @@ -274,13 +275,10 @@ sadd strip ∘∘ add # subs two balanced ternary numbers (can introduce leading 0s) # second argument gets abstracted (performance) -sub [[1 + -0]] +sub [[1 + -0]] ⧗ Number → Number → Number …-… 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) @@ -290,7 +288,7 @@ ssub strip ∘∘ sub # returns true if number is greater than other number # larger numbers should be second argument (performance) -gre? [[>?(1 - 0)]] +gre? [[>?(1 - 0)]] ⧗ Number → Number → Boolean …>?… gre? @@ -300,7 +298,7 @@ gre? [[>?(1 - 0)]] # returns true if number is less than other number # smaller numbers should be second argument (performance) -les? \gre? +les? \gre? ⧗ Number → Number → Boolean …<?… les? @@ -310,7 +308,7 @@ les? \gre? # returns true if number is less than or equal to other number # smaller numbers should be second argument (performance) -leq? [[¬(1 >? 0)]] +leq? [[¬(1 >? 0)]] ⧗ Number → Number → Boolean …≤?… leq? @@ -320,7 +318,7 @@ leq? [[¬(1 >? 0)]] # returns true if number is greater than or equal to other number # smaller numbers should be second argument (performance) -geq? \leq? +geq? \leq? ⧗ Number → Number → Boolean …≥?… geq? @@ -329,7 +327,7 @@ geq? \leq? :test ((+3) ≥? (+2)) (true) # negates a balanced ternary number if <0 -abs [<?0 -0 0] +abs [<?0 -0 0] ⧗ Number → Number |‣ abs @@ -337,24 +335,31 @@ abs [<?0 -0 0] :test (|(-1)) ((+1)) :test (|(+42)) ((+42)) +# apply a function n times to a value +# ~> substitute church numbers +apply z [[[rec]]] ⧗ Number → (a → a) → a → a + rec =?1 case-end case-apply + case-apply 0 ∘ (2 --1 0) + case-end i + +:test (apply (+5) ++‣ (+3)) ((+8)) + # muls two balanced ternary numbers (can introduce leading 0s) -mul [[1 z a⁻ a⁺ a⁰]] +mul [[1 z a⁻ a⁺ a⁰]] ⧗ Number → Number → Number z (+0) a⁻ [↑⁰0 - 1] a⁺ [↑⁰0 + 1] a⁰ [↑⁰0] -…*… mul - -smul strip ∘∘ mul +…⋅… mul -:test (((+42) * (+0)) =? (+0)) (true) -:test (((-1) * (+42)) =? (-42)) (true) -:test (((+3) * (+11)) =? (+33)) (true) -:test (((+42) * (-4)) =? (-168)) (true) +:test (((+42) ⋅ (+0)) =? (+0)) (true) +:test (((-1) ⋅ (+42)) =? (-42)) (true) +:test (((+3) ⋅ (+11)) =? (+33)) (true) +:test (((+42) ⋅ (-4)) =? (-168)) (true) # divs a balanced ternary number by three (rshifts least significant trit) -div³ [~(0 z a⁻ a⁺ a⁰)] +div³ [~(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number z (+0) : (+0) a⁻ [0 [[↑⁻1 : 1]]] a⁺ [0 [[↑⁺1 : 1]]] @@ -367,7 +372,7 @@ div³ [~(0 z a⁻ a⁺ a⁰)] :test (/³(+5)) ((+2)) # divs a balanced ternary number by two (essentially binary >>1) -div² [z [[[[rec]]]] (+0) 0 0] +div² [z [[[[rec]]]] (+0) 0 0] ⧗ Number → Number rec =?1 case-end case-div case-div 3 /³(2 + 0) /³1 0 case-end 2 @@ -381,7 +386,7 @@ div² [z [[[[rec]]]] (+0) 0 0] # manually counts how many times a balanced ternary number fits into another one # TODO: quadratic approximation? # TODO: fix for negative numbers -brute-div \[z [[[[[rec]]]]] (+0) 0 0] +brute-div \[z [[[[[rec]]]]] (+0) 0 0] ⧗ Number → Number → Number rec (2 >? 0) case-end case-count case-count 4 ++3 (2 + 1) 1 0 case-end 3 @@ -393,16 +398,20 @@ brute-div \[z [[[[[rec]]]]] (+0) 0 0] :test ((+4) /! (+5)) ((+0)) # TODO: fix for negative numbers -brute-mod \[z [[[[[rec]]]]] (+0) 0 0] +brute-mod \[z [[[[[rec]]]]] (+0) 0 0] ⧗ Number → Number → Number rec (2 >? 0) case-end case-count case-count 4 ++3 (2 + 1) 1 0 - case-end 0 - (3 * 1) + case-end 0 - (3 ⋅ 1) …%!… brute-mod # finds quotient and remainder using long division # WARNING: don't use; incorrect and slow -quot-rem [[z [[[[rec]]]] ((+1) : (+0)) 1 0]] +# TODO: faster algorithm +# dividend -> divisor -> (quot, rem) +# 0 divisor, 1 dividend, 2 (quot, rem) +# align: (quot, divisor) +quot-rem [[z [[[[rec]]]] ((+1) : (+0)) 1 0]] ⧗ Number → Number → (Pair Number Number) rec (1 =? 0) case-eq ((1 <? 0) case-les case-div) case-div calc (z [[[align]]] ^2 0) align (0 ≤? 4) (1 : 0) (2 ↑⁰1 ↑⁰0) @@ -413,18 +422,18 @@ quot-rem [[z [[[[rec]]]] ((+1) : (+0)) 1 0]] # divs two balanced ternary numbers # WARNING: don't use; incorrect and slow -div ^‣ ∘∘ quot-rem +div ^‣ ∘∘ quot-rem ⧗ Number → Number …/… div # returns remainder of integer division # WARNING: don't use; incorrect and slow -mod ~‣ ∘∘ quot-rem +mod ~‣ ∘∘ quot-rem ⧗ Number → Number …%… mod # returns max number of two -max [[(1 ≤? 0) 0 1]] +max [[(1 ≤? 0) 0 1]] ⧗ Number → Number → Number # returns min number of two -min [[(1 ≤? 0) 1 0]] +min [[(1 ≤? 0) 1 0]] ⧗ Number → Number → Number |