eudoxie
Maniac
Joined: 17 Sep 2012 13:36 Posts: 277 Location: 81.170.128.52
|
I've cleaned up some of the code I've posted earlier in this forum, and turned it into a small library for ternary mathematics and logic using host-native integers (that is, instead of storing digits in a vector, we store the number as a native integer, and use deep magic to simulate the effects of ternary operations, such as data type overflow.) (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 Produces | | | | Code: 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: /* (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: /* (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; }
}
| | | | |
|