CIT 591 Assignment 6: Balanced Ternary API
Fall 2009, David Matuszek

# Purposes of this assignment

• 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

# General idea of the assignment:

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.

# About balanced ternary

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":

103 = 1000 102 = 100 101 = 10 100 = 1
`7` (times 103 is 7000) `2` (times 102 is 200) `0` (times 101 is 0) `4` (times 100 is 4)
`7`*103 + `2`*102 + `0`*101 + `4`*100 = `7204`

Similarly, the ternary system uses three digits, usually `0`, `1`, and `2`, and a system in which each position in a number is worth three times the value of the position to its immediate right. (A "ternary digit" is called a "trit".)

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:

33 = 27 32 = 9 31 = 3 30 = 1
`1` (times 33 is 27) `0` (times 32 is 0) `N` (times 31 is 0) `1` (times 30 is 4)
`1`*33 + `0`*32 + `(-1)`*31 + `1`*30 = `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 Decimal equivalent `N0000` `N000` `N00` ... `N11` `NN` `N0` `N1` `N` `0` `1` `1N` `10` `11` `1NN` ... `100` `1000` `10000` `-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.

# Details

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 `value` can be either an integer, such as `-5`, or a string, such as `'N11'`. (You can tell which it is by using the `isinstance(value, Class)` method.) There is no practical limit on the size of the numbers that can be represented.
`__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 `other` number. If `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 `other` number from this number. If `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 `other` number. If `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 `other` balanced ternary number, respectively. This method allows you to use the tests `<`, `<=`, `==`, `!=`, `>=`, 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.