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.




ОТДЕЛ Сетунь+; 
ИСПОЛЬЗУЕТ 
  Параметр ИЗ "...\Отделы\Обмен\", 
  Текст ИЗ "...\Отделы\Числа\", 
  Вывод ИЗ "...\Отделы\Обмен\"; 

ПЕР 
  зч: РЯД 10 ИЗ ЗНАК; 
  счпоз: ЦЕЛ; 
  число: ЦЕЛ; 
  память: ДОСТУП К НАБОР
    ячейки: РЯД 20 ИЗ ЦЕЛ;
    размер: УЗКЦЕЛ;
    отрицательное: КЛЮЧ
  КОН; 

ЗАДАЧА СоздатьПамять; 
УКАЗ 
  СОЗДАТЬ(память); 
  память.размер := 0; 
  память.отрицательное := ОТКЛ 
КОН СоздатьПамять; 

ЗАДАЧА ДобавитьВПамять(что: ЦЕЛ); 
УКАЗ 
  память.ячейки[память.размер] := что; 
  УВЕЛИЧИТЬ(память.размер) 
КОН ДобавитьВПамять; 

ЗАДАЧА ОбратитьПамять; 
ПЕР 
  зчсл: ЦЕЛ; 
  сч: ЦЕЛ; 
УКАЗ 
  ОТ сч := 0 ДО память.размер ДЕЛИТЬ 2 - 1 ВЫП 
    зчсл := память.ячейки[сч]; 
    память.ячейки[сч] := память.ячейки[память.размер-сч-1]; 
    память.ячейки[память.размер-сч-1] := зчсл 
  КОН 
КОН ОбратитьПамять; 

ЗАДАЧА ВывестиПамять; 
ПЕР 
  сч: ЦЕЛ; 
УКАЗ  
  ОТ сч := 0 ДО память.размер-1 ВЫП 
    ЕСЛИ память.ячейки[сч] < 0 ТО
      Вывод.Цепь("-")
    АЕСЛИ память.ячейки[сч] > 0 ТО
      Вывод.Цепь("+")
    ИНАЧЕ Вывод.Цепь("0") КОН 
  КОН 
КОН ВывестиПамять; 

ЗАДАЧА УдалитьПамять; 
УКАЗ 
  память := ПУСТО 
КОН УдалитьПамять; 

ЗАДАЧА Перевести(число: ЦЕЛ); 
ПЕР 
  о: ЦЕЛ; 
  з: КЛЮЧ; 
  ЗАДАЧА ВПамять(что: ЦЕЛ); 
  УКАЗ 
    ЕСЛИ память.отрицательное ТО 
      ЕСЛИ что < 0 ТО ДобавитьВПамять(1)
      АЕСЛИ что > 0 ТО ДобавитьВПамять(-1)
      ИНАЧЕ ДобавитьВПамять(0) КОН 
    ИНАЧЕ 
      ДобавитьВПамять(что) 
    КОН 
  КОН ВПамять; 
УКАЗ 
  ЕСЛИ число < 0 ТО память.отрицательное := ВКЛ КОН; 
  число := МОДУЛЬ(число); 
  з := ОТКЛ; 
  ПОКА число > 0 ВЫП 
    о := число ОСТАТОК 3; 
    число := число ДЕЛИТЬ 3; 
    ЕСЛИ з ТО 
      ЕСЛИ о = 2 ТО ВПамять(0) АЕСЛИ о = 1 ТО ВПамять(-1) ИНАЧЕ ВПамять(1); з := ОТКЛ КОН 
    ИНАЧЕ 
      ЕСЛИ о = 2 ТО ВПамять(-1); з := ВКЛ ИНАЧЕ ВПамять(о) КОН 
    КОН 
  КОН; 
  ЕСЛИ з ТО ВПамять(1) КОН; 
  ОбратитьПамять; 
  ВывестиПамять(ВКЛ); 
КОН Перевести; 

ЗАДАЧА ВЧисло(): ЦЕЛ; 
ПЕР 
  сч, мн: ЦЕЛ; 
  результат: ЦЕЛ; 
УКАЗ 
  результат := 0; 
  мн := 1; 
  ОТ сч := 0 ДО память.размер-1 ВЫП 
    УВЕЛИЧИТЬ(результат, память.ячейки[память.размер-сч-1]*мн); 
    мн := мн * 3 
  КОН; 
  ВОЗВРАТ результат 
КОН ВЧисло; 

УКАЗ 
  Параметр.Текст(1, зч); счпоз := 0; 
  число := Текст.ВЦел(зч, счпоз); 
  СоздатьПамять; 
  Перевести(число); 
  Вывод.ЧЦел(" = %d.", ВЧисло(), 0, 0, 0); 
  УдалитьПамять 

КОН Сетунь.
