diff options
| author | Marvin Borner | 2024-03-13 01:47:46 +0100 |
|---|---|---|
| committer | Marvin Borner | 2024-03-13 01:47:46 +0100 |
| commit | 7fc946443adcef9224a3c672b5929a93489c8c93 (patch) | |
| tree | beb663a20e86233023383a5f369f82319ab0baaf /std | |
| parent | f0b836a87f25939f593632381409743623bf9cb7 (diff) | |
Added much faster division algorithm
Diffstat (limited to 'std')
| -rw-r--r-- | std/Number/Ternary.bruijn | 100 |
1 files changed, 65 insertions, 35 deletions
diff --git a/std/Number/Ternary.bruijn b/std/Number/Ternary.bruijn index 86f4593..8cf891f 100644 --- a/std/Number/Ternary.bruijn +++ b/std/Number/Ternary.bruijn @@ -37,36 +37,47 @@ t⁰? [0 false false true] ⧗ Trit → Boolean :test (t⁰? t⁺) (false) :test (t⁰? t⁰) (true) -# shifts a negative trit into a balanced ternary number +# lshifts a negative trit into a balanced ternary number ↑⁻‣ [[[[[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 +# lshifts a positive trit into a balanced ternary number ↑⁺‣ [[[[[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 +# lshifts a zero trit into a balanced ternary number ↑⁰‣ [[[[[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 +# lshifts a specified trit into a balanced ternary number …↑… [[[[[[5 2 1 0 (4 3 2 1 0)]]]]]] ⧗ Trit → Number → Number :test (t⁻ ↑ (+42)) (↑⁻(+42)) :test (t⁺ ↑ (+42)) (↑⁺(+42)) :test (t⁰ ↑ (+42)) (↑⁰(+42)) -# lshifts a zero trit into a balanced ternary number -←⁰‣ [[[[[4 (0 3) 2 1 0]]]]] +# lshifts balanced ternary number without pushing new trit +# basically removes mst or leading 0 +←‣ [^(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number + z (+0) : true + a⁻ &[[(0 (+0) ↑⁻1) : false]] + a⁺ &[[(0 (+0) ↑⁺1) : false]] + a⁰ &[[(0 (+0) ↑⁰1) : false]] + +:test (←(+3)) ([[[[0 3]]]]) +:test (←(+5)) ([[[[2 (2 3)]]]]) + +# rshifts a zero trit into a balanced ternary number (pad) +→⁰‣ [[[[[4 (0 3) 2 1 0]]]]] ⧗ Number → Number # infinity # WARNING: using this mostly results in undefined behavior! (TODO?) @@ -82,13 +93,14 @@ negate [[[[[4 3 1 2 0]]]]] ⧗ Number → Number :test (-(+42)) ((-42)) # converts a balanced ternary number to a list of trits -list! [0 z a⁻ a⁺ a⁰] ⧗ Number → List +number→trits [0 z a⁻ a⁺ a⁰] ⧗ Number → (List Trit) z [[0]] - a⁻ [t⁻ : 0] - a⁺ [t⁺ : 0] - a⁰ [t⁰ : 0] + a⁻ pair t⁻ + a⁺ pair t⁺ + a⁰ pair t⁰ -# TODO: Tests! +:test (number→trits (+0)) ([[0]]) +:test (number→trits (+5)) (t⁻ : (t⁻ : (t⁺ : [[0]]))) # strips leading 0s from a balanced ternary number strip [^(0 z a⁻ a⁺ a⁰)] ⧗ Number → Number @@ -134,9 +146,9 @@ lst [0 t⁰ [t⁻] [t⁺] [t⁰]] ⧗ Number → Trit # extracts most significant trit from a balanced ternary number mst* [B.get t⁰ (0 z a⁻ a⁺ a⁰)] ⧗ Number → Trit z B.empty - a⁻ [B.store! 0 t⁻] - a⁺ [B.store! 0 t⁺] - a⁰ [B.store! 0 t⁰] + a⁻ \B.store! t⁻ + a⁺ \B.store! t⁺ + a⁰ \B.store! t⁰ :test (mst* (-1)) (t⁻) :test (mst* (+0)) (t⁰) @@ -148,8 +160,8 @@ mst* [B.get t⁰ (0 z a⁻ a⁺ a⁰)] ⧗ Number → Trit # ignores leading 0s mst [B.get t⁰ (0 z a⁻ a⁺ a⁰)] ⧗ Number → Trit z B.empty - a⁻ [B.store! 0 t⁻] - a⁺ [B.store! 0 t⁺] + a⁻ \B.store! t⁻ + a⁺ \B.store! t⁺ a⁰ [0] :test (mst (-1)) (t⁻) @@ -463,47 +475,65 @@ ternary-search z [[[[rec]]]] ⧗ (Number → Number) → Number → Number → N :test ((ternary-search [-((0 - (+3)) ⋅ (0 - (+3)))] (+0) (+5)) =? (+3)) (true) -# finds quotient and remainder using binary search -# TODO: fix for numbers <=1 (case analysis, q,r<0) -quot-rem [[go --(binary-search [0 ⋅ 1 >? 2] (+0) 1)]] ⧗ Number → Number → (Pair Number Number) - go [0 : (2 - (1 ⋅ 0))] - # pads a ternary number with 0s until it's as long a another ternary number -pad y [[[(log3* 0) <? (log3* 1) (2 1 ←⁰0) 0]]] ⧗ Number → Number → Number +pad y [[[(log3* 0) <? (log3* 1) (2 1 →⁰0) 0]]] ⧗ Number → Number → Number # forces number to be exactly n trits long (either pad/trim) force [[[0 <? 2 pad trim] (log3* 0)]] ⧗ Number → Number - pad y [[[=?1 0 (2 --1 ←⁰0)]]] (2 - 0) 1 - trim y [[[=?1 0 (2 --1 /³0)]]] (0 - 2) 1 + pad z [[[=?1 0 (2 --1 →⁰0)]]] (2 - 0) 1 + trim z [[[=?1 0 (2 --1 ←0)]]] (0 - 2) 1 + +# lshifts after concat, given trit count +# TODO: reduce force +double-shift [[[[[left : right]] (force 2 1) (force 2 0)]]] + left force 4 ((mst* 0) ↑ (+0) + (↑⁰1)) + right force 4 ↑⁰0 +# efficient quotient/remainder implementation for balanced ternary # technique by Douglas W. Jones -# TODO: fix -quot-rem* [[[[z [[[[rec]]]] 1 (+0) 3]] ((max (log3 1) (log3 0)) ⋅ (+2)) 0]] - rec =?2 (0 : 1) ([[compare-case eq lt gt 1 (+0)]] rem' quo') - rem' force 5 ((mst* (force 5 0)) ↑ (+0) + ↑⁰1) - quo' force 5 ↑⁰0 +# algorithm originally intended for fixed-width numbers (=> ugly hacks with force+log3) +# TODO: remove the final `huh` correction step (probably some off-by-one bug?) +quot-rem [[[[[z [[[[rec]]]] 1 (+0) 4]]] <?0 (max (log3 1) (log3 0)) 0]] ⧗ Number → Number → (Pair Number Number) + rec =?2 huh (double-shift 5 1 0 [[compare-case eq gt lt 1 (+0)]]) + huh (>?1 ⋀? 6) ⋁? (<?1 ⋀? \6) (--0 : (1 + 7)) (0 : 1) eq 5 --4 1 0 - lt [(-0 >? 2) ⋁? ((-0 =? 2) ⋀? <?1) fix (6 --5 2 1)] (force 7 (1 + 6)) - fix 6 --5 0 --1 - gt [(-0 <? 2) ⋁? ((-0 =? 2) ⋀? >?1) fix (6 --5 2 1)] (force 7 (1 - 6)) - fix 6 --5 0 ++1 + gt [-0 <? 2 ⋁? (-0 =? 2 ⋀? >?1) fix (6 --5 2 1)] (8 add sub 1 6) + fix 6 --5 0 (9 dec inc 1) + lt [-0 >? 2 ⋁? (-0 =? 2 ⋀? <?1) fix (6 --5 2 1)] (8 sub add 1 6) + fix 6 --5 0 (9 inc dec 1) + +# finds quotient and remainder using binary search +# TODO: fix for numbers <=1 (case analysis, q,r<0) +quot-rem* [[go --(binary-search [0 ⋅ 1 >? 2] (+0) 1)]] ⧗ Number → Number → (Pair Number Number) + go [0 : (2 - (1 ⋅ 0))] # divs two balanced ternary numbers -div ^‣ ∘∘ quot-rem ⧗ Number → Number +div ^‣ ∘∘ quot-rem ⧗ Number → Number → Number …/… div :test ((+42) / (+4) =? (+10)) (true) :test ((+5) / (+3) =? (+1)) (true) +:test ((-5) / (-3) =? (+1)) (true) +:test ((-5) / (+3) =? (-2)) (true) +:test ((+5) / (-3) =? (-2)) (true) + +# bad mod implementation using repeated subtraction +mod* z [[[rec]]] ⧗ Number → Number → Number + rec [=?0 0 (<?0 2 (3 0 1))] (1 - 0) # returns remainder of integer division -mod ~‣ ∘∘ quot-rem ⧗ Number → Number +mod ~‣ ∘∘ quot-rem ⧗ Number → Number → Number …%… mod :test ((+42) % (+4) =? (+2)) (true) :test ((+7) % (+3) =? (+1)) (true) :test ((+8) % (+2) =? (+0)) (true) +:test ((+5) % (+3) =? (+2)) (true) +:test ((-5) % (-3) =? (-2)) (true) +:test ((-5) % (+3) =? (+1)) (true) +:test ((+5) % (-3) =? (-1)) (true) # returns true if the number is even (remainder mod 2 == 0) # TODO: faster solution (using tupling?) |