| Code: /* Package of routines for arithmetic in balanced ternary */ /* Numbers are held as an array of size lena stored least */ /* significant byte first */
/* Developed by James Allwright, */ /* Department of Electronics and Computer Science, */ /* University of Southampton, UK */
#define MAXLEN 50
static int plus_one[MAXLEN] = {1}; static int len_plus_one = 1;
add(lena, lenb, lenc, a, b, c) /* c = a + b */ /* add together 2 numbers in balanced ternary */ int *lena, *lenb, *lenc; int a[MAXLEN], b[MAXLEN], c[MAXLEN]; { int carry, i;
zero(lenc, c); carry = 0; i = 0; while ((carry != 0) || (i < *lena) || (i < *lenb)) { c[i] = carry; if (i < *lena) { c[i] = c[i] + a[i]; }; if (i < *lenb) { c[i] = c[i] + b[i]; }; carry = 0; if (c[i] > 1) { c[i] = c[i] - 3; carry = 1; }; if (c[i] < -1) { c[i] = c[i] + 3; carry = -1; }; i = i + 1; if ((i >= MAXLEN) && (carry != 0)) { printf("Overflow error!\n"); exit(-1); }; }; *lenc = i+1; while ((*lenc > 0) && (c[*lenc-1] == 0)) { *lenc = *lenc -1; }; };
negate(lena, a) /* a = -a */ int *lena; int a[MAXLEN]; { int i;
for (i=0; i < *lena; i++) { a[i] = -a[i]; }; };
neg(lena, lenb, a, b) /* b = -a */ int *lena, *lenb; int a[MAXLEN], b[MAXLEN]; { int i;
for (i=0; i < *lena; i++) { b[i] = -a[i]; }; *lenb = *lena; };
sub(lena, lenb, lenc, a, b, c) /* c = a - b */ /* subtract numbers in balanced ternary */ /* using negate and add */ int *lena, *lenb, *lenc; int a[MAXLEN], b[MAXLEN], c[MAXLEN]; { int lent; int temp[MAXLEN]; /* temp = -b */ neg(lenb, &lent, b, temp); add(lena, &lent, lenc, a, temp, c); };
copy(lena, lenb, a, b) /* copies a into b */ int *lena, *lenb; int a[MAXLEN], b[MAXLEN]; { int i;
for (i=0; i<*lena; i++) { b[i] = a[i]; }; *lenb = *lena; };
zero(lena, a) /* a = 0 */ /* sets a to zero */ int *lena; int a[MAXLEN]; { int i;
for (i=0; i<MAXLEN; i++) { a[i] = 0; }; *lena = 0; };
mshift(lena, a) /* shift left one place (multiply by 3) */ int *lena; int a[MAXLEN]; { int i;
if (*lena >= MAXLEN ) { printf("Overflow error in mshift\n"); exit(-1); }; *lena = *lena + 1; for (i=*lena-1; i>0; i--) { a[i] = a[i-1]; }; a[0] = 0; };
dshift(lena, a) /* shift right one place (divide by 3) */ int *lena; int a[MAXLEN]; { int i;
if (*lena > 0) { *lena = *lena - 1; for (i=0; i<*lena; i++) { a[i] = a[i+1]; }; }; };
mul(lena, lenb, lenc, a, b, c) /* multiply together 2 numbers in balanced ternary */ int *lena, *lenb, *lenc; int a[MAXLEN], b[MAXLEN], c[MAXLEN]; { int lend, lent; int d[MAXLEN], temp[MAXLEN]; int i;
zero(lenc, c); if (*lena + *lenb - 2 > MAXLEN) { printf("Result too large error in multiplication!\n"); exit(1); }; copy(lenb, &lend, b, d); for (i=0; i < *lena; i++) { if (a[i] == 1) { /* c = c + d */ add(lenc, &lend, &lent, c, d, temp); copy(&lent, lenc, temp, c); }; if (a[i] == -1) { /* c = c - d */ sub(lenc, &lend, &lent, c, d, temp); copy(&lent, lenc, temp, c); }; if (i < *lena-1) { mshift(&lend, d); }; }; };
int compare(lena, lenb, a, b) /* used by div */ /* returns : */ /* 1 if |a| > |b| */ /* 0 if |a| == |b| */ /* -1 if |a| < |b| */
int *lena, *lenb; int a[MAXLEN], b[MAXLEN]; { int signa, signb; int place; if (*lena > *lenb) { return(1); }; if (*lena < *lenb) { return(-1); }; /* get sign of a and b */ signa = a[*lena-1]; signb = b[*lenb-1]; place = *lena - 1; while ((place >= 0) && (signa*a[place] == signb*b[place])) { place = place -1; }; if (place == -1) { return(0); } else { if (signa*a[place] > signb*b[place]) { return(1); } else { return(-1); }; }; };
div(lena_in, lenb_in, lenc, lena, a_in, b_in, c, a) /* divide numbers in balanced ternary */ /* calculates a_in / b_in, returning */ /* c = result, a = remainder */ /* algorithm is like decimaltoBT */ /* a and b are working copies of a_in and b_in */ int *lena_in, *lenb_in, *lenc, *lena; int a_in[MAXLEN], b_in[MAXLEN], c[MAXLEN], a[MAXLEN]; { int lenb_store; int *lenb; int lent; int b[MAXLEN], temp[MAXLEN]; int pos, digit;
if (*lenb_in == 0) { printf("Division by zero error!\n"); exit(1); }; if (*lena_in == 0) { *lenc = 0; return; }; copy(lena_in, lena, a_in, a); /* remainder starts as a */ lenb = &lenb_store; copy(lenb_in, lenb, b_in, b); /* copy in b */ pos = 0; digit = - 1;
/* align b appropriately */ while (*lenb < (*lena+1)) { mshift(lenb, b); pos = pos + 1; }; while (*lenb > (*lena+1)) { dshift(lenb, b); pos = pos - 1; }; if (pos >= 0) { *lenc = pos + 1; /* initial guess at length of result */ } else { *lenc = 0; }
while ((*lena > 0) && (pos >= 0)) { /* decide whether to try +b or -b */ if (a[*lena - 1] == b[*lenb - 1]) { digit = - digit; /* b = -b */ neg(lenb, &lent, b, temp); copy(&lent, lenb, temp, b); }; /* temp = a + b */ add(lena, lenb, &lent, a, b, temp); if (compare(lena, &lent, a, temp) == 1) { /* accept digit */ /* a = temp */ copy(&lent, lena, temp, a); c[pos] = digit; } else { /* don't accept digit */ c[pos] = 0; }; pos = pos - 1; dshift(lenb, b); };
/* if we've reduced a to zero, fill in the remaining digits with 0 */ while (pos >= 0) { c[pos] = 0; pos = pos - 1; };
/* correct the length of the result */ while ((*lenc > 0) && (c[*lenc-1] == 0)) { *lenc = *lenc - 1; };
/* ensure that the remainder is the same sign as a_in */ if (*lena > 0) { /* no problem if there is no remainder */ if (a_in[*lena_in - 1] != a[*lena-1]) { if ((a_in[*lena_in - 1] == b_in[*lenb_in-1]) ) { /* a = a + b_in */ add(lena, lenb_in, &lent, a, b_in, temp); copy(&lent, lena, temp, a); /* c = c - 1 */ sub(lenc, &len_plus_one, &lent, c, plus_one, temp); copy(&lent, lenc, temp, c); } else { /* a = a - b_in */ sub(lena, lenb_in, &lent, a, b_in, temp); copy(&lent, lena, temp, a); /* c = c + 1 */ add(lenc, &len_plus_one, &lent, c, plus_one, temp); copy(&lent, lenc, temp, c); }; }; }; };
BTtodecimal(lena, a, result) /* convert Balanced Ternary to decimal */ int *lena; int a[MAXLEN]; int *result; { int b, i;
b = 1; *result = 0; for (i=0; i < (*lena); i++) { *result = *result + b * a[i]; b = b * 3; }; };
int abs(a) int a; { if (a > 0) { return(a); } else { return(-a); }; };
decimaltoBT(lenr, result, value) /* convert decimal to Balanced Ternary */ int *lenr; int result[MAXLEN]; int value; { int target, val, goal, pos;
*lenr = 0; target = value; pos = 0; val = 1; goal = 2 * target; if (goal < 0) { goal = -goal; }; while ((val < goal) && (pos < MAXLEN)) { val = 3 * val; pos = pos + 1; }; if (pos >= MAXLEN) { printf("Overflow error in decimaltoBT\n"); exit(-1); }; if ( target < 0) { val = -val; }; while (pos >= 0) { if (abs(target-val) < abs(target)) { if (val > 0) { result[pos] = 1; target = target - val; } else { result[pos] = -1; target = target - val; }; if (*lenr == 0) { *lenr = pos+1; }; } else { result[pos] = 0; }; val = val / 3; pos = pos - 1; /* make target and val the same sign */ if ((target * val) < 0) { val = -val; }; }; };
printnum(lena, a) int *lena; int a[MAXLEN]; { int i;
for (i=*lena-1; i>=0; i--) { printf("(%d)", a[i]); }; if (*lena == 0) printf("(0)"); };
main(argc, argv) int argc; char *argv[]; { int a[MAXLEN], b[MAXLEN], c[MAXLEN], rem[MAXLEN]; int lena, lenb, lenc, lenrem; int i, answer; int t1, t2, t3;
printf("Testing decimaltoBT and BTtodecimal.\n"); for (i=0; i<100; i++) { t1 = (rand() % 1000) - 500; decimaltoBT(&lena, a, t1); BTtodecimal(&lena, a, &t3); if (t3 != t1) { printf("Error : %d has been converted to %d\n", t1, t3); }; }; printf("Testing add.\n"); for (i=0; i<100; i++) { t1 = (rand() % 1000) - 500; t2 = (rand() % 1000) - 500; decimaltoBT(&lena, a, t1); decimaltoBT(&lenb, b, t2); add(&lena, &lenb, &lenc, a, b, c); BTtodecimal(&lenc, c, &t3); if (t3 != (t1+t2)) { printf("add gives %d + %d = %d\n", t1, t2, t3); printf("Error : answer should be %d\n", t1+t2); }; }; printf("Testing sub.\n"); for (i=0; i<100; i++) { t1 = (rand() % 1000) - 500; t2 = (rand() % 1000) - 500; decimaltoBT(&lena, a, t1); decimaltoBT(&lenb, b, t2); sub(&lena, &lenb, &lenc, a, b, c); BTtodecimal(&lenc, c, &t3); if (t3 != (t1-t2)) { printf("add gives %d + %d = %d\n", t1, t2, t3); printf("Error : answer should be %d\n", t1-t2); }; }; printf("Testing mul.\n"); for (i=0; i<100; i++) { t1 = (rand() % 10000) - 5000; t2 = (rand() % 10000) - 5000; decimaltoBT(&lena, a, t1); decimaltoBT(&lenb, b, t2); mul(&lena, &lenb, &lenc, a, b, c); BTtodecimal(&lenc, c, &t3); if (t3 != (t1*t2)) { printf("mul gives %d * %d = %d\n", t1, t2, t3); printf("Error : answer should be %d\n", t1*t2); }; }; printf("Testing div.\n"); for (i=0; i<100; i++) { t1 = (rand() % 1000) - 500; t2 = (rand() % 50) - 25; if (t2 == 0) { t2 = 1; }; decimaltoBT(&lena, a, t1); decimaltoBT(&lenb, b, t2); div(&lena, &lenb, &lenc, &lenrem, a, b, c, rem); BTtodecimal(&lenc, c, &t3); if (t3 != (t1/t2)) { printf("div gives %d / %d = %d\n", t1, t2, t3); printf("Error : answer should be %d\n", t1/t2); }; }; };
| |