Ternary Numnber
/* * @(#)Ternary.java 1.0 Mar 7, 2008 * * The MIT License * * Copyright (c) 2008 Malachi de AElfweald <malachid@gmail.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal * in the Software without restriction, including without limitation the rights * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell * copies of the Software, and to permit persons to whom the Software is * furnished to do so, subject to the following conditions: * * The above copyright notice and this permission notice shall be included in * all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN * THE SOFTWARE. */ //package org.eoti.math.ternary; import java.math.BigDecimal; import java.math.BigInteger; import java.util.Comparator; import java.util.concurrent.CopyOnWriteArrayList; public class Ternary extends Number implements Comparable<Ternary> { protected BigInteger biThree = BigInteger.valueOf(3); protected BigDecimal bdThree = new BigDecimal(biThree); protected CopyOnWriteArrayList<Trit> trits; public static void main(String[] args) { if(args.length == 0) { System.out.format("java org.eoti.lang.Ternary number [[number]...]\n"); System.exit(0); } for(String arg : args) { BigInteger toConvert = new BigInteger(arg); Ternary ternary = new Ternary(toConvert); System.out.format("\nDecimal:\t%s\nTernary:\t%s\n", toConvert, ternary); } } public Ternary(int toConvert) { this(BigInteger.valueOf(toConvert)); } public Ternary(BigInteger toConvert) { this(); int position = 0; BigInteger remaining = toConvert; BigInteger rounded, left; while(!remaining.equals(BigInteger.ZERO)) { rounded = ((new BigDecimal(remaining)).divide(bdThree, 0, BigDecimal.ROUND_HALF_UP)).toBigInteger(); left = remaining.subtract(rounded.multiply(biThree)); if(left.equals(BigInteger.ONE)) setTrit(position++, Trit.POSITIVE); else if(left.equals(BigInteger.ZERO)) setTrit(position++, Trit.NEUTRAL); else setTrit(position++, Trit.NEGATIVE); remaining = rounded; } } public Ternary() { super(); trits = new CopyOnWriteArrayList<Trit>(); } public Ternary(Ternary toClone) { this(); trits.addAll(toClone.trits); } public Ternary abs() { if(signum() >= 0) return new Ternary(this); return invert(this); } public int tritLength() { for(int position=trits.size()-1; position>=0; position--) { if(!trits.get(position).equals(Trit.NEUTRAL)) return position+1; } return 0; //return trits.size(); } public void clearTrit(int position){setTrit(position, Trit.NEUTRAL);} public void setTrit(int position, Trit trit) { if(trits.size() <= position) ensureCapacity(position+1); trits.set(position, trit); } public Trit getTrit(int position) { if(position < 0) return Trit.NEUTRAL; if(trits.size() <= position) ensureCapacity(position+1); return trits.get(position); } public int signum(){return getTrit(tritLength()-1).toInt();} public void ensureCapacity(int nTerts) { while(trits.size() < nTerts) trits.add(Trit.NEUTRAL); } public void trim() { while( (trits.size() > 0) && (trits.get(trits.size()-1).isNeutral()) ) trits.remove(trits.size()-1); } public void increment(){increment(0);} public void increment(int position) { Trit t = getTrit(position).rotateUp(); setTrit(position, t); if(t.isNegative()) // carry increment(position+1); } public void decrement(){decrement(0);} public void decrement(int position) { Trit t = getTrit(position).rotateDown(); setTrit(position, t); if(t.isPositive()) // borrow decrement(position+1); } public String toString() { if(trits.size() == 0) return Trit.NEUTRAL.toString(); StringBuilder sb = new StringBuilder(); for(Trit trit : trits) sb.append(trit); return sb.reverse().toString(); } public int compareTo(Ternary t) { // shortcut if one is positive and the other negative int ourSig = signum(); int theirSig = t.signum(); if(ourSig > theirSig) return 1; if(theirSig > ourSig) return -1; // we're the same sign... who has more trits? int ourLength = tritLength(); int theirLength = t.tritLength(); if(ourLength > theirLength) return (ourSig>0?1:-1); if(theirLength > ourLength) return (ourSig>0?-1:1); // same sign, same length... guess we need to find first mismatch for(int position = ourLength-1; position >= 0; position--) { int comparison = getTrit(position).compareTo(t.getTrit(position)); if(comparison != 0) return comparison; } // guess we are identical return 0; } public boolean equals(Object obj) { if(obj == null) return false; return toString().equals(obj.toString()); } public int hashCode() { return toString().hashCode(); } public BigInteger toBigInteger() { BigInteger toRet = BigInteger.ZERO; BigInteger curr; for(int pos=0; pos<trits.size(); pos++) { curr = (biThree.pow(pos)).multiply(BigInteger.valueOf(getTrit(pos).toInt())); toRet = toRet.add(curr); } return toRet; } public void shiftLeft(){shiftLeft(1);} public void shiftLeft(int num) { CopyOnWriteArrayList<Trit> newTrits = new CopyOnWriteArrayList<Trit>(); for(int i=0; i<num; i++) newTrits.add(Trit.NEUTRAL); newTrits.addAll(trits); trits = newTrits; } public void shiftRight(){shiftRight(1);} public void shiftRight(int num) { ensureCapacity(trits.size() + num); for(int i=0; i<num; i++) trits.remove(0); } public byte byteValue(){return toBigInteger().byteValue();} public double doubleValue(){return toBigInteger().doubleValue();} public float floatValue(){return toBigInteger().floatValue();} public int intValue(){return toBigInteger().intValue();} public long longValue(){return toBigInteger().longValue();} public short shortValue(){return toBigInteger().shortValue();} /** * Add the specified addend to this augend * * @param addend to be added * @return ternary summation */ public Ternary add(Ternary addend) { /** * Try to find a better way of doing this * using gate logic * and DON'T just use toBigInteger to do it */ // make sure the LONGER one is on top if(tritLength() < addend.tritLength()) return addend.add(this); Ternary summation = new Ternary(this); Ternary toCarry = new Ternary(); for(int pos=0; pos<trits.size(); pos++) { Trit a = summation.getTrit(pos); Trit b = addend.getTrit(pos); switch(a.state) { case Negative: summation.setTrit(pos, b.rotateDown()); break; case Positive: summation.setTrit(pos, b.rotateUp()); break; default: summation.setTrit(pos, b); } if(a.equals(b)) toCarry.setTrit(pos+1, a); } if(toCarry.tritLength() == 0) return summation; return summation.add(toCarry); } /** * Subtract the specified subtrahend from this minuend * * @param subtrahend to be subtracted * @return ternary difference */ public Ternary subtract(Ternary subtrahend) { return add(invert(subtrahend)); } public static Ternary invert(Ternary toInvert) { Ternary inverted = new Ternary(); for(int i=0; i<toInvert.trits.size(); i++) inverted.setTrit(i, toInvert.getTrit(i).invert()); return inverted; } /** * Multiply this multiplicand by the specified multiplier * * @param multiplier to multiply by * @return ternary product */ public Ternary multiply(Ternary multiplier) { /** * Try to find a better way of doing this * using gate logic * and DON'T just use toBigInteger to do it */ // make sure the LONGER one is on top if(tritLength() < multiplier.tritLength()) return multiplier.multiply(this); Ternary product = new Ternary(); for(int posB=0; posB<multiplier.trits.size(); posB++) { Ternary row = new Ternary(); for(int posA=0; posA<trits.size(); posA++) { Trit a = getTrit(posA); Trit b = multiplier.getTrit(posB); Trit c = a.equality(b); if(a.isNeutral() && b.isNeutral()) c = Trit.NEUTRAL; row.setTrit(posA + posB, c); } product = product.add(row); } return product; } /** * Divide this divided by the specified divisor * * @param divisor to divide by * @return ternary[] containing {quotient,remainder} */ public Ternary[] divide(Ternary divisor) { /** * 6/3=2r0 * 6=dividend * 3=divisor * 2=quotient * 0=remainder */ Ternary dividend = new Ternary(this); Ternary quotient = new Ternary(0); Ternary remainder = new Ternary(0); int dividendSign = dividend.signum(); if(dividendSign == 0) return new Ternary[]{quotient, remainder}; int divisorSign = divisor.signum(); if(divisorSign == 0) throw new ArithmeticException("Divide by Zero not currently supported."); if(dividendSign != divisorSign) { // if one or the other (not both) are negative, then the result will have a negative quotient Ternary tmp = null; Ternary[] results = null; if(dividendSign < 0) { tmp = new Ternary(dividend); tmp = invert(tmp); //results = tmp.divide(divisor); results = tmp.divide(divisor); }else{ tmp = new Ternary(divisor); tmp = invert(tmp); //results = dividend.divide(tmp); results = dividend.divide(tmp); } quotient = invert(results[0]); remainder = dividend.subtract(quotient.multiply(divisor)); return new Ternary[]{quotient, remainder}; } // two positives or two negatives will be positive results if(dividendSign < 0) { dividend = invert(dividend); divisor = invert(divisor); } int position = dividend.tritLength()-1; while(position >= 0) { remainder = (new Ternary(dividend)).subtract(quotient.multiply(divisor)); remainder.shiftRight(position); int compare = remainder.compareTo(divisor); if(compare > 0) { quotient.increment(); }else if(compare < 0){ if(position > 0) quotient.shiftLeft(1); position--; }else{ quotient.increment(); position--; } } remainder = (new Ternary(dividend)).subtract(quotient.multiply(divisor)); return new Ternary[]{quotient, remainder}; } public Ternary sqrt() { return sqrt(this); } public static Ternary sqrt(Ternary number) { return sqrt(number, new Ternary(1)); } protected static Ternary sqrt(Ternary number, Ternary guess) { // ((n/g) + g)/2: until same result twice in a row Ternary result = new Ternary(0); Ternary flipA = new Ternary(result); Ternary flipB = new Ternary(result); boolean first = true; while( result.compareTo(guess) != 0) { if(!first) guess = result; else first = false; result = (number.divide(guess))[0]; result = result.add(guess); result = (result.divide(new Ternary(2)))[0]; result.trim(); // handle flip flops if(result.equals(flipB)) return flipA; flipB = flipA; flipB.trim(); flipA = result; flipA.trim(); } return result; } } class Trit implements Comparable<Trit>, Comparator<Trit> { protected enum State { Negative(-1, '\u012B'), Neutral(0, '0'), Positive(1, '1'); State(int intValue, char charValue) { this.intValue = intValue; this.charValue = charValue; } protected int intValue; protected char charValue; public int toInt(){return intValue;} public char toChar(){return charValue;} } // convenience access public static final Trit NEGATIVE = new Trit(State.Negative); public static final Trit NEUTRAL = new Trit(State.Neutral); public static final Trit POSITIVE = new Trit(State.Positive); protected State state; public Trit(State state){this.state = state;} public Trit(Trit trit){this.state = trit.state;} public boolean isNegative(){return state == State.Negative;} public boolean isNeutral(){return state == State.Neutral;} public boolean isPositive(){return state == State.Positive;} public Trit max(Trit other){return toInt() >= other.toInt() ? this : other;} public Trit min(Trit other){return toInt() <= other.toInt() ? this : other;} public Trit or(Trit other){return max(other).clone();} public Trit and(Trit other){return min(other).clone();} public Trit xor(Trit other) { if(isNegative() && other.isNegative()) return NEGATIVE.clone(); if(isNegative() && other.isPositive()) return POSITIVE.clone(); if(isPositive() && other.isNegative()) return POSITIVE.clone(); return NEUTRAL.clone(); } public Trit nand(Trit other){return not(and(other));} public Trit nor(Trit other){return not(or(other));} public Trit nxor(Trit other){return not(xor(other));} /** * Invert unary operation * ? becomes 1 * 0 becomes 0 * 1 becomes ? */ public Trit invert(){return not();} public Trit not() { switch(state) { case Negative: return Trit.POSITIVE.clone(); case Positive: return Trit.NEGATIVE.clone(); default: return Trit.NEUTRAL.clone(); } } public Trit not(Trit other){return inequality(other);} public Trit inequality(Trit other) { Trit eq = equality(other); if(eq.isPositive()) return NEGATIVE.clone(); if(eq.isNegative()) return POSITIVE.clone(); return NEUTRAL.clone(); } public Trit disjunction(Trit other){return or(other);} public Trit conjunction(Trit other){return and(other);} public Trit equality(Trit other) { if(state == other.state) return POSITIVE.clone(); if(isNeutral()) return NEUTRAL.clone(); if(other.isNeutral()) return NEUTRAL.clone(); return NEGATIVE.clone(); } public Trit implication(Trit other) { if(other.isNegative() && isNeutral()) return NEUTRAL.clone(); if(other.isNegative() && isPositive()) return NEGATIVE.clone(); if(other.isNeutral() && isPositive()) return NEUTRAL.clone(); return POSITIVE.clone(); } public Trit alternation(Trit other){return xor(other);} /** * ShiftUp unary operation * ? becomes 0 * 0 becomes 1 * 1 becomes 1 */ public Trit shiftUp(){return NEUTRAL.implication(this);} /** * ShiftDown unary operation * ? becomes ? * 0 becomes ? * 1 becomes 0 */ public Trit shiftDown(){return not(implication(NEUTRAL));} /** * RotateUp unary operation * ? becomes 0 * 0 becomes 1 * 1 becomes ? */ public Trit rotateUp() { /** * Change to use gate logic? */ switch(state) { case Negative: return NEUTRAL.clone(); case Neutral: return POSITIVE.clone(); default: return NEGATIVE.clone(); } } /** * RotateDown unary operation * ? becomes 1 * 0 becomes ? * 1 becomes 0 */ public Trit rotateDown() { /** * Change to use gate logic? */ switch(state) { case Negative: return POSITIVE.clone(); case Neutral: return NEGATIVE.clone(); default: return NEUTRAL.clone(); } } public String toString(){return ""+toChar();} public char toChar(){return state.toChar();} public int toInt(){return state.toInt();} public Trit clone(){return new Trit(state);} public boolean equals(Object obj) { if(obj == null) return false; if(!Trit.class.isAssignableFrom(obj.getClass())) return false; return (compareTo((Trit)obj) == State.Neutral.toInt()); } public int compareTo(Trit obj){return compare(this, obj);} public int compare(Trit t1, Trit t2) { if(t1.state.toInt() < t2.state.toInt()) return State.Negative.toInt(); if(t1.state.toInt() > t2.state.toInt()) return State.Positive.toInt(); return State.Neutral.toInt(); } /** * Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those * provided by <code>java.util.Hashtable</code>. * <p/> * The general contract of <code>hashCode</code> is: <ul> <li>Whenever it is invoked on the same object more than once * during an execution of a Java application, the <tt>hashCode</tt> method must consistently return the same integer, * provided no information used in <tt>equals</tt> comparisons on the object is modified. This integer need not remain * consistent from one execution of an application to another execution of the same application. <li>If two objects are * equal according to the <tt>equals(Object)</tt> method, then calling the <code>hashCode</code> method on each of the * two objects must produce the same integer result. <li>It is <em>not</em> required that if two objects are unequal * according to the {@link Object#equals(Object)} method, then calling the <tt>hashCode</tt> method on each of the two * objects must produce distinct integer results. However, the programmer should be aware that producing distinct * integer results for unequal objects may improve the performance of hashtables. </ul> * <p/> * As much as is reasonably practical, the hashCode method defined by class <tt>Object</tt> does return distinct * integers for distinct objects. (This is typically implemented by converting the internal address of the object into * an integer, but this implementation technique is not required by the Java<font size="-2"><sup>TM</sup></font> * programming language.) * * @return a hash code value for this object. * * @see Object#equals(Object) * @see java.util.Hashtable */ @Override public int hashCode(){ return toString().hashCode(); } } /* package org.eoti.math.ternary; import junit.framework.TestCase; import junit.framework.Test; import junit.framework.TestSuite; public class TernaryTest extends TestCase { public TernaryTest(String name){super(name);} public static Test suite(){return new TestSuite(TernaryTest.class);} public void testInt() { int toTest = 13; assertEquals("Int", toTest, (new Ternary(toTest)).intValue()); } public void testSignum() { assertEquals("Positive Signum", 1, (new Ternary(10)).signum()); assertEquals("Neutral Signum", 0, (new Ternary(0)).signum()); assertEquals("Negative Signum", -1, (new Ternary(-10)).signum()); } public void testTritLength() { assertTrue("TritLength(13)", (new Ternary(13)).tritLength() == 3); assertTrue("TritLength(14)", (new Ternary(14)).tritLength() == 4); } public void testClearTrit() { Ternary tst = new Ternary(13); tst.clearTrit(1); Ternary expected = new Ternary(10); assertEquals("ClearTrit", expected, tst); } public void testSetTrit() { Ternary tst = new Ternary(10); tst.setTrit(1, Trit.POSITIVE); Ternary expected = new Ternary(13); assertEquals("SetTrit", expected, tst); } public void testIncrement() { Ternary tst = new Ternary(-1); tst.increment(); assertEquals("Increment -1->0", 0, tst.intValue()); tst.increment(); assertEquals("Increment 0->1", 1, tst.intValue()); tst.increment(); assertEquals("Increment 1->2", 2, tst.intValue()); tst.increment(); assertEquals("Increment 2->3", 3, tst.intValue()); } public void testDecrement() { Ternary tst = new Ternary(3); tst.decrement(); assertEquals("Decrement 3->2", 2, tst.intValue()); tst.decrement(); assertEquals("Decrement 2->1", 1, tst.intValue()); tst.decrement(); assertEquals("Decrement 1->0", 0, tst.intValue()); tst.decrement(); assertEquals("Decrement 0->-1", -1, tst.intValue()); } public void testShiftLeft() { Ternary tst = new Ternary(8); // +0- tst.shiftLeft(); tst.trim(); Ternary expected = new Ternary(24);// +0-0 expected.trim(); assertEquals("ShiftLeft", expected, tst); } public void testShiftRight() { Ternary tst = new Ternary(24);// +0-0 tst.shiftRight(); tst.trim(); Ternary expected = new Ternary(8); // +0- expected.trim(); assertEquals("ShiftRight", expected, tst); } public void testAdd() { assertEquals("Add PosPos", new Ternary(13), (new Ternary(10)).add(new Ternary(3))); assertEquals("Add PosNeg", new Ternary(7), (new Ternary(10)).add(new Ternary(-3))); assertEquals("Add NegNeg", new Ternary(-13), (new Ternary(-10)).add(new Ternary(-3))); assertEquals("Add NegPos", new Ternary(-7), (new Ternary(-10)).add(new Ternary(3))); } public void testSubtract() { assertEquals("Subtract PosPos", new Ternary(7), (new Ternary(10)).subtract(new Ternary(3))); assertEquals("Subtract PosNeg", new Ternary(13), (new Ternary(10)).subtract(new Ternary(-3))); assertEquals("Subtract NegNeg", new Ternary(-7), (new Ternary(-10)).subtract(new Ternary(-3))); assertEquals("Subtract NegPos", new Ternary(-13), (new Ternary(-10)).subtract(new Ternary(3))); } public void testMultiply() { assertEquals("Multiply PosPos", new Ternary(15), (new Ternary(5)).multiply(new Ternary(3))); assertEquals("Multiply PosNeg", new Ternary(-15), (new Ternary(5)).multiply(new Ternary(-3))); assertEquals("Multiply NegNeg", new Ternary(15), (new Ternary(-5)).multiply(new Ternary(-3))); assertEquals("Multiply NegPos", new Ternary(-15), (new Ternary(-5)).multiply(new Ternary(3))); } public void testDivide() { // 6/3=2r0; 6=dividend; 3=divisor; 2=quotient; 0=remainder Ternary dividend = new Ternary(7); Ternary divisor = new Ternary(2); Ternary expectedQuotient = new Ternary(3); Ternary expectedRemainder = new Ternary(1); Ternary[] results = dividend.divide(divisor); results[0].trim(); results[1].trim(); assertEquals("Divide(7/2) Quotient", expectedQuotient, results[0]); assertEquals("Divide(7/2) Remainder", expectedRemainder, results[1]); dividend = new Ternary(7); divisor = new Ternary(-2); expectedQuotient = new Ternary(-3); expectedRemainder = new Ternary(1); results = dividend.divide(divisor); results[0].trim(); results[1].trim(); assertEquals("Divide(7/-2) Quotient", expectedQuotient, results[0]); assertEquals("Divide(7/-2) Remainder", expectedRemainder, results[1]); dividend = new Ternary(-7); divisor = new Ternary(2); expectedQuotient = new Ternary(-3); expectedRemainder = new Ternary(-1); results = dividend.divide(divisor); results[0].trim(); results[1].trim(); assertEquals("Divide(-7/2) Quotient", expectedQuotient, results[0]); assertEquals("Divide(-7/2) Remainder", expectedRemainder, results[1]); dividend = new Ternary(-7); divisor = new Ternary(-2); expectedQuotient = new Ternary(3); expectedRemainder = new Ternary(1); results = dividend.divide(divisor); results[0].trim(); results[1].trim(); assertEquals("Divide(-7/-2) Quotient", expectedQuotient, results[0]); assertEquals("Divide(-7/-2) Remainder", expectedRemainder, results[1]); dividend = new Ternary(0); divisor = new Ternary(2); expectedQuotient = new Ternary(0); expectedRemainder = new Ternary(0); results = dividend.divide(divisor); results[0].trim(); results[1].trim(); assertEquals("Divide(0/2) Quotient", expectedQuotient, results[0]); assertEquals("Divide(0/2) Remainder", expectedRemainder, results[1]); try{ dividend = new Ternary(2); divisor = new Ternary(0); results = dividend.divide(divisor); fail("Divide(2/0): Should have caused ArithmeticException"); }catch(ArithmeticException ae){ // good } } public void testSqrt() { if(true) { assertTrue("SKIPPING testSqrt", true); return; } assertEquals("SQRT", new Ternary(3), (new Ternary(15)).sqrt()); assertEquals("SQRT", new Ternary(4), (new Ternary(16)).sqrt()); assertEquals("SQRT", new Ternary(4), (new Ternary(17)).sqrt()); assertEquals("SQRT", new Ternary(6), (new Ternary(48)).sqrt()); assertEquals("SQRT", new Ternary(7), (new Ternary(49)).sqrt()); assertEquals("SQRT", new Ternary(7), (new Ternary(50)).sqrt()); assertEquals("SQRT", new Ternary(41), (new Ternary(1702)).sqrt()); assertEquals("SQRT", new Ternary(41), (new Ternary(1703)).sqrt()); assertEquals("SQRT", new Ternary(41), (new Ternary(1704)).sqrt()); assertEquals("SQRT", new Ternary(10), (new Ternary(100)).sqrt()); } public void testAbs() { assertEquals("SQRT", new Ternary(5), (new Ternary(5)).abs()); assertEquals("SQRT", new Ternary(5), (new Ternary(-5)).abs()); assertEquals("SQRT", new Ternary(0), (new Ternary(0)).abs()); } } */