1

When when we use base 2, binary, to count each bit has a different positive value(except the sign bit) for example:

 0   0   0  0  0  0  0 
64  32  16  8  4  2  1

Now I need to count in the range -120 - 120 using signed powers of 3, my "bits" are:

  0     0    0    0    0   0   0   0    0    0
-81   -27   -9   -3   -1   1   3   9   27   81

How should I go about finding a method to actually count using these bits aside from memoizing what combination leads to which value at the start of the program?

In more mathematical terms, given a number n how should I go about finding the combination of "powers of 3 bits" that is equal to n.

As an alternative way to solve the problem, instead of a straight conversion between these numbering formats, it might be possible that given n already converted into this "powers of 3" format, I can find n+1 in this format directly(without converting back to decimal, adding 1 and then converting back). However I also have no clue how to proceed in this direction.

I am constrained to this method of representing numbers since the main project is at its core, a fancier file converter and this is the format one of the file types i need to support uses.

P.S. If this is the wrong forum for this please direct me to the correct one. I'm not sure myself where exactly this kind of question should be asked.

EDIT: The representation of 0 is no bits set, all 0s I believe, and whenever one of the bits gets set, its value is added to the number.

Rares Dima
  • 1,575
  • 1
  • 15
  • 38
  • 1
    What is the representation of `0`? Is it `-1 1` or, say, `-9 9`? Or any of them will do? – Dmitry Bychenko Jan 22 '18 at 08:23
  • No bits set, all `0`s. That is the "default" and whenever you set a bit, the default value of 0 changes by adding the value of the newly set bit. – Rares Dima Jan 22 '18 at 08:24
  • 1
    Do you want the ternary representation of a number? If not I am not sure what you want to achieve, can you give some example numbers and the representation you want. – SaiBot Jan 22 '18 at 08:32
  • @SaiBot `0` for example is no bits set. `14`(dec) would be represented as `9+3+1`(those bits set, rest are all `0`). `15` would be represented as `27+(-9)+(-3)`. `99` would be represented as `81+27+(-9)`. `-34` would be represented as `(-27)+(-9)+(-1)+3`. That is the basic gist of it. – Rares Dima Jan 22 '18 at 08:36
  • 1
    Just for context: In the general case there is no way around enumerating all possible combinations as mentioned in https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum. There might still be a solution in the special case you are asking for. – SaiBot Jan 22 '18 at 08:45

1 Answers1

3

This is balanced ternary system that was used in Setun' computer. Every "digit" (-1,0,1) is called trit similar to bit.

Without hardware support you can translate number in this system using iterations - get the largest power of three (p) taking part in given value, fill corresponding trit with current sign, subtract p from value, adjust sign and continue.

Note that MST=1 (the most significant trit) is included in values from (3^n-3^(n-1)-...-1) to (3^n+3^(n-1)+...+1). For example, 2-nd trit (9) is the oldest set one in values from 5 to 13. Value in the parenthesis is sum of geometric progression and there exists short formula for it.

So we can move from 0-th trit to more significant ones, recalculating limits. Working Delphi code, checked for -40..40 limits

 function ToBTS(Value: Integer): TArray<Integer>;
  var
    p, sgn, t: Integer;

    procedure AdjustSign();
    begin
      if value < 0 then begin
         sgn := -sgn;
         value := -value;
      end;
    end;

  begin
   SetLength(Result, 8);
   for t := 0 to 7 do
     Result[t] := 0;
   sgn := 1;
   p := 1; // power of three
   t := 0; // trit number

   AdjustSign();
   while p * 3 - 1 < 2 * value do begin //forward traversal
     p := p * 3;
     t := t + 1; //move to more significant trit
    end;

   while value <> 0 do begin  
      Result[t] := sgn;
      value := value - p;
      AdjustSign();
     //backward traversal
      while (value > 0) and (p - 1 >= 2 * value) do begin
        p := p div 3;
        t := t - 1; //move to less significant trit
      end;
    end;
 end;

output (+ for 1, - for -1)

-13 0---
-12 0--0
-11 0--+
-10 0-0-
-9 0-00
-8 0-0+
-7 0-+-
-6 0-+0
-5 0-++
-4 00--
-3 00-0
-2 00-+
-1 000-
0 0000
1 000+
2 00+-
3 00+0
4 00++
5 0+--
6 0+-0
7 0+-+
8 0+0-
9 0+00
10 0+0+
11 0++-
12 0++0
13 0+++
MBo
  • 77,366
  • 5
  • 53
  • 86