Balanced ternary: Difference between revisions
m
→{{header|11l}}: X.throw
Alextretyak (talk | contribs) (→{{header|11l}}: Static type variables and static methods are supported now) |
Alextretyak (talk | contribs) m (→{{header|11l}}: X.throw) |
||
| (13 intermediate revisions by 7 users not shown) | |||
Line 29:
{{trans|Python}}
<syntaxhighlight lang="11l">
. -:str2dig = [‘+’ = 1, ‘-’ = -1, ‘0’ = 0]
. -:dig2str = [1 = ‘+’, -1 = ‘-’, 0 = ‘0’]
. -:table = [(0, -1), (1, -1), (-1, 0), (0, 0), (1, 0), (-1, 1), (0, 1)]
[Int] digits
Line 45 ⟶ 40:
.digits = copy(inp)
E
X.throw ValueError(‘BalancedTernary: Wrong input digits.’)
F :
R BalancedTernary(reversed(inp).map(c -> .:str2dig[c]))
. F :int2ternary(n)
I n == 0
R [Int]()
V n3 = ((n % 3) + 3) % 3
I n3 == 0 {R [0] [+] .:int2ternary
I n3 == 1 {R [1] [+] .:int2ternary
I n3 == 2 {R [-1] [+] .:int2ternary
X.throw RuntimeError(‘’)
F :from_int(inp)
R BalancedTernary(.:int2ternary(inp))
F to_int()
Line 64 ⟶ 65:
R reversed(.digits).map(d -> .:dig2str[d]).join(‘’)
. F :neg(digs)
R digs.map(d -> -d)
Line 70 ⟶ 71:
R BalancedTernary(.:neg(.digits))
. F :add(a, b, =c = 0)
I !(!a.empty & !b.empty)
I c == 0
Line 106 ⟶ 107:
R BalancedTernary(_mul(.digits, b.digits))
V a = BalancedTernary.from_str(‘+-0++0+’)
print(‘a: ’a.to_int()‘ ’a)
V b =
print(‘b: ’b.to_int()‘ ’b)
V c =
print(‘c: ’c.to_int()‘ ’c)
Line 839 ⟶ 835:
65 : +-++-
-262023 : ----0+--0++0</pre>
=={{header|Bruijn}}==
The default syntax sugar for numbers in bruijn is balanced ternary. The implementation of respective arithmetic operators is in <code>std/Number/Ternary</code> and <code>std/Math</code>. Converting between bases can be accomplished using <code>std/Number/Conversion</code>. The following is a library excerpt to show how to define the most common operators (succ,pred,add,sub,mul,eq) efficiently. They can be easily converted to the notation of pure lambda calculus (as originally by Torben Mogensen in "An Investigation of Compact and Efficient Number Representations in the Pure Lambda Calculus").
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/Logic .
:import std/Pair .
# negative trit indicating coefficient of (-1)
t⁻ [[[2]]]
# positive trit indicating coefficient of (+1)
t⁺ [[[1]]]
# zero trit indicating coefficient of 0
t⁰ [[[0]]]
# shifts a negative trit into a balanced ternary number
↑⁻‣ [[[[[2 (4 3 2 1 0)]]]]]
# shifts a positive trit into a balanced ternary number
↑⁺‣ [[[[[1 (4 3 2 1 0)]]]]]
# shifts a zero trit into a balanced ternary number
↑⁰‣ [[[[[0 (4 3 2 1 0)]]]]]
# shifts a specified trit into a balanced ternary number
…↑… [[[[[[5 2 1 0 (4 3 2 1 0)]]]]]]
# negates a balanced ternary number
-‣ [[[[[4 3 1 2 0]]]]]
# increments a balanced ternary number (can introduce leading 0s)
++‣ [~(0 z a⁻ a⁺ a⁰)]
z (+0) : (+1)
a⁻ &[[↑⁻1 : ↑⁰1]]
a⁺ &[[↑⁺1 : ↑⁻0]]
a⁰ &[[↑⁰1 : ↑⁺1]]
# decrements a balanced ternary number (can introduce leading 0s)
--‣ [~(0 z a⁻ a⁺ a⁰)]
z (+0) : (-1)
a⁻ &[[↑⁻1 : ↑⁺0]]
a⁺ &[[↑⁺1 : ↑⁰1]]
a⁰ &[[↑⁰1 : ↑⁻1]]
# converts the normal balanced ternary representation into abstract form
→^‣ [0 z a⁻ a⁺ a⁰]
z (+0)
a⁻ [[[[[2 4]]]]]
a⁺ [[[[[1 4]]]]]
a⁰ [[[[[0 4]]]]]
# converts the abstracted balanced ternary representation back to normal
→_‣ y [[0 z a⁻ a⁺ a⁰]]
z (+0)
a⁻ [↑⁻(2 0)]
a⁺ [↑⁺(2 0)]
a⁰ [↑⁰(2 0)]
# adds two balanced ternary numbers (can introduce leading 0s)
…+… [[[c (0 z a⁻ a⁺ a⁰)] 1 →^0]]
b⁻ [1 ↑⁺(3 0 t⁻) ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁰)]
b⁰ [1 ↑ (3 0 t⁰)]
b⁺ [1 ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁺) ↑⁺(3 0 t⁰)]
a⁻ [[[1 (b⁻ 1) b⁻' b⁰ b⁻]]]
b⁻' [1 ↑⁰(3 0 t⁻) ↑⁻(3 0 t⁰) ↑⁺(3 0 t⁻)]
a⁺ [[[1 (b⁺ 1) b⁰ b⁺' b⁺]]]
b⁺' [1 ↑⁺(3 0 t⁰) ↑⁰(3 0 t⁺) ↑⁻(3 0 t⁺)]
a⁰ [[[1 (b⁰ 1) b⁻ b⁺ b⁰]]]
z [[0 --(→_1) ++(→_1) →_1]]
c [[1 0 t⁰]]
# subtracts two balanced ternary numbers (can introduce leading 0s)
…-… [[1 + -0]]
# multiplicates two balanced ternary numbers (can introduce leading 0s)
…⋅… [[1 z a⁻ a⁺ a⁰]]
z (+0)
a⁻ [↑⁰0 - 1]
a⁺ [↑⁰0 + 1]
a⁰ [↑⁰0]
# true if balanced ternary number is zero
=?‣ [0 true [false] [false] i]
# true if two balanced ternary numbers are equal
# → ignores leading 0s!
…=?… [[[0 z a⁻ a⁺ a⁰] 1 →^0]]
z [=?(→_0)]
a⁻ [[0 false [2 0] [false] [false]]]
a⁺ [[0 false [false] [2 0] [false]]]
a⁰ [[0 (1 0) [false] [false] [2 0]]]
main [[0]]
# --- tests/examples ---
:test ((-42) + (-1) =? (-43)) (true)
:test ((+1) + (+2) =? (+3)) (true)
:test ((-42) - (-1) =? (-41)) (true)
:test ((+1) - (+2) =? (-1)) (true)
:test ((-1) ⋅ (+42) =? (-42)) (true)
:test ((+3) ⋅ (+11) =? (+33)) (true)
</syntaxhighlight>
=={{header|C}}==
Line 3,267 ⟶ 3,369:
result= ----0+--0++0 -262023
</pre>
=={{header|jq}}==
{{Works with|jq}}
'''Works with gojq, the Go implementation of jq'''
'''Adapted from [[#Wren|Wren]]'''
<syntaxhighlight lang="jq">
### Generic utilities
# Emit a stream of the constituent characters of the input string
def chars: explode[] | [.] | implode;
# Flip "+" and "-" in the input string, and change other characters to 0
def flip:
{"+": "-", "-": "+"} as $t
| reduce chars as $c (""; . + ($t[$c] // "0") );
### Balanced ternaries (BT)
# Input is assumed to be an integer (use `new` if checking is required)
def toBT:
# Helper - input should be an integer
def mod3:
if . > 0 then . % 3
else ((. % 3) + 3) % 3
end;
if . < 0 then - . | toBT | flip
else if . == 0 then ""
else mod3 as $rem
| if $rem == 0 then (. / 3 | toBT) + "0"
elif $rem == 1 then (. / 3 | toBT) + "+"
else ((. + 1) / 3 | toBT) + "-"
end
end
| sub("^00*";"")
| if . == "" then "0" end
end ;
# Input: BT
def integer:
. as $in
| length as $len
| { sum: 0,
pow: 1 }
| reduce range (0;$len) as $i (.;
$in[$len-$i-1: $len-$i] as $c
| (if $c == "+" then 1 elif $c == "-" then -1 else 0 end) as $digit
| if $digit != 0 then .sum += $digit * .pow else . end
| .pow *= 3 )
| .sum ;
# If the input is a string, check it is a valid BT, and trim leading 0s;
# if the input is an integer, convert it to a BT;
# otherwise raise an error.
def new:
if type == "string" and all(chars; IN("0", "+", "-"))
then sub("^00*"; "") | if . == "" then "0" end
elif type == "number" and trunc == .
then toBT
else "'new' given invalid input: \(.)" | error
end;
# . + $b
def plus($b):
# Helper functions:
def at($i): .[$i:$i+1];
# $a and $b should each be "0", "+" or "-"
def addDigits2($a; $b):
if $a == "0" then $b
elif $b == "0" then $a
elif $a == "+"
then if $b == "+" then "+-" else "0" end
elif $b == "+" then "0" else "-+"
end;
def addDigits3($a; $b; $carry):
addDigits2($a; $b) as $sum1
| addDigits2($sum1[-1:]; $carry) as $sum2
| if ($sum1|length) == 1
then $sum2
elif ($sum2|length) == 1
then $sum1[0:1] + $sum2
else $sum1[0:1]
end;
{ longer: (if length > ($b|length) then . else $b end),
shorter: (if length > ($b|length) then $b else . end) }
| until ( (.shorter|length) >= (.longer|length); .shorter = "0" + .shorter )
| .a = .longer
| .b = .shorter
| .carry = "0"
| .sum = ""
| reduce range(0; .a|length) as $i (.;
( (.a|length) - $i - 1) as $place
| addDigits3(.a | at($place); .b | at($place); .carry) as $digisum
| .carry = (if ($digisum|length) != 1 then $digisum[0:1] else "0" end)
| .sum = $digisum[-1:] + .sum )
| .carry + .sum
| new;
def minus: flip;
# . - $b
def minus($b): plus($b | flip);
def mult($b):
(1 | new) as $one
| (0 | new) as $zero
| { a: .,
$b,
mul: $zero,
flipFlag: false }
| if .b[0:1] == "-" # i.e. .b < 0
then .b |= minus
| .flipFlag = true
end
| .i = $one
| .in = 1
| (.b | integer) as $bn
| until ( .in > $bn;
.a as $a
| .mul |= plus($a)
| .i |= plus($one)
| .in += 1 )
| if .flipFlag then .mul | minus else .mul end ;
### Illustration
def a: "+-0++0+";
def b: -436 | new;
def c: "+-++-";
(a | integer) as $an
| (b | integer) as $bn
| (c | integer) as $cn
| ($an * ($bn - $cn)) as $in
| (a | mult( (b | minus(c)))) as $i
| "a = \($an)",
"b = \($bn)",
"c = \($cn)",
"a * (b - c) = \($i) ~ \($in) => \($in|new)"
</syntaxhighlight>
{{output}}
<pre>
a = 523
b = -436
c = 65
a * (b - c) = ----0+--0++0 ~ -262023 => ----0+--0++0
</pre>
Line 3,365 ⟶ 3,620:
a * (b - c): -262023, ----0+--0++0</pre>
=={{header|Koka}}==
Based on the OCaml version
<syntaxhighlight lang="koka">
type btdigit
Pos
Zero
Neg
alias btern = list<btdigit>
fun to_string(n: btern): string
join(
n.reverse.map fn(d)
match d
Pos -> "+"
Zero -> "0"
Neg -> "-"
)
fun from_string(s: string): exn btern
var sl := Nil
s.foreach fn(c)
match c
'+' -> sl := Cons(Pos, sl)
'0' -> sl := Cons(Zero, sl)
'-' -> sl := Cons(Neg, sl)
_ -> throw("Invalid Character")
sl
fun to_int(n: btern): int
match n
Nil -> 0
Cons(Zero, Nil) -> 0
Cons(Pos, rst) -> 1+3*rst.to_int
Cons(Neg, rst) -> -1+3*rst.to_int
Cons(Zero, rst) -> 3*rst.to_int
fun from_int(n: int): <exn> btern
if n == 0 then [] else
match n % 3
0 -> Cons(Zero, from_int((n/3).unsafe-decreasing))
1 -> Cons(Pos, from_int(((n - 1)/3).unsafe-decreasing))
2 -> Cons(Neg, from_int(((n+1)/3).unsafe-decreasing))
_ -> throw("Impossible")
fun (+)(n1: btern, n2: btern): <exn,div> btern
match (n1, n2)
([], a) -> a
(a, []) -> a
(Cons(Pos, t1), Cons(Neg, t2)) ->
val sum = t1 + t2
if sum.is-nil then [] else Cons(Zero, sum)
(Cons(Neg, t1), Cons(Pos, t2)) ->
val sum = t1 + t2
if sum.is-nil then [] else Cons(Zero, sum)
(Cons(Zero, t1), Cons(Zero, t2)) ->
val sum = t1 + t2
if sum.is-nil then [] else Cons(Zero, sum)
(Cons(Pos, t1), Cons(Pos, t2)) -> Cons(Neg, t1 + t2 + [Pos])
(Cons(Neg, t1), Cons(Neg, t2)) -> Cons(Pos, t1 + t2 + [Neg])
(Cons(Zero, t1), Cons(h, t2)) -> Cons(h, t1 + t2)
(Cons(h, t1), Cons(Zero, t2)) -> Cons(h, t1 + t2)
_ -> throw("Impossible")
fun neg(n: btern)
n.map fn(d)
match d
Pos -> Neg
Zero -> Zero
Neg -> Pos
fun (-)(n1: btern, n2: btern): <exn,div> btern
n1 + neg(n2)
fun (*)(n1, n2)
match n2
[] -> []
[Pos] -> n1
[Neg] -> n1.neg
(Cons(Pos, t)) -> Cons(Zero, t*n1) + n1
(Cons(Neg, t)) -> Cons(Zero, t*n1) - n1
(Cons(Zero, t)) -> Cons(Zero, t*n1)
fun main()
val a = "+-0++0+".from_string
val b = (-436).from_int
val c = "+-++-".from_string
val d = a * (b - c)
println("a = " ++ a.to_int.show ++ "\nb = " ++ b.to_string ++ "\nc = " ++ c.to_int.show ++ "\na * (b - c) = " ++ d.to_string ++ " = " ++ d.to_int.show )
</syntaxhighlight>
{{out}}
<pre>
a = 523
b = -++-0--
c = 65
a * (b - c) = ----0+--0++0 = -262023
</pre>
=={{header|Kotlin}}==
This is based on the Java entry. However, I've added 'BigInteger' support as this is a current requirement of the task description even though it's not actually needed to process the test case:
Line 3,881 ⟶ 4,234:
=={{header|Nim}}==
<syntaxhighlight lang="nim">import std/[strformat, tables]
type
Line 3,972 ⟶ 4,324:
func `*`*(a, b: BTernary): BTernary =
## Multiply
var start: BTernary
Line 5,185 ⟶ 5,537:
[a*(b-c)] ----0+--0++0 balanced ternary = -262023 (decimal)
</pre>
=={{header|RPL}}==
{{trans|Nim}}
{{works with|RPL|HP-48}}
« "-0+" SWAP POS 2 -
» '<span style="color:blue">CH→TR</span>' STO
« "-0+" SWAP 2 + DUP SUB
» '<span style="color:blue">TR→CH</span>' STO
« '''WHILE''' DUP SIZE OVER HEAD "0" == AND '''REPEAT''' TAIL '''END'''
» '<span style="color:blue">NOZEROS</span>' STO
« DUP SIZE → bt len
« 0
1 len '''FOR''' j
bt j DUP SUB <span style="color:blue">CH→TR</span>
3 len j - ^ * +
'''NEXT'''
» » '<span style="color:blue">BT→I</span>' STO
« DUP "" "0" IFTE
'''WHILE''' OVER '''REPEAT'''
OVER 3 MOD
1 ≤ LASTARG NEG IFTE <span style="color:grey>''@ convert 2 into -1''</span>
DUP <span style="color:blue">TR→CH</span> ROT - 3 / IP SWAP
'''END'''
SWAP DROP
» '<span style="color:blue">I→BT</span>' STO
« '''IF''' OVER SIZE OVER SIZE < '''THEN''' SWAP '''END'''
'''WHILE''' OVER SIZE OVER SIZE > '''REPEAT''' "0" SWAP + '''END'''
→ a b
« "" 0
a SIZE 1 '''FOR''' j
a j DUP SUB <span style="color:blue">CH→TR</span> + b j DUP SUB <span style="color:blue">CH→TR</span> +
'''IF''' DUP ABS 2 ≥ '''THEN'''
DUP 3 MOD 1 ≤ LASTARG NEG IFTE
SWAP SIGN
'''ELSE''' 0 '''END'''
SWAP <span style="color:blue">TR→CH</span> ROT + SWAP
-1 '''STEP'''
'''IF THEN''' LASTARG <span style="color:blue">TR→CH</span> SWAP + '''END'''
<span style="color:blue">NOZEROS</span>
» » '<span style="color:blue">ADDBT</span>' STO
« ""
1 3 PICK SIZE '''FOR''' j
OVER j DUP SUB
<span style="color:blue">CH→TR</span> NEG <span style="color:blue">TR→CH</span> +
'''NEXT'''
SWAP DROP
» '<span style="color:blue">NEGBT</span>' STO
« "" → a b shift
« "0"
a SIZE 1 '''FOR''' j
a j DUP SUB
'''IF''' DUP "0" ≠ '''THEN'''
b
'''IF''' SWAP "-" == '''THEN''' <span style="color:blue">NEGBT</span> '''END'''
'''END'''
shift + <span style="color:blue">ADDBT</span>
'shift' "0" STO+
-1 '''STEP'''
<span style="color:blue">NOZEROS</span>
» » '<span style="color:blue">MULBT</span>' STO
« "+-0++0+" -436 <span style="color:blue">I→BT</span> "+-++-" → a b c
« a <span style="color:blue">BT→I</span> b <span style="color:blue">BT→I</span> c <span style="color:blue">BT→I</span> 3 →LIST
a b c <span style="color:blue">NEGBT ADDBT MULBT</span>
» » '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
3: { 523 -436 65 }
2: "----0+--0++0"
1: -262023
</pre>
Line 6,018 ⟶ 6,448:
{{libheader|Wren-big}}
{{libheader|Wren-trait}}
<syntaxhighlight lang="
import "./trait" for Comparable
class BTernary is Comparable {
| |||