It can be easily extended to use any balanced base. By default, it supports logic and arithmetic up to 18 balanced ternary digits.
It implements both host integer-based balanced logic and functions for host integer-based arithmetic, that can be delayed in many cases!
So, if you wanted to calculate something, like a sum of hundred numbers. You can calculate it as though it was any number, and then pass it to the wrap function and it returns the result of doing the calculations on a balanced computer. Comparisons are also native speed.
This makes it incredibly fast.
On my computer it performs over 150 million bit get operations in a second.
It requires no initialization, but you may need to redefine bint as signed long long on some architectures (32 bit?)
ibalanced.h:
Code: Select all
/* (C) 2009 - Viktor Lofgren
* Free to use for non-commercial purposes.
*/
#ifndef IBALANCED_H
#define IBALANCED_H
#include <limits.h>
#ifndef BINT_OVERRIDE
#define BINT_MAX LONG_MAX
#define BINT_MIN LONG_MIN
#define BINT_TYPE signed long
#endif
typedef BINT_TYPE bint;
extern bint* b_powers;
extern bint* b_powers_2;
extern bint b_power_count;
#define b_remainder( value , divisor ) ((value) >= 0 ? \
(value) - (divisor) * (( 2 * (value) + (divisor) - 1 ) / ( 2 * (divisor) )) : \
(value) - (divisor) * (( 2 * (value) - (divisor) - 1 ) / ( 2 * (divisor) )))
#define b_remainder_odd( value , divisor ) ((value) >= 0 ? \
((value) - (divisor) * (( (value) + (divisor)/2 ) / ( (divisor) ))) : \
((value) - (divisor) * (( (value) - (divisor)/2 ) / ( (divisor) ))))
#define b_quotient( value , divisor ) (( (value) > 0 ? \
( ( 2 * (value) + (divisor) - 1 ) / ( 2 * (divisor) ) ) : \
( - ( - 2 * (value) + (divisor) - 1 ) / ( 2 * (divisor) ) ) )
#define b_quotient_odd( value , divisor ) (( (value) > 0 ? \
( ( (value) + (divisor)/2 ) / ( (divisor) ) ) : \
( - ( - (value) + (divisor)/2 ) / ( (divisor) ) ) )
bint b_get_digit(register bint value, register int digit);
bint b_set_digit(register bint value, register int digit, register int new);
bint wrap(register bint value, register int width);
/* Wrap is a front-end for b_remainder_odd(value, b_powers_2[width])
* and returns the portion of the value that can be held in a word with
* width digits.
*
* It is the cornerstone in integer-based balanced arithmetic.
* It looks like this:
* wrap(value, N)
* A
* |
* |
* / / | / / - - - - /- - - base_powers_2[N]
* / | / | | / | / | /
* / | / | | / | / | /
* --/-----|-----/-----|-----/-----------/ ----|-----/-------- > value
* / | / | / | | / | /
* / | / | / | | / | /
* / / | / /
* |
* | |
* |
* | |
* | base_powers_2[N]
*
*
* The following arithmetic are safe to perform on a wrapped value without a re-wrap:
* modulo (%), division,
* The following arithmetic are unsafe, and need a re-wrap:
* addition, subtraction, multiplication
*
* Useful properties of wrap:
* wrap(wrap(a, N) + b, N) = wrap(a+b, N)
* wrap(wrap(a, N) - b, N) = wrap(a-b, N)
* wrap(wrap(a, N) * b, N) = wrap(a*b, N)
* wrap(-a, N) = -wrap(a, N)
*
* wrap(a+M*N, N) = wrap(a, N) for M = ... -3, -2, -1, 0, 1, 2, 3, ...
* wrap(a, N) = a if |a| < base_powers_2[i]
*
* wrap(wrap(a, P), Q) = wrap(a, Q) if Q < P
* wrap(wrap(a, P), Q) = wrap(a, P) if P < Q
*
*
* Be careful about multiplication though. Piling up
* too many numbers may result in a datatype overflow.
*/
enum {
// FUT UUU TUF
B_XOR = 1 * -1 + 3 * 0 + 9 * 1 +
27 * 0 + 81 * 0 + 243 * 0 +
729 * 1 + 2187 * 0 + 6561 * -1,
// TTT TUU TUF
B_OR = 1 * 1 + 3 * 1 + 9 * 1 +
27 * 1 + 81 * 0 + 243 * 0 +
729 * 1 + 2187 * 0 + 6561 * -1,
// TUF UUF FFF
B_AND = 1 * 1 + 3 * 0 + 9 * -1 +
27 * 0 + 81 * 0 + 243 * -1 +
729 *-1 + 2187 * -1 + 6561 * -1,
// FTU TUF UFT
B_SHIFT= 1 * -1 + 3 * 1 + 9 * 0 +
27 * 1 + 81 * 0 + 243 * -1 +
729 * 0 + 2187 * -1 + 6561 * 1,
// TTU TUF UFF
B_SNR= 1 * 1 + 3 * 1 + 9 * 0 +
27 * 1 + 81 * 0 + 243 * -1 +
729 * 0 + 2187 * -1 + 6561 * -1,
};
bint bivalent(bint op, register int width, register bint a, register bint b);
/* Bivalent operations are coded so that (in the case of base 3),
* a b (digit of op = result)
*
* 1 1 op[0]
* 1 0 op[1]
* 1 -1 op[2]
* 0 1 op[3]
* 0 0 op[4]
* 0 -1 op[5]
* -1 1 op[6]
* -1 0 op[7]
* -1 -1 op[8]
*
*/
#endif
Code: Select all
/* (C) 2009 - Viktor Lofgren
* Free to use for non-commercial purposes.
*/
#include "ibalanced.h"
/* Default constants */
bint default_b_powers[] = { 1, 3, 9, 27, 81, 243, 729,
2187, 6561, 19683, 59049, 177147, 531441, 1594323,
4782969, 14348907, 43046721, 129140163,
387420489L, };
bint default_b_powers_2[] = { 0, 1, 4, 13, 40, 121, 364,
1093, 3280, 9841, 29524, 88573, 265720, 797161,
2391484, 7174453, 21523360, 64570081,
193710244L
};
/* Pointers to constant tables. Can be changed to use another base,
* or more or fewer values according to whatever rocks your boat*/
bint* b_powers = default_b_powers;
bint* b_powers_2 = default_b_powers_2;
bint b_power_count = 19;
/* Basic functions */
bint b_get_digit(register bint value, register int digit) {
if(digit >= b_power_count - 1 || digit < 0) return 0;
if(value >= 0) {
return (value + b_powers_2[digit]) / b_powers[digit] - b_powers[1] * ((value + b_powers_2[digit+1]) / b_powers[digit+1]);
} else {
return (value - b_powers_2[digit]) / b_powers[digit] + b_powers[1] * (( - value + b_powers_2[digit+1]) / b_powers[digit+1]);
}
}
bint b_set_digit(register bint value, register int digit, register int new) {
if(digit >= b_power_count - 1 || new* new>= b_powers[1]*b_powers[1]) return 0;
if(value >= 0) {
return value - b_powers[digit] * ((value + b_powers_2[digit]) / b_powers[digit] - new) +
b_powers[digit+1] * ( ( value + b_powers_2[digit+1]) / b_powers[digit+1]);
} else {
return value + b_powers[digit] * ((-value + b_powers_2[digit]) / b_powers[digit] + new) +
b_powers[digit+1] * ( ( value - b_powers_2[digit+1]) / b_powers[digit+1]);
}
}
bint wrap(register bint value, register int width) {
return b_remainder_odd(value, b_powers[width]);
}
bint bivalent(bint op, register int width, register bint a, register bint b) {
while(width--) {
a = b_set_digit(a, width, b_get_digit(op, -3 * b_get_digit(a, width) - b_get_digit(b, width) + 4));
}
return a;
}
test.c (test case)
Code: Select all
/* (C) 2009 - Viktor Lofgren
* Free to use for non-commercial purposes.
*/
#include "ibalanced.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <time.h>
int main(int argc, char* argv[]) {
int i;
bint bi;
srand(time(NULL));
printf("IBALANCED TEST CASE\n");
printf(" Parameters: \n");
printf("\tsizeof(bint) = %lu\n", sizeof(bint));
printf("\tb_power_count = %ld (%ld accessible digits)\n", b_power_count, b_power_count-1);
printf("\tb_powers = %p", (void*) b_powers);
assert(b_powers);
printf(" = ");
for(i = 0; i < b_power_count; i++) {
printf("%ld ", b_powers[i]);
}
puts("");
printf("\tb_powers_2 = %p", (void*) b_powers_2);
assert(b_powers_2);
printf(" = ");
for(i = 0; i < b_power_count; i++) {
printf("%ld ", b_powers_2[i]);
}
puts("");
printf("Checking whether b_powers[%ld]*b_powers[%ld] <= BINT_MAX ", b_power_count-1, b_power_count-1);
if( 2*log(b_powers[b_power_count-1]) > log(BINT_MAX)) {
printf("\a... FAIL!\n !!! \t This architecture does not fully support arithmetic this wide!\n"
" !!! \t Recommend using smaller b_power_count, or a bigger data size. \n");
puts(" Press Enter to continue (expect errors) \n");
getchar();
} else puts("... OK");
printf("Checking whether b_power_count is big enough to hold a logic table for base %ld: ", b_powers[1]);
if( b_powers[1] * b_powers[1] > b_power_count - 1 ) {
printf("\a FAIL!\n !!! \t Logic functions will be useless\n");
puts(" Press Enter to continue (expect errors) \n");
getchar();
} else puts("... OK");
printf("Checking whether 2 * b_powers_2[n] + 1 - b_powers[n] = 0");
for(i = 0; i < b_power_count; i++) {
if(b_powers_2[i]*2+1-b_powers[i] != 0) {
printf("\t%d: \t2*%ld+1 - %ld \t = %ld", i, b_powers_2[i], b_powers[i],
b_powers_2[i]*2 + 1 - b_powers[i]);
printf("... FAIL\n"); return EXIT_FAILURE;
}
}
puts("... OK");
printf("Checking b_get_digit of %ld to %ld (in steps of 400): ", -b_powers[b_power_count-2], b_powers[b_power_count-2]);
for(bi = -b_powers[b_power_count-2]; bi <= b_powers[b_power_count-2]; bi+=400) {
bint j, sum = 0;
for(j = b_power_count - 2; j >= 0; j--) {
sum = 3 * sum + b_get_digit(bi, j);
}
if(sum != bi) {
printf("%ld != %ld... FAIL\n", sum, bi);
return EXIT_FAILURE;
}
}
printf("... OK\n");
printf("Checking b_set_digit on 5000000 random samples: ");
for(i = 0; i < 5000000; i++) {
bint rand_start = (rand() % b_powers[b_power_count-2]) * (rand() % 2 == 0 ? -1 : 1);
bint digit = rand() % (b_power_count - 2);
bint new_value = rand() % 3 - 1;
bint expected_value = rand_start - (b_get_digit(rand_start, digit) - new_value) * b_powers[digit];
bint result = b_set_digit(rand_start, digit, new_value);
if(result != expected_value) {
printf("b_set_digit(%ld,%ld,%ld) = %ld", rand_start, digit, new_value, result);
printf("... FAIL!\n");
return EXIT_FAILURE;
}
}
puts("... OK");
printf("Testing wrap(..): ");
for(i = -100; i <= 100; i++) {
if(4*i*i <= b_powers[4]*b_powers[4])
if(wrap(i, 4) != i) {
printf("... FAIL (test wrap(%d, 4) = %d)\n", i, i);
return EXIT_FAILURE;
}
if(wrap(i, 4) != b_set_digit(i, 4, 0)) {
printf("... FAIL (test wrap(%d, 4) = b_set_digit(%d, 4, 0)\n", i, i);
return EXIT_FAILURE;
}
}
puts("... OK");
printf("Printing base 3 truth tables: \n");
bint k;
puts("\tA\tB\t|\tXOR\tAND\tOR\t|\tSHIFT\tSNR");
for(k = -1; k <= 1; k++) {
bint j;
for(j = -1; j <= 1; j++) {
printf("\t%2ld\t%2ld \t|\t %2ld \t %2ld \t %2ld \t|\t %2ld\t%2ld\n", k, j,
bivalent(B_XOR, 1, k, j),
bivalent(B_AND, 1, k, j),
bivalent(B_OR, 1, k, j),
bivalent(B_SHIFT, 1, k, j),
bivalent(B_SNR, 1, k, j)
);
}
}
printf("Testing bivalent: \n");
{
bint TTTUUUFFF = 1 + 3 + 9 - 729 - 2187 - 6561;
bint TUFTUFTUF = 1 - 9 + 27 - 243 + 729 - 6561;
if(bivalent(B_XOR, 9, TTTUUUFFF, TUFTUFTUF) != B_XOR) { printf("... FAIL (in B_XOR)\n"); }
if(bivalent(B_OR, 9, TTTUUUFFF, TUFTUFTUF) != B_OR) { printf("... FAIL (in B_OR)\n"); }
if(bivalent(B_AND, 9, TTTUUUFFF, TUFTUFTUF) != B_AND) { printf("... FAIL (in B_AND)\n"); }
if(bivalent(B_SHIFT, 9, TTTUUUFFF, TUFTUFTUF) != B_SHIFT) { printf("... FAIL (in B_SHIFT)\n"); }
if(bivalent(B_SNR, 9, TTTUUUFFF, TUFTUFTUF) != B_SNR) { printf("... FAIL (in B_SNR)\n"); }
}
puts("... DONE");
return EXIT_SUCCESS;
}
