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:

 Support arbitrarily large integers, both positive and negative;
 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).
 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.
 Provide ways to perform addition, negation and multiplication directly on balanced ternary integers; do not convert to native integers first.
 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.




with javascript_semantics
function bt2dec(string bt)
    integer res = 0
    for i=1 to length(bt) do
        res = 3*res+(bt[i]='+')-(bt[i]='-')
    end for
    return res
end function
 
function negate(string bt)
    for i=1 to length(bt) do
        if bt[i]!='0' then
            bt[i] = '+'+'-'-bt[i]
        end if
    end for
    return bt
end function
 
function dec2bt(integer n)
    string res = "0"
    if n!=0 then
        integer neg = n<0
        if neg then n = -n end if
        res = ""
        while n!=0 do
            integer r = mod(n,3)
            res = "0+-"[r+1]&res
            n = floor((n+(r=2))/3)
        end while
        if neg then res = negate(res) end if
    end if
    return res
end function
 
-- res,carry for a+b+carry lookup tables (not the fastest way to do it, I'm sure):
constant {tadd,addres} = columnize({{"---","0-"},{"--0","+-"},{"--+","-0"},
                                    {"-0-","+-"},{"-00","-0"},{"-0+","00"},
                                    {"-+-","-0"},{"-+0","00"},{"-++","+0"},
                                    {"0--","+-"},{"0-0","-0"},{"0-+","00"},
                                    {"00-","-0"},{"000","00"},{"00+","+0"},
                                    {"0+-","00"},{"0+0","+0"},{"0++","-+"},
                                    {"+--","-0"},{"+-0","00"},{"+-+","+0"},
                                    {"+0-","00"},{"+00","+0"},{"+0+","-+"},
                                    {"++-","+0"},{"++0","-+"},{"+++","0+"}})
 
 
function bt_add(string a, b)
    integer padding = length(a)-length(b),
            carry = '0', ch
    if padding!=0 then
        if padding<0 then
            a = repeat('0',-padding)&a
        else
            b = repeat('0',padding)&b
        end if
    end if
    for i=length(a) to 1 by -1 do
        string cc = addres[find(a[i]&b[i]&carry,tadd)]
        a[i] = cc[1]
        carry = cc[2]
    end for
    if carry!='0' then
        a = carry&a
    else
        while length(a)>1 and a[1]='0' do
            a = a[2..$]
        end while
    end if
    return a
end function
 
function bt_mul(string a, string b)
    string pos = a, neg = negate(a), res = "0"
    for i=length(b) to 1 by -1 do
        integer ch = b[i]
        if ch='+' then
            res = bt_add(res,pos)
        elsif ch='-' then
            res = bt_add(res,neg)
        end if
        pos = pos&'0'
        neg = neg&'0'
    end for 
    return res
end function
 
string a = "+-0++0+", b = dec2bt(-436), c = "+-++-",
       res = bt_mul(a,bt_add(b,negate(c)))
printf(1,"%7s:  %12s  %9d\n",{"a",a,bt2dec(a)})
printf(1,"%7s:  %12s  %9d\n",{"b",b,bt2dec(b)})
printf(1,"%7s:  %12s  %9d\n",{"c",c,bt2dec(c)})
printf(1,"%7s:  %12s  %9d\n",{"a*(b-c)",res,bt2dec(res)})
