nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 01:18



Reply to topic  [ 6 posts ] 
Integer-based ternary code I wrote a while back 
Author Message
Maniac

Joined: 17 Sep 2012 13:36
Posts: 277
Location: 81.170.128.52
Reply with quote
I wrote a small library of code a while back that did two pretty interesting things, first of all it did integer-based ternary logic (as opposed to integer-array-based like I did in Tunguska) so it can get and set the value of individual trits out of a native integer. It also caches the result of these operations, so in theory it should be able to do ternary logic extremely quickly at the penalty of a somewhat big memory imprint and initial caching time.


It was a while back I wrote the code, so I'm not sure how stable or working it is, but the testcase seems to make no objections, so I'm sharing it.

I think I wrote it as an experimental new faster back end to Tunguska, with every focus on getting it to run as fast as possible (so the code isn't very elegant) but for some reason I abandoned it. But still, it seems like it's could be useful to someone someday.

intern.h:
Code:
/* Integer-based Trernary Library
 *
 * (C) 2008 Viktor Lofgren <vlofgren@gmail.com>
 * Free to use for non-commercial purposes.
 *
 *
 * */

#ifndef intern_h
#define intern_h

#define TRYTE_MAX 364

/* If the following causes problem ... */
#define IS_NEG(X) (X) & 0x10000000
/* ... feel free to use this one instead:
#define IS_NEG(X) (X) < 0 ? 1 : 0
*/

#define STUB printf("%s:%d\t***STUB***\n", __FILE__, __LINE__), 0

typedef int tryte;
inline tryte tryte_add(register tryte a, register tryte b);
inline tryte tryte_mul(register tryte a, register tryte b);
inline int get_trit(register tryte a, register int trit);
int hexadec_nonary(int val);

#endif


intern.c:
Code:
/* Integer-based Trernary Library
 *
 * (C) 2008 Viktor Lofgren <vlofgren@gmail.com>
 * Free to use for non-commercial purposes.
 *
 * Most functions have a noncached and a cached version, where the
 * cached version is vastly preferred.
 *
 * */

#include "intern.h"
#include <stdio.h>
#include <stdlib.h>

#define TEST(VALUE) printf("Testing '%s' = %d\n", #VALUE, VALUE);
#define TEST_COND(COND) printf("Testing condition '%s' (%s)\n", #COND, (COND) ? "Success!":"Failure");

/* * * * * * * * * * * * * * * * * * * * * * * * *
 *   Value caches.              *
 *                   *
 * * * * * * * * * * * * * * * * * * * * * * * * */

int (*shl_cache)[730][6]    = NULL;
int (*shr_cache)[730][6]    = NULL;
int (*gtrit_cache)[730][6]    = NULL;
int (*strit_cache)[730][6][3]    = NULL;
int (*and_cache)[730][730]    = NULL;
int (*or_cache)[730][730]    = NULL;
int (*xor_cache)[730][730]    = NULL;

/* * * * * * * * * * * * * * * * * * * * * * * * *
 *                   *
 *   Non-cached functions.           *
 *                   *
 *   It's dumb to use these directly when    *
 *   there is a perfectly fine value cache    *
 *   system...                  *
 *                   *
 * * * * * * * * * * * * * * * * * * * * * * * * */

inline int _get_trit(register tryte a, register int trit) {
   /* Be afraid. Be very afraid. */
   if(trit == 0) return IS_NEG(a)    ?    (-(-a + 1)%3 + 1)       :    ((a+1)%3 - 1);
   a -= IS_NEG(a)          ?   (-(-a + 1)%3 + 1)       :    ((a+1)%3 - 1);
   if(trit == 1) return IS_NEG(a)    ?    (-(-a + 4)%9 + 4)/3       :    ((a+4)%9 - 4)/3;
   a -= IS_NEG(a)          ?    (-(-a + 4)%9 + 4)       :    ((a+4)%9 - 4);
   if(trit == 2) return IS_NEG(a)    ?    (-(-a + 13)%27 + 13)/9       :    ((a+13)%27 - 13)/9;
   a -= IS_NEG(a)          ?    (-(-a + 13)%27 + 13)       :    ((a+13)%27 - 13);
   if(trit == 3) return IS_NEG(a)    ?   (-(-a + 40)%81 + 40)/27    :    ((a+40)%81 - 40)/27;
   a -= IS_NEG(a)          ?    (-(-a + 40)%81 + 40)       :    ((a+40)%81 - 40);
   if(trit == 4) return IS_NEG(a)    ?    (-(-a + 121)%243 + 121)/81    :    ((a+121)%243 - 121)/81;
   a -= IS_NEG(a)          ?    (-(-a + 121)%243 + 121)    :    ((a+121)%243 - 121);
   if(trit == 5) return IS_NEG(a)    ?    (-(-a + 364)%729 + 364)/243    :    ((a+364)%729 - 364)/243;

   else return 0; // DOES NOT COMPUTE!!
}

inline int _set_trit(register tryte a, register int trit, register int newtrit) {
   if(newtrit < -1 || newtrit > 1) return 0; // DNC
   switch(trit) {
      case 0: return a - _get_trit(a, 0) + newtrit;
      case 1: return a - 3*(_get_trit(a, 1) + newtrit);
      case 2: return a - 9*(_get_trit(a, 2) + newtrit);
      case 3: return a - 27*(_get_trit(a, 3) + newtrit);
      case 4: return a - 81*(_get_trit(a, 4) + newtrit);
      case 5: return a - 243*(_get_trit(a, 5) + newtrit);
      default: return 0; // DNC
   }
}

inline int _shr_tryte(register tryte a, register int trits) {
   while(trits--)
      a = _set_trit(a, 0, 0) / 3;

   return a;
}

inline int _shl_tryte(register tryte a, register int trits) {
   while(trits--)
      a = _set_trit(a, 5, 0) * 3;
   return a;
}

/* * * * * * * * * * * * * * * * * * * * * * * * *
 *                   *
 *   Logical operators.           *
 *                   *
 * * * * * * * * * * * * * * * * * * * * * * * * */

inline int xor_trit(register int a, register int b) {
   return -a*b;
}

inline int and_trit(register int a, register int b) {
   if(a == b) return a;
   if(a < 0 || b < 0) return -1;
   return 0;
}

inline int or_trit(register int a, register int b) {
   if(a == b) return a;
   if(a > 0 || b > 0) return 1;
   if(a == 0 || b == 0) return 0;
}

inline int not_trit(register int a) {
   return -a;
}

/* * * * * * * * * * * * * * * * * * * * * * * * *
 *                   *
 *   Tritwise functions.           *
 *                   *
 * * * * * * * * * * * * * * * * * * * * * * * * */

int _xor_tryte(register tryte a, register tryte b) {
   tryte retval = 0;
   register int i;
   for(i = 5; i >= 0; i--) {
      retval = retval*3 + xor_trit(_get_trit(a, i), _get_trit(b, i));
   }
   return retval;
}

int _and_tryte(register tryte a, register tryte b) {
   tryte retval = 0;
   register int i;
   for(i = 5; i >= 0; i--) {
      retval = retval*3 + and_trit(_get_trit(a, i), _get_trit(b, i));
   }
   return retval;
}

int _or_tryte(register tryte a,register  tryte b) {
   tryte retval = 0;
   register int i;
   for(i = 5; i >= 0; i--) {
      retval = retval*3 + or_trit(_get_trit(a, i), _get_trit(b, i));
   }
   return retval;
}


/* * * * * * * * * * * * * * * * * * * * * * * * *
 *   Cached functions.           *
 *                   *
 *   For the love of kittens, run do_cache()  *
 *   before you use them!           *
 *                   *
 * * * * * * * * * * * * * * * * * * * * * * * * */

inline int get_trit(register tryte a, register int trit) {
   if(a < - 364 || a > 364 || trit < 0 || trit > 5) return 0;
   else return (*gtrit_cache)[a+364][trit];
}

inline int set_trit(register tryte a, register int trit, register int newtrit) {
   if(a < - 364 || a > 364 || trit < 0 || trit > 5 || newtrit < -1 || newtrit > 1) return 0;
   else return (*strit_cache)[a+364][trit][newtrit+1];
}

inline int shr_tryte(register tryte a, register int trits) {
   if(a < - 364 || a > 364 || trits < 0 || trits > 5) return 0;
   return (*shr_cache)[a+364][trits];
}

inline int shl_tryte(register tryte a, register int trits) {
   if(a < - 364 || a > 364 || trits < 0 || trits > 5) return 0;
   return (*shl_cache)[a+364][trits];
}

inline int xor_tryte(register tryte a, register tryte b) {
   if(a < - 364 || a > 364 || b < -364 || b > 364) return 0;
   return (*xor_cache)[a+364][b+364];
}

inline int and_tryte(register tryte a, register tryte b) {
   if(a < - 364 || a > 364 || b < -364 || b > 364) return 0;
   return (*and_cache)[a+364][b+364];
}

inline int or_tryte(register tryte a, register tryte b) {
   if(a < - 364 || a > 364 || b < -364 || b > 364) return 0;
   return (*or_cache)[a+364][b+364];
}


/* It makes no sense to cache these:
 *   Use integer arithmetic instead!
 *      (Code readthrough months later: Why are these even here?)
 */

inline tryte tryte_add(register tryte a, register tryte b) {
   if(IS_NEG(a)) {
      if(!IS_NEG(b)) {
         return a+b;
      }
      else return -tryte_add(-a,-b);
   }
   return (a+b + TRYTE_MAX) % (2*TRYTE_MAX+1) - TRYTE_MAX;
}

inline tryte tryte_mul(register tryte a, register tryte b) {
   if(IS_NEG(a) ^ IS_NEG(b)) return -tryte_mul(a,-b);
   else return (a*b +TRYTE_MAX) % (2*TRYTE_MAX+1) - TRYTE_MAX;
}

/* Convert tryte to hexadecimal nonary notation. */
int hexadec_nonary(tryte val) {
   #define HEXTRITS(X) (IS_NEG((X)) ? (-(X) + 9) : X)
   return
      HEXTRITS(get_trit(val, 0) + 3*get_trit(val, 1)) +
      HEXTRITS(get_trit(val, 2) + 3*get_trit(val, 3))*16 +
      HEXTRITS(get_trit(val, 4) + 3*get_trit(val, 5))*16*16;
   #undef HEXTRITS
}

void testcase() {
   tryte a = TRYTE_MAX , b = -TRYTE_MAX;
   TEST(tryte_mul(a,b));
   int i;
   for(i = -TRYTE_MAX; i <= TRYTE_MAX; i++) {
      printf("%d:%3.3x\n", i, hexadec_nonary(i));
   }
   TEST_COND(get_trit(TRYTE_MAX, 0) == 1);
   TEST_COND(get_trit(TRYTE_MAX, 1) == 1);
   TEST_COND(get_trit(TRYTE_MAX, 2) == 1);
   TEST_COND(get_trit(TRYTE_MAX, 3) == 1);
   TEST_COND(get_trit(TRYTE_MAX, 4) == 1);
   TEST_COND(get_trit(TRYTE_MAX, 5) == 1);
   
   TEST_COND(get_trit(-TRYTE_MAX, 0) == -1);
   TEST_COND(get_trit(-TRYTE_MAX, 1) == -1);
   TEST_COND(get_trit(-TRYTE_MAX, 2) == -1);
   TEST_COND(get_trit(-TRYTE_MAX, 3) == -1);
   TEST_COND(get_trit(-TRYTE_MAX, 4) == -1);
   TEST_COND(get_trit(-TRYTE_MAX, 5) == -1);
   TEST(set_trit(TRYTE_MAX, 5, 0));
   TEST(shl_tryte(TRYTE_MAX, 0));
   TEST(shl_tryte(TRYTE_MAX, 1));
   TEST(shl_tryte(TRYTE_MAX, 2));
   TEST(shl_tryte(TRYTE_MAX, 3));
   TEST(shl_tryte(TRYTE_MAX, 4));
   TEST(shl_tryte(TRYTE_MAX, 5));
   TEST(shl_tryte(TRYTE_MAX, 6));
   TEST(or_tryte(1+3-9, 3-9 ));
   TEST(and_tryte(1+3-9, 3+9 ));

}

void do_cache() {
   register int a, b, c;
   printf("Caching...\n");
   shl_cache = malloc(sizeof(*shl_cache));
   shr_cache = malloc(sizeof(*shr_cache));
   gtrit_cache = malloc(sizeof(*gtrit_cache));
   strit_cache = malloc(sizeof(*strit_cache));
   and_cache = malloc(sizeof(*and_cache));
   or_cache = malloc(sizeof(*or_cache));
   xor_cache = malloc(sizeof(*xor_cache));
   for(a = -364; a <= 364; a++) {
      for(b = 0; b < 6; b++) {
         (*shl_cache)[a+364][b] = _shl_tryte(a,b);
         (*shr_cache)[a+364][b] = _shr_tryte(a,b);
         (*gtrit_cache)[a+364][b] = _get_trit(a, b);
         for(c = -1; c < 2; c++) {
            (*strit_cache)[a+364][b][c+1] = _set_trit(a, b, c);
         }
      }
      for(b = -364; b <= 364; b++) {
         (*and_cache)[a+364][b+364] = _and_tryte(a,b);
         (*or_cache)[a+364][b+364] = _or_tryte(a,b);
         (*xor_cache)[a+364][b+364] = _xor_tryte(a,b);
      }
   }
   printf("Done...\n");
}

int main(int argc, char* argv[]) {
   do_cache();
   testcase();
   and_trit(1,1);
}


19 Jan 2009 05:08
Profile
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Thank you! Very valuable piece of code. Will be very handy.


20 Jan 2009 08:48
Profile
Maniac

Joined: 17 Sep 2012 13:36
Posts: 277
Location: 81.170.128.52
Reply with quote
I have experimented with making Tunguska use it, but not quite gotten it to work (though the blame is mine, the tunguska tryte class isn't pretty at all, I really should redesign it some day.)

Though I've gotten it to use it enough to get an estimation of the speed gain, and it isn't half bad. It approximately runs 2.5 times faster than the old code (on my machine, it has an average speed of 5,000,000 operations per second.) It's probably possible to push it to twice that, but that would require even more extensive "surgery" of the sources.


20 Jan 2009 11:34
Profile
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Wow! 2.5 times acceleration is very serious improvement! I hope you'll be able to solve all troubles with using the code in Tunguska :)

Btw - does the Tunguska has some limits of its speed or it work with different speed on different computers ? I mean, if I wrote a intro or demo, will it work the at same speed on my and your computers ?


21 Jan 2009 06:49
Profile
Maniac

Joined: 17 Sep 2012 13:36
Posts: 277
Location: 81.170.128.52
Reply with quote
Yeah. The main problem is the scope of the change. It would require altering a lot of code. But on the other hand, I'll need to do that either way to weed out some of the less well designed code.

It currently does not have any speed limit. I will probably end up adding that some time though, since it would make it run smoother.


21 Jan 2009 07:23
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
moving up

_________________
:dj: https://mastodon.social/@Shaos


10 Nov 2012 08:55
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 6 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


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.