CIT 591 Assignment 6: Balanced Ternary API

Fall 2009, David Matuszek

- To make another attempt to get everyone to try TDD (some of you haven't!)
- To give you more practice with unit testing
- To give you experience writing an API

Modern computers use the binary number system. However, an early Russian computer, the Setun, used a different number system, balanced ternary. This mysterious-sounding number system isn't as scary as it sounds. In fact, if you enjoy playing with numbers, it's actually quite fun.

Your assignment is to write a BalancedTernary API (Application Programmer's Interface) in Python. That is, you are not writing a program; you are writing a **class and its methods** for other programmers to use in their programs.

The decimal number system uses ten digits, `0`

through `9`

,
and a system in which each position in a number is worth ten times the value of
the position to its immediate right. Thus, for example, the number `7204`

indicates "seven thousands, two hundreds, no tens, and four":

10^{3} = 1000 |
10^{2} = 100 |
10^{1} = 10 |
10^{0} = 1 |
---|---|---|---|

`7` (times 10^{3} is 7000) |
`2` (times 10^{2} is 200) |
`0` (times 10^{1} is 0) |
`4` (times 10^{0} is 4) |

`7` *10^{3} + `2` *10^{2} + `0` *10^{1} + `4` *10^{0} = `7204` |

Similarly, the ternary system uses three digits,

`0`

, `1`

,
and `2`

, and a system in which each position in a number is worth This assignment, however, is to implement a *balanced* ternary system, in which the
three kinds of digits have the values `0`

, `1`

, and `-1`

. To avoid
the awkwardness of using two characters, `'-'`

and `1`

, to represent a
single digit, we will instead use `N`

to stand for the digit `-1`

.
Similar to the above example, then, the number `10N1`

indicates "one 27, no 9s,
negative one 3s, and 1:

3^{3} = 27 |
3^{2} = 9 |
3^{1} = 3 |
3^{0} = 1 |
---|---|---|---|

`1` (times 3^{3} is 27) |
`0` (times 3^{2} is 0) |
`N` (times 3^{1} is 0) |
`1` (times 3^{0} is 4) |

`1` *3^{3} + `0` *3^{2} + `(-1)` *3^{1} + `1` *3^{0} = `10N1` (or, in decimal,
27 + 0 - 3 + 1 = 25) |

In balanced ternary, as in more familiar number systems, there is exactly one way to represent any (integer) number. Unlike familiar number systems, there is no need for an additional symbol to indicate that a number is negative; for example,

`-5`

is represented as `N11`

Here are some more examples:

Balanced ternary | `N0000` |
`N000` |
`N00` |
... | `N11` |
`NN` |
`N0` |
`N1` |
`N` |
`0` |
`1` |
`1N` |
`10` |
`11` |
`1NN` |
... | `100` |
`1000` |
`10000` |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Decimal equivalent | `-81` |
`-27` |
`-9` |
... | `-5` |
`-4` |
`-3` |
`-2` |
`-1` |
`0` |
`1` |
`2` |
`3` |
`4` |
`5` |
... | `9` |
`27` |
`81` |

It will take some time to get used to balanced ternary. Fortunately, you do not have to be comfortable with the number system before you start writing the program.

Write a class `BalancedTernary(object)`

, with the following methods. These are all "special" methods--Python uses them to implement arithmetic, and if you implement the same methods, Python will treat ternary numbers as if they were "regular" numbers, and let you use them in expressions.

`__init__(self,`

*value*)- This is the constructor for balanced ternary objects. The

can be either an integer, such as*value*`-5`

, or a string, such as`'N11'`

. (You can tell which it is by using the`isinstance(`

method.) There is no practical limit on the size of the numbers that can be represented.*value*,*Class*)

`__int__(self)`

- Returns the value of this balanced ternary number as a decimal integer. If
`bt`

is a BalancedTernary object, you can call this method by saying`int(bt)`

. `__str__(self)`

- Returns the value of this balanced ternary number as a string, using the "digits"
`1`

,`0`

, and`N`

. If`bt`

is a BalancedTernary object, you can call this method by saying`str(bt)`

. This method will also be called by the`print`

statement when given a balanced ternary number. `__repr__(self)`

- Same as
`__str__`

. In fact, you should implement this method by calling`str`

. This method will be used by IDLE when it needs to print a balanced ternary number. `__add__(self,`

*other*)- Computes and returns (as a balanced ternary number) the sum of this number and the

number. If*other*`bt1`

and`bt2`

are BalancedTernary objects, you can call this method by saying`bt1 + bt2`

. `__sub__(self,`

*other*)- Computes and returns (as a balanced ternary number) the result of subtracting the

number from this number. If*other*`bt1`

and`bt2`

are BalancedTernary objects, you can call this method by saying`bt1 - bt2`

. `__mul__(self,`

*other*)- Computes and returns (as a balanced ternary number) the product of this number and the

number. If*other*`bt1`

and`bt2`

are BalancedTernary objects, you can call this method by saying`bt1 * bt2`

. Hint: Think about how you multiply decimal numbers on paper, and use the same technique.

`1N100N x N0N1 --------- 1N100N N1N001 000000 N1N001 --------- N1NNNN01N`

`__neg__(self)`

- Computes and returns (as a balanced ternary number) the negative of this number; that is, a number with the same absolute value but the opposite sign. If
`bt`

is a BalancedTernary object, you can call this method by saying`-bt`

. `__cmp__(self,`

*other*)- Returns a negative, zero, or positive
**integer**, depending on whether this number is less than, equal to, or greater than the

balanced ternary number, respectively. This method allows you to use the tests*other*`<`

,`<=`

,`==`

,`!=`

,`>=`

, and`>`

with balanced ternary numbers.

Develop these methods using TDD. Your test class should be on a different file than your `BalancedTernary`

class, and both should be submitted for grading.

The `__init__`

constructor, when it takes a decimal integer as a parameter, and the `__int__`

method, which returns a decimal number, must do some of their work using "normal" integer arithmetic. However, the other methods should work directlly with the balanced ternary representation. In other words: It's "not fair" to do the arithmetic in decimal and present the results in balanced ternary.

When adding two numbers, you have to add each pair of digits, but you may have a carry as well. This means you need to be able to add three "trits" at a time. You can do this much in decimal, if that's convenient.

You should think carefully about how you want to represent a balanced ternary number internally. A good representation is one that simplifies writing the methods; a poor one will make your programming harder. The simplest internal representation would be as a decimal integer (!), but I'm specifically forbidding that representation.

When you add two numbers, you frequently have a "carry," so at some point in your code you will have to be able to add three balanced ternary "digits." This might make a good method.

If you have `__add__`

and `__neg__`

working, `__sub__`

is easy. In fact, many of these methods can call other methods to do much of their work.

I found it handy to use dictionaries for a couple of things. The `map`

method came in handy, too. Always be on the lookout for ways to make the program simpler, cleaner, and easier to understand.

Your methods should work correctly; everything should pass *my* unit tests. You should use TDD and write thorough unit tests for all of your methods (including any helper methods).

Style will also be a factor, moreso than in previous programs. You should follow the DRY principle, and the conventions for spaces, along with all the style rules discussed previously. (Following DRY is less important in the unit test methods, but even there you should look for ways to save work.