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 Ada.Finalization;
 
package BT is
 
   type Balanced_Ternary is private;
 
   -- conversions
   function To_Balanced_Ternary (Num : Integer) return Balanced_Ternary;
   function To_Balanced_Ternary (Str : String)  return Balanced_Ternary;
   function To_Integer (Num : Balanced_Ternary)  return Integer;
   function To_string (Num : Balanced_Ternary)   return String;
 
   -- Arithmetics
   -- unary minus
   function "-" (Left : in Balanced_Ternary)
		return Balanced_Ternary;
 
   -- subtraction
   function "-" (Left, Right : in Balanced_Ternary)
		return Balanced_Ternary;
 
   -- addition
   function "+" (Left, Right : in Balanced_Ternary)
		return Balanced_Ternary;
   -- multiplication
   function "*" (Left, Right : in Balanced_Ternary)
		return Balanced_Ternary;
 
private   
   -- a balanced ternary number is a unconstrained array of (1,0,-1) 
   -- dinamically allocated, least significant trit leftmost
   type Trit is range -1..1;
   type Trit_Array is array (Positive range <>) of Trit;
   pragma Pack(Trit_Array);
 
   type Trit_Access is access Trit_Array;
 
   type Balanced_Ternary is new Ada.Finalization.Controlled
     with record
	Ref : Trit_access;
   end record;
 
   procedure Initialize (Object : in out Balanced_Ternary);
   procedure Adjust     (Object : in out Balanced_Ternary);
   procedure Finalize   (Object : in out Balanced_Ternary);
 
end BT;