Great algorithm to convert an integer to ternary

[eudoxie]

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.

Code: Select all

/* 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://nedopc.org/ternary/tunguska/math ... .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.

[Mac Buster]

Congratulations! Very nice piece of quick working code It works with C# too (with small changes in definitions of course).

[eudoxie]

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]

Hi,

I tried to understand...but could not ,

i will try again

[eudoxie]

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.

Code: Select all

/* 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.

Code: Select all

/* 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]

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...

[eudoxie]

Yeah, this method is incredibly useful. In Tunguska, I changed the lines

Code: Select all

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

to

Code: Select all

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]

Hi,
10-40% is a really good progress Waaw!!!!

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

[eudoxie]

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):

Code: Select all

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

Code: Select all

int result = wrap(a*b);

So you get like
wrap(364) = 364
wrap(365) = -364
wrap(366) = -363
wrap(-365) = 364
etc.

[hemuman]

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

[Shaos]

changed dead link to new one