nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 21 Oct 2018 23:28



Reply to topic  [ 2 posts ] 
[Ternary] Native integer code for Java 
Author Message
Maniac

Joined: 17 Sep 2012 14:36
Posts: 277
Location: 81.170.128.52
Reply with quote
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
Code:
        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)));


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;
    }

}


06 Mar 2011 15:23
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 17028
Location: Colorado
Reply with quote
Post 
moving up

_________________
:eugeek: https://twitter.com/Shaos1973


10 Nov 2012 10:02
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 2 posts ] 

Who is online

Users browsing this forum: Google [Bot] and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.