Ternary.info FAQ FORUM LOGIN REG
Ternary.info
special interest group on balanced ternary numeral system and trinary logic
Main Menu

Ternary.info Forum Index
   Ternary Software {ENG}
     Great algorithm		Register To Post

Threaded | Newest First Previous Topic | Next Topic | Bottom
Poster Thread
eudoxie
Posted on: 2009/1/22 16:53
Home away from home
Joined: 2007/12/27
From: Sweden
Posts: 266
Great algorithm
This is fantastic. I've written an algorithm for host integer to trit array representation that is incredibly simple and fast. It's O(log(v)), all-integer and has no superfluous variables or overhead.

/* Convert a native integer v to
 * an array of at most n ternary digits, t. */
void to_ternary(int* t, int n, int v) {
        int i; 
        for(i = 0; i < n && v != 0; i++) {
                if(v >= 0) {
                        t[i] = v-3*((v+1)/3);
                        v = (v+1)/3;
                } else {
                        t[i] = v-3*((v-1)/3);
                        v = (v-1)/3;
                }
        }
        for(; i < n; i++) t[i] = 0; 
}


It's based on a mathematical insight I had on balanced bases when I was taking the bus earlier today. I wrote it down in a PDF if anyone is interested...

http://www.acc.umu.se/~achtt315/math.tools.for.balanced.bases.pdf

The algorithm takes advantage of what happens to equation (8) when you let kappa be 1, and from that it's just a matter of inserting values into equation (11) and making optimizations.
Mbr
Posted on: 2009/1/22 17:20
Moderator
Joined: 2005/4/10
From: Moscow
Posts: 364
Re: Great algorithm
Congratulations! Very nice piece of quick working code :) It works with C# too (with small changes in definitions of course).


----------------
http://www.vntb.ru/
eudoxie
Posted on: 2009/1/22 17:26
Home away from home
Joined: 2007/12/27
From: Sweden
Posts: 266
Re: Great algorithm
Thanks. It should hopefully work with any language that where a*(b/a) is the same as a*floor(b/a) for integers a and b.
hemuman
Posted on: 2009/1/23 5:35
Just can't stay away
Joined: 2008/8/1
From: India, Bangalore
Posts: 98
Re: Great algorithm
Hi,

I tried to understand...but could not ,

i will try again


----------------
Manoj Kumar
http://manojky.net/
http://tvm.manojky.net/
http://yafaray.manojky.net/
eudoxie
Posted on: 2009/1/23 14:28
Home away from home
Joined: 2007/12/27
From: Sweden
Posts: 266
Re: Great algorithm
I find it's a very useful formulation. This function extracts an arbitrary digit in a host integer. It should be pretty easy to extend for systems that use wider words than 6.

/* Get the n:th trit in v */
int tritn(int v, int n) {
        if(v >= 0) {
                switch(n) {
                        case 0: return v - 3*((v+1)/3);
                        case 1: return (v+1)/3 - 3*((v+4)/9);
                        case 2: return (v+4)/9 - 3*((v+13)/27);
                        case 3: return (v+13)/27 - 3*((v+40)/81);
                        case 4: return (v+40)/81 - 3*((v+121)/243);
                        case 5: return (v+121)/243 - 3*((v+364)/729);
                    
                }  
        } else {
                switch(n) {
                        case 0: return v + 3*((1-v)/3);
                        case 1: return (v-1)/3 + 3*((4-v)/9);
                        case 2: return (v-4)/9 + 3*((13-v)/27);
                        case 3: return (v-13)/27 + 3*((40-v)/81);
                        case 4: return (v-40)/81 + 3*((121-v)/243);
                        case 5: return (v-121)/243 + 3*((364-v)/729);
                }

        }
        return 0; 
}


I haven't tested this one very extensively, but it seems to work. It allows you to set a trit in a host integer. It doesn't check so that t is in a valid range, so obviously care must be taken.

/* Set trit n in integer v to t */
int settrit(int v, int n, int t) {
        if(v >= 0) {
                switch(n) {
                        case 0:
                                return t + 3*((v+1)/3);
                        case 1:
                                return v - 3*((v+1)/3 - t) + 9*((v+4)/9);
                        case 2:
                                return v - 9*((v+4)/9 - t) + 27*((v+13)/27);
                        case 3:
                                return v - 27*((v+13)/27 -t) + 81*((v+40)/81);
                        case 4:
                                return v - 81*((v+40)/81 -t) + 243*((v+121)/243);
                        case 5:
                                return v - 243*((v+121)/243 -t) + 729*((v+364)/729);
                }
        } else {
                switch(n) {
                        case 0:
                                return t - 3*((1-v)/3);
                        case 1:
                                return v + 3*((1-v)/3 + t) + 9*((v-4)/9);
                        case 2:
                                return v + 9*((4-v)/9 + t) + 27*((v-13)/27);
                        case 3:
                                return v + 27*((13-v)/27 + t) + 81*((v-40)/81);
                        case 4:
                                return v + 81*((40-v)/81 + t) + 243*((v-121)/243);
                        case 5:
                                return v + 243*((121-v)/243 + t) + 729*((v-364)/729);
                }

        }
        return 0;
}
hemuman
Posted on: 2009/1/24 3:07
Just can't stay away
Joined: 2008/8/1
From: India, Bangalore
Posts: 98
Re: Great algorithm
Hi,

I am using the first code to convert int to Tryte....its useful....and i will be using 2nd one to perform memory operations in TVM...


----------------
Manoj Kumar
http://manojky.net/
http://tvm.manojky.net/
http://yafaray.manojky.net/
eudoxie
Posted on: 2009/1/24 18:06
Home away from home
Joined: 2007/12/27
From: Sweden
Posts: 266
Re: Great algorithm
Yeah, this method is incredibly useful. In Tunguska, I changed the lines

tryte instruction = memref(ip);
tryte highbits = instruction >> 4;
instruction = (instruction << 2) >> 2;


to

int highbits, instruction = memref(ip).to_int();
if(instruction > 0) {
  highbits = ((instruction + 40) / 81);
} else {
  highbits = ((instruction-40) / 81);
}
instruction -= 81 * highbits;


And got a 10-40% speed increase. I knew this was a bottleneck in the design, but yikes! On my system, it's now just below 3,000,000 operations per second!
hemuman
Posted on: 2009/1/24 19:57
Just can't stay away
Joined: 2008/8/1
From: India, Bangalore
Posts: 98
Re: Great algorithm
Hi,
10-40% is a really good progress Waaw!!!!

Just wanted to know if you have developed any ternary algorithms for Matrix operations.


----------------
Manoj Kumar
http://manojky.net/
http://tvm.manojky.net/
http://yafaray.manojky.net/
eudoxie
Posted on: 2009/1/24 20:24
Home away from home
Joined: 2007/12/27
From: Sweden
Posts: 266
Re: Great algorithm
Hmm, I'm not sure how that would be applicable. Most matrix operations are just a series of regular scalar operations. Base really doesn't factor in.

Though I have developed a wraparound function that allows you to use native integer arithmetic and still get "wraparound" of numbers bigger or smaller than what fits in the word.

For word size 6 (where of course 364=(3^6-1)/2 and 729=3^6):
int wrap(int v) {
  if(v > 364) return v - (v+364)/729;
  else if(v < -364) return v - (v-364)/729;
  return v;
}


So then if you want to know something like a*b, you simply skip the intermediate trit array step by using

int result = wrap(a*b);


So you get like
wrap(364) = 364
wrap(365) = -364
wrap(366) = -363
wrap(-365) = 364
etc.
hemuman
Posted on: 2009/1/24 20:45
Just can't stay away
Joined: 2008/8/1
From: India, Bangalore
Posts: 98
Re: Great algorithm
Thats an interesting function...i guess this can be used in case of representing Angels as they always lie between 0 t0 360 deg....so in ternary we can have them between "0-729"...yup its useful for matrix transform of 3D objects


----------------
Manoj Kumar
http://manojky.net/
http://tvm.manojky.net/
http://yafaray.manojky.net/
Threaded | Newest First Previous Topic | Next Topic | Top

Register To Post
 
Login
Username:

Password:


Lost Password?

Register now!


Copyright (c) 2005-2008 Ternary.info. All rights reserved.
Powered by XOOPS 2.0 (c) 2001-2003 The XOOPS Project
Theme & Graphics by Xoops Brasil