Integer-based ternary code I wrote a while back

[eudoxie]

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: Select all

/* 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: Select all

/* 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);
}

[Mac Buster]

Thank you! Very valuable piece of code. Will be very handy.

[eudoxie]

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.

[Mac Buster]

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 ?

[eudoxie]

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.

[Shaos]

moving up