CS3343/3341 Analysis of Algorithms Spring 2012 Weird Topic |
Balanced Ternary
|
Most of our hardware has been based on binary state storage, and binary numbers were used internally. Hardware involved with commercial transactions often has to handle money exact to the penny, but even here the number of pennies can be represented in binary. However, a subset of hardware was constructed to handle decimal numbers directly -- handheld calculators are one good example. From the beginning they used decimal numbers internally, so that the limit on the size of an exponent might be +99, for example. This web page asks the question: what if, instead of flip-flop hardware, we had flip-flap-flop hardware, where a 3-state storage was natural for the hardware? Most people would assume that we might then use base 3 numbers, ternary it's called. But there is a startling alternative.
There is another number system, similar to base 3, that Knuth (Vol. 2, p. 207) calls "perhaps the prettiest number system of all." Instead of 0, 1, and 2, this new system uses -1, 0, and 1 for the value of "trits." Just as with hexadecimal numbers, where one has to invent new symbols for the "digits" with values from 10 to 15 (using A through F), here one needs at least a new symbol for -1. There is no standard notation, but the table shows two ways to write -1: use 1, or -. It's not crazy to use a "minus" sign to stand for -1 because balanced ternary represents negative numbers without an initial minus sign (see below).
These examples include ones with a "decimal" point, which is not handled by the software here. (Several items in this writeup are taken verbatim from Knuth.)| Balanced Ternary, Examples and Notation | ||||||||
|---|---|---|---|---|---|---|---|---|
| Values | -1 | 0 | 1 | Samples | ||||
| 5 | - 6 | 32 5/9 | - 32 and 5 / 9 | 1 / 2 | ||||
| Wikipedia | - | 0 | + | + - - | - + 0 | + + - 0 . - - | - - + 0 . + + | 0 . + + + + + ... |
| Knuth |
1
| 0 | 1 | 1 1 1 | 1 1 0 | 1 1 1 0 . 1 1 | 1 1 1 0 . 1 1 | 0 . 1 1 1 1 1 ... |
| My own | - | 0 | | | | - - | - | 0 | | | - 0 . - - | - - | 0 . | | | 0 . | | | | | ... |
| Balanced Ternary Values | |||
|---|---|---|---|
| Java | C | ||
// BalancedTernary.java: convert to balanced ternary
// with weights ("trits" -1, 0, and 1
// least sig trit in 0th postion
public class BalancedTernary {
private int len; // length of arrays to use
public int[] zeros; // zero value
public BalancedTernary(int leng) {
len = leng;
zeros = new int[len];
for (int i = 0; i < len; i++) zeros[i] = 0;
}
// convert to base 3
public int[] toBase3(int n) {
int[] r = new int[len];
for (int i = 0; i < r.length; i++) r[i] = 0;
int loc = 0;
while (n > 0) {
r[loc++] = n%3;
if (loc == r.length) {
System.out.println("Overflow in toBase");
System.exit(1);
}
n = n/3;
}
return r;
}
// find negative of bal ternary #
public int[] negate(int[] b) {
int[] c = new int[b.length];
for (int i = 0; i < b.length; i++) c[i] = b[i];
for (int i = 0; i < c.length; i++) {
if (c[i] == 1) c[i] = -1;
else if (c[i] == -1) c[i] = 1;
}
return c;
}
// convert from base 3 to bal ternary
public int[] toBalTern(int[] r) {
int[] b = new int[r.length];
for (int i = 0; i < r.length; i++) b[i] = r[i];
for (int i = 0; i < r.length -1; i++) {
// add 1's to all but most sig digit
b[i] = b[i] + 1;
// process carry
int j = i;
while (b[j] == 3) {
b[j] = 0;
j++;
b[j] = b[j] + 1;
}
}
// subtract 1 from all but most sig digit
for (int i = 0; i < r.length -1; i++)
b[i] = b[i] - 1;
return b;
}
// print in reverse without leading zeros
public void printReverseNoZero(int[] r) {
int j = r.length-1;
while (r[j] == 0) j--;
for (int i = j; i >= 0; i--)
System.out.print(r[i]);
}
// print bal ternary with | - and 0
public void printBalTern(int[] b) {
for (int i = b.length-1; i >= 0; i--) {
if (b[i] == 1) System.out.print("|");
else if (b[i] == -1) System.out.print("-");
else System.out.print("0");
}
}
// print bal ternary without leading zeros
public void printBalTernNoZero(int[] b) {
int j = b.length-1;
while (b[j] == 0) j--;
for (int i = j; i >= 0; i--) {
if (b[i] == 1) System.out.print("|");
else if (b[i] == -1) System.out.print("-");
else System.out.print("0");
}
}
public void printHeader() {
System.out.println(" \tbalanced");
System.out.println(" n base 3\tternary");
System.out.println("-----------------------");
}
public static void main(String[] args) {
BalancedTernary balT = new BalancedTernary(10);
// print table of values
balT.printHeader();
System.out.println(" 0: 0 \t0");
for (int i = -1; i >= -40; i--) {
if (i >= -9) System.out.print(" ");
else System.out.print(" ");
System.out.print(i + ": -");
int[] x = balT.toBase3(-i);
balT.printReverseNoZero(x);
System.out.print(" \t");
int[] y = balT.toBalTern(x);
balT.printBalTernNoZero(balT.negate(y));
System.out.println();
}
System.out.println();
balT.printHeader();
System.out.println(" 0: 0 \t0");
for (int i = 1; i <= 40; i++) {
if (i < 10) System.out.print(" ");
else if (i < 100) System.out.print(" ");
System.out.print(i + ": ");
int[] x = balT.toBase3(i);
balT.printReverseNoZero(x);
System.out.print(" \t");
int[] y = balT.toBalTern(x);
balT.printBalTernNoZero(y);
System.out.println();
}
}
}
| // BalancedTernary.c: convert to bal tern
// with weights ("trits" -1, 0, and 1
// least sig trit in 0th postion
#include <stdio.h>
#include <stdlib.h>
#define LEN 10 // length of arrays to use
int zeros[LEN]; // zero value
// convert to base 3
int* tobase3(int n) {
int* r = (int *)malloc(4*LEN);
int i;
for (i = 0; i < LEN; i++) r[i] = 0;
int loc = 0;
while (n > 0) {
r[loc++] = n%3;
if (loc == LEN) {
printf("Overflow in toBase\n");
exit(1);
}
n = n/3;
}
return r;
}
// find negative of bal ternary #
int* negate(int* b) {
int* c = (int *)malloc(4*LEN);
int i;
for (i = 0; i < LEN; i++) c[i] = b[i];
for (i = 0; i < LEN; i++) {
if (c[i] == 1) c[i] = -1;
else if (c[i] == -1) c[i] = 1;
}
return c;
}
// convert from base 3 to bal ternary
int* tobaltern(int* r) {
int* b = (int *)malloc(4*LEN);
int i;
for (i = 0; i < LEN; i++) b[i] = r[i];
for (i = 0; i < LEN -1; i++) {
// add 1's to all but most sig dig
b[i] = b[i] + 1;
// process carry
int j = i;
while (b[j] == 3) {
b[j] = 0;
j++;
b[j] = b[j] + 1;
}
}
// subtract 1 from all but most sig dig
for (i = 0; i < LEN -1; i++)
b[i] = b[i] - 1;
return b;
}
// print in reverse without leading zeros
void printreversenozero(int* r) {
int j = LEN-1;
int i;
while (r[j] == 0) j--;
for (i = j; i >= 0; i--)
printf("%i", r[i]);
}
// print bal ternary with | - and 0
void printbaltern(int* b) {
int i;
for (i = LEN-1; i >= 0; i--) {
if (b[i] == 1) printf("|");
else if (b[i] == -1) printf("-");
else printf("0");
}
}
// print bal ternary without leading zeros
void printbalternnozero(int* b) {
int j = LEN-1;
while (b[j] == 0) j--;
int i;
for (i = j; i >= 0; i--) {
if (b[i] == 1) printf("|");
else if (b[i] == -1) printf("-");
else printf("0");
}
}
void printheader() {
printf(" \tbalanced\n");
printf(" n base 3\tternary\n");
printf("--------------------------\n");
}
int main() {
int i;
for (i = 0; i < LEN; i++) zeros[i] = 0;
// print table of values
printheader();
printf(" 0: 0 \t0\n");
for (i = -1; i >= -40; i--) {
if (i >= -9) printf(" ");
else printf(" ");
printf("%i: -", i);
int* x = tobase3(-i);
printreversenozero(x);
printf(" \t");
int* y = tobaltern(x);
printbalternnozero(negate(y));
printf("\n");
}
printf("\n");
printheader();
printf(" 0: 0 \t0\n");
for (i = 1; i <= 40; i++) {
if (i < 10) printf(" ");
else if (i < 100) printf(" ");
printf("%i: ", i);
int* x = tobase3(i);
printreversenozero(x);
printf(" \t");
int* y = tobaltern(x);
printbalternnozero(y);
printf("\n");
}
}
| ||
balanced
n base 3 ternary
| balanced
n base 3 ternary
| balanced
n base 3 ternary
| balanced
n base 3 ternary
|