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

10³ = 1000	10² = 100	10¹ = 10	10⁰ = 1
`7` (times 10³ is 7000)	`2` (times 10² is 200)	`0` (times 10¹ is 0)	`4` (times 10⁰ is 4)
`7`10³ + `2`10² + `0`10¹ + `4`10⁰ = `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:

3³ = 27	3² = 9	3¹ = 3	3⁰ = 1
`1` (times 3³ is 27)	`0` (times 3² is 0)	`N` (times 3¹ is 0)	`1` (times 3⁰ is 4)
`1`3³ + `0`3² + `(-1)`3¹ + `1`3⁰ = `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.

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.

Additional constraint

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.

Advice

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.

Grading:

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.

Due date:

Midnight, October 27 29, via Blackboard. Zip your files and submit one zip file. Only one of you and your partner should submit, but be sure both your names are clearly visible in Blackboard comments and in the program comments.