user
Balanced ternary is a way of representing numbers. Unlike the prevailing binary representation, a balanced ternary integer is in base 3, and each digit can have the values 1, 0, or −1.

Examples

Decimal 11 = 32 + 31 − 30, thus it can be written as "++−"

Decimal 6 = 32 − 31 + 0 × 30, thus it can be written as "+−0"

Task

Implement balanced ternary representation of integers with the following:

1. Support arbitrarily large integers, both positive and negative;
2. Provide ways to convert to and from text strings, using digits '+', '−' and '0' (unless you are already using strings to represent balanced ternary; but see requirement 5).
3. Provide ways to convert to and from native integer type (unless, improbably, your platform's native integer type *is* balanced ternary). If your native integers can't support arbitrary length, overflows during conversion must be indicated.
4. Provide ways to perform addition, negation and multiplication directly on balanced ternary integers; do *not* convert to native integers first.
5. Make your implementation efficient, with a reasonable definition of "efficient" (and with a reasonable definition of "reasonable").

**Test case** With balanced ternaries *a* from string "+−0++0+", *b* from native integer −436, *c* "+−++−":

* write out *a*, *b* and *c* in decimal notation;
* calculate *a* × (*b* − *c*), write out the result in both ternary and decimal notations.

**Note:** The pages generalised floating point addition and generalised floating point multiplication have code implementing arbitrary precision floating point balanced ternary.
assistant
(formerly Perl 6)

**Works with**: rakudo version 2017.01

```
class BT {
    has @.coeff;

    my %co2bt = '-1' => '-', '0' => '0', '1' => '+';
    my %bt2co = %co2bt.invert;

    multi method new (Str $s) {
	self.bless(coeff => %bt2co{$s.flip.comb});
    }
    multi method new (Int $i where $i >= 0) {
	self.bless(coeff => carry $i.base(3).comb.reverse);
    }
    multi method new (Int $i where $i < 0) {
	self.new(-$i).neg;
    }

    method Str () { %co2bt{@!coeff}.join.flip }
    method Int () { [+] @!coeff Z* (1,3,9...*) }

    multi method neg () {
	self.new: coeff => carry self.coeff X* -1;
    }
}

sub carry (*@digits is copy) {
    loop (my $i = 0; $i < @digits; $i++) {
	while @digits[$i] < -1 { @digits[$i] += 3; @digits[$i+1]--; }
	while @digits[$i] > 1  { @digits[$i] -= 3; @digits[$i+1]++; }
    }
    pop @digits while @digits and not @digits[*-1];
    @digits;
}

multi prefix:<-> (BT $x) { $x.neg }

multi infix:<+> (BT $x, BT $y) {
    my ($b,$a) = sort +*.coeff, ($x, $y);
    BT.new: coeff => carry ($a.coeff Z+ |$b.coeff, |(0 xx $a.coeff - $b.coeff));
}

multi infix:<-> (BT $x, BT $y) { $x + $y.neg }

multi infix:<*> (BT $x, BT $y) {
    my @x = $x.coeff;
    my @y = $y.coeff;
    my @z = 0 xx @x+@y-1;
    my @safe;
    for @x -> $xd {
	@z = @z Z+ |(@y X* $xd), |(0 xx @z-@y);
	@safe.push: @z.shift;
    }
    BT.new: coeff => carry @safe, @z;
}

my $a = BT.new: "+-0++0+";
my $b = BT.new: -436;
my $c = BT.new: "+-++-";
my $x = $a * ( $b - $c );

say 'a == ', $a.Int;
say 'b == ', $b.Int;
say 'c == ', $c.Int;
say "a × (b − c) == ", ~$x, ' == ', $x.Int;

```

Output:

```
a == 523
b == -436
c == 65
a × (b − c) == ----0+--0++0 == -262023
```