/*
* @(#)Ternary.java 1.0 Mar 7, 2008
*
* The MIT License
*
* Copyright (c) 2008 Malachi de AElfweald
*
* 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
{
protected BigInteger biThree = BigInteger.valueOf(3);
protected BigDecimal bdThree = new BigDecimal(biThree);
protected CopyOnWriteArrayList 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();
}
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
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 newTrits = new CopyOnWriteArrayList();
for(int i=0; i
newTrits.addAll(trits);
trits = newTrits;
}
public void shiftRight(){shiftRight(1);}
public void shiftRight(int num)
{
ensureCapacity(trits.size() + num);
for(int i=0; i
}
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
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
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
Ternary row = new Ternary();
for(int posA=0; 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, Comparator
{
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 java.util.Hashtable.
*
* The general contract of hashCode is: - Whenever it is invoked on the same object more than once
* during an execution of a Java application, the hashCode method must consistently return the same integer,
* provided no information used in equals 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. - If two objects are
* equal according to the equals(Object) method, then calling the hashCode method on each of the
* two objects must produce the same integer result. - It is not required that if two objects are unequal
* according to the {@link Object#equals(Object)} method, then calling the hashCode 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.
*
* As much as is reasonably practical, the hashCode method defined by class Object 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 JavaTM
* 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());
}
}
*/