(It's also not truly base agnostic. There are a few lingering 3s around the Word code. But change them to 'base' and it should be alright)
For example
Code: Select all
Word w = new Word(3,6);
TriLogic tri = new TriLogic(6);
int a = 364;
int b = 10;
System.out.println("a = " + w.toString(a));
System.out.println("b = " + w.toString(b));
System.out.println("a + b = " + w.toString(w.wrap(a+b)) + " = " + w.wrap(a+b));
System.out.println("a - b = " + w.toString(w.wrap(a+b)) + " = " + w.wrap(a-b));
System.out.println("a * b = " + w.toString(w.wrap(a*b)) + " = " + w.wrap(a*b));
System.out.println("digit-wise a xor b = " + w.toString(tri.commutative(tri.XOR, a, b)));
System.out.println("digit-wise a or b = " + w.toString(tri.commutative(tri.OR, a, b)));
System.out.println("digit-wise a and b = " + w.toString(tri.commutative(tri.AND, a, b)));
Code: Select all
a = [1,1,1,1,1,1]
b = [1,0,1,0,0,0]
a + b = [-1,-1,0,-1,-1,-1] = -355
a - b = [-1,-1,0,-1,-1,-1] = 354
a * b = [1,1,-1,0,0,0] = -5
digit-wise a xor b = [1,0,1,0,0,0]
digit-wise a or b = [1,1,1,1,1,1]
digit-wise a and b = [1,0,1,0,0,0]
Code:
Code: Select all
/* (C) 2011 Viktor Lofgren
*
*
* Free for non-commercial use.
*/
package tunguska.host_native;
/**
* Toolkit for native-integer balanced base arithmetic
*
* <p>Use wrap() to simulate integer overflow, enabling native arithmetic.<br/>
* <b>Example:</b> If you wish to simulate the calculation of a b + c + d , call
* wrap(wrap(ab) + c + d)</p>
*
*
* <p><b>Caveat:</b> The digit-shifting operators are named according to
* little-endian digit terminology (that is, shift right is similar to
* a sort of division), but toInteger(int[] arry) and toArray(int v) use
* big endian bit ordering.</p>
*
* @author Viktor Lofgren
*/
public class Word {
public final int width;
public final int base;
final int[] powers;
final int[] powers_2;
int carry;
public Word(int base, int width) {
carry = 0;
this.base = base;
this.width = width;
if((base-1) / 2 != base/2) {
throw new ArithmeticException("Base must be odd");
}
powers = new int[width+1];
powers_2 = new int[width+1];
powers[0] = 1;
for(int i = 1; i <= width; i++) {
powers[i] = powers[i-1]*base;
powers_2[i] = powers[i] / 2;
}
}
/**
* Simulate integer overflow
*
*/
public int wrap(int i) {
carry = i - _wrap(i);
i = i - carry;
carry /= powers[width];
return i;
}
/**
* Simulate integer overflow at digit 'digit' (0 <= digit <= width)
*
*/
public int wrap(int i, int digit) {
carry = i - _wrap(i, digit);
i = i - carry;
carry /= powers[digit];
return i;
}
/**
* Simulate integer overflow without setting carry
* @see wrap(int i)
*/
public int _wrap(int i) {
if(i > 0)
return (i + powers_2[width]) % powers[width] - powers_2[width];
else
return -(-i + powers_2[width]) % powers[width] + powers_2[width];
}
/**
* Simulate integer overflow without setting carry
* @see wrap(int i, int digit)
*/
public int _wrap(int i, int digit) {
assert(digit > 0 && digit <= width);
if(i > 0)
return (i + powers_2[digit]) % powers[digit] - powers_2[digit];
else
return -(-i + powers_2[digit]) % powers[digit] + powers_2[digit];
}
/** Get carry of latest operation
*/
public int carry() {
return carry;
}
/** Digit-wise left shift */
public int shift_left(int i, int digits) {
carry = i - _wrap(i, width-digits);
i = powers[digits] * (i - carry);
carry /= powers[width-digits];
return i;
}
/** Single digit shift left */
public int shift_left(int i) {
carry = i - _wrap(i, width-1);
i = base * (i - carry);
carry /= powers[width-1];
return i;
}
/** Digit-wise shift right */
public int shift_right(int i, int digits) {
carry = _wrap(i, digits);
return (i - carry) / powers[digits];
}
/** Single digit shift right */
public int shift_right(int i) {
carry = _wrap(i, 1);
return (i - carry) / 3;
}
/** Digit-wise left shift, ignore carry */
public int _shift_left(int i, int digits) {
return powers[digits] * _wrap(i, width-digits);
}
/** Single digit shift left, ignore carry */
public int _shift_left(int i) {
return base * _wrap(i, width-1);
}
public int _shift_right(int i, int digits) {
return (i - _wrap(i, digits)) / powers[digits];
}
public int _shift_right(int i) {
return (i - _wrap(i, 1)) / 3;
}
/** Convert native integer to array of balanced base digits
* with big endian digit order.
*/
public int[] toArray(int v) {
int[] arry = new int[width];
for(int i = 0; i < width && v != 0; i++) {
if(v >= 0) {
arry[i] = v - 3 * ( ( v + 1) / 3 );
v = ( v + 1 ) / base;
} else {
arry[i] = v - 3 * ( ( v - 1 ) / 3);
v = ( v - 1) / base;
}
}
return arry;
}
/** Convert array of balanced base digits to native integer.
* Big endian digit order.
*/
public int fromArray(int[] digits) {
int rv = 0;
for(int i = digits.length-1; i >= 0; i--) {
rv = base * rv + digits[i];
}
return _wrap(rv);
}
public String toString(int v) {
StringBuilder rv = new StringBuilder();
rv.append('[');
for(int i : toArray(v)) {
rv.append(i);
rv.append(',');
}
rv.setCharAt(rv.length()-1, ']');
return rv.toString();
}
/* Deep voodoo */
public int getDigit(int value, int digit) {
assert(digit >= 0 && digit < width);
if(value >= 0) {
return ( value + powers_2[digit] ) / powers[digit]
- base * (( value + powers_2[digit+1]) / powers[digit+1]);
} else {
return ( value - powers_2[digit] ) / powers[digit]
+ base * (( -value + powers_2[digit+1]) / powers[digit+1]);
}
}
public int setDigit(int i, int digit, int value) {
return i + powers[digit] * ( value - getDigit(i, digit));
}
}
Code: Select all
/* (C) 2011 Viktor Lofgren
*
*
* Free for non-commercial use.
*/
package tunguska.host_native;
/**
* Balanced base 3 logic.
*
* <p>The reason this isn't base-agnostic is because the number of possible
* operators in higher balanced bases is given by e<sup>2 b ln(b)</sup>.
* This function grows at a quite ridiculous rate.
* </p>
*
* <p>Base 3 has 729 commutative operators<br />
* Base 5 has 9 765 625 commutative operators <br />
* Base 7 has 678 223 072 849 commutative operators <br />
* Base 9 has 150 094 635 296 999 121 commutative operators</p>
*
* So realistically, only base 3 is possible.
*
* @author Viktor Lofgren
*/
public class TriLogic {
final int[][] commutative;
public final int XOR = construct(1, 0, 1,
0, -1, 0);
public final int OR = construct(-1, 0, 1,
0, 1, 1);
public final int AND = construct(-1, 0, 1,
-1, -1, 0);
public final int SHIFT = construct(1, 0, -1,
-1, 0, 1);
public final int SHIFT_NO_ROTATE = construct(-1, 0, 1,
-1, 0, 1);
final Word word;
static int construct(int ff, int uu, int tt, int fu, int ft, int ut) {
return ff + 3 * uu + 9 * tt + 27 * fu + 81 * ft + 243 * ut;
}
public TriLogic(int width) {
commutative = new int[729][];
word = new Word(3, width);
Word tryte = new Word(3,6);
for(int i = 0; i < 729; i++) {
commutative[i] = tryte.toArray(i-364);
}
}
/** Commutative operator given by oper. Native-integer coded
* ternary word of width 6 (a tryte) so that
*
* <table border style="margin: 1em">
* <tr>
* <th>a[i]</th>
* <th>b[i]</th>
* <th>oper(a[i], b[i])</th>
* </tr>
* <tr>
* <td> -1 </td> <td> -1 </td> <td> oper[0] </td> </tr>
* <td> 0 </td> <td> 0 </td> <td> oper[1] </td> </tr>
* <td> 1 </td> <td> 1 </td> <td> oper[2] </td> </tr>
*
* <td> -1 </td> <td> 0 </td> <td> oper[3] </td> </tr>
* <td> -1 </td> <td> 1 </td> <td> oper[4] </td> </tr>
* <td> 0 </td> <td> 1 </td> <td> oper[5] </td> </tr>
*
* </tr>
* </table>
*
*/
public int commutative(int oper, int a, int b) {
if(oper == XOR) return xor(a,b);
int[] operator = commutative[364 + oper];
int d = 0;
for(int i = 0; i < word.width; i++) {
a = word.shift_right(a);
int ai = word.carry();
b = word.shift_right(b);
int bi = word.carry();
int di = 0;
if(ai == bi)
di = operator[1+ai];
else {
di = operator[4+bi + ai];
}
d += word.powers[i] * di;
}
return d;
}
public int invert(int a) {
int b = 0;
for(int i = 0; i < word.width; i++) {
a = word.shift_right(a);
b -= word.powers[i] * word.carry();
}
return b;
}
public int inc(int a) {
int b = 0;
for(int i = 0; i < word.width; i++) {
a = word.shift_right(a);
int ai = word.carry() + 1;
if(ai > 1) ai = -1;
b -= word.powers[i] * ai;
}
return b;
}
public int dec(int a) {
int b = 0;
for(int i = 0; i < word.width; i++) {
a = word.shift_right(a);
int ai = word.carry() - 1;
if(ai < -1) ai = 1;
b -= word.powers[i] * ai;
}
return b;
}
int xor(int a, int b) {
int d = 0;
for(int i = 0; i < word.width; i++) {
a = word.shift_right(a);
int ai = word.carry();
b = word.shift_right(b);
int bi = word.carry();
d += word.powers[i] * (ai * bi);
}
return d;
}
}
