nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 23 Apr 2018 22:37



Reply to topic  [ 2 posts ] 
[Ternary] Improved Integer-based balanced library 
Author Message
Maniac

Joined: 17 Sep 2012 14:36
Posts: 277
Location: 81.170.128.52
Reply with quote
I've put together a library in C that merges ideas discussed in this thread and this thread.

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:
/* (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


ibalanced.c:
Code:
/* (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:
/* (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;
}


10 Apr 2009 17:30
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16448
Location: Colorado
Reply with quote
Post 
moving up

_________________
:eugeek: https://twitter.com/Shaos1973


10 Nov 2012 09:57
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 2 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.