Bugzilla 47598 - Improved formula evaluator number comparison

git-svn-id: https://svn.apache.org/repos/asf/poi/trunk@798771 13f79535-47bb-0310-9956-ffa450edef68

7 files changed, 871 insertions, 221 deletions

diff --git a/src/java/org/apache/poi/hssf/record/formula/eval/RelationalOperationEval.java b/src/java/org/apache/poi/hssf/record/formula/eval/RelationalOperationEval.java
index c678507aab..f54b7cd2bc 100644
--- a/src/java/org/apache/poi/hssf/record/formula/eval/RelationalOperationEval.java
+++ b/src/java/org/apache/poi/hssf/record/formula/eval/RelationalOperationEval.java
@@ -17,6 +17,8 @@
 
 package org.apache.poi.hssf.record.formula.eval;
 
+import org.apache.poi.ss.util.NumberComparer;
+
 /**
  * Base class for all comparison operator evaluators
  *
@@ -108,8 +110,7 @@ public abstract class RelationalOperationEval implements OperationEval {
 			if (vb instanceof NumberEval) {
 				NumberEval nA = (NumberEval) va;
 				NumberEval nB = (NumberEval) vb;
-				// Excel considers -0.0 < 0.0 which is the same as Double.compare()
-				return Double.compare(nA.getNumberValue(), nB.getNumberValue());
+				return NumberComparer.compare(nA.getNumberValue(), nB.getNumberValue());
 			}
 		}
 		throw new IllegalArgumentException("Bad operand types (" + va.getClass().getName() + "), ("
@@ -126,7 +127,7 @@ public abstract class RelationalOperationEval implements OperationEval {
 		}
 		if (v instanceof NumberEval) {
 			NumberEval ne = (NumberEval) v;
-			return Double.compare(0, ne.getNumberValue());
+			return NumberComparer.compare(0.0, ne.getNumberValue());
 		}
 		if (v instanceof StringEval) {
 			StringEval se = (StringEval) v;
diff --git a/src/java/org/apache/poi/ss/util/ExpandedDouble.java b/src/java/org/apache/poi/ss/util/ExpandedDouble.java
new file mode 100644
index 0000000000..41827df044
--- /dev/null
+++ b/src/java/org/apache/poi/ss/util/ExpandedDouble.java
@@ -0,0 +1,98 @@
+/* ====================================================================

+   Licensed to the Apache Software Foundation (ASF) under one or more

+   contributor license agreements.  See the NOTICE file distributed with

+   this work for additional information regarding copyright ownership.

+   The ASF licenses this file to You under the Apache License, Version 2.0

+   (the "License"); you may not use this file except in compliance with

+   the License.  You may obtain a copy of the License at

+

+       http://www.apache.org/licenses/LICENSE-2.0

+

+   Unless required by applicable law or agreed to in writing, software

+   distributed under the License is distributed on an "AS IS" BASIS,

+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

+   See the License for the specific language governing permissions and

+   limitations under the License.

+==================================================================== */

+

+package org.apache.poi.ss.util;

+

+import java.math.BigInteger;

+import static org.apache.poi.ss.util.IEEEDouble.*;

+

+/**

+ * Represents a 64 bit IEEE double quantity expressed with both decimal and binary exponents

+ * Does not handle negative numbers or zero

+ * <p/>

+ * The value of a {@link ExpandedDouble} is given by<br/>

+ * <tt> a &times; 2<sup>b</sup></tt>

+ * <br/>

+ * where:<br/>

+ *

+ * <tt>a</tt> = <i>significand</i><br/>

+ * <tt>b</tt> = <i>binaryExponent</i> - bitLength(significand) + 1<br/>

+ *

+ * @author Josh Micich

+ */

+final class ExpandedDouble {

+	private static final BigInteger BI_FRAC_MASK = BigInteger.valueOf(FRAC_MASK);

+	private static final BigInteger BI_IMPLIED_FRAC_MSB = BigInteger.valueOf(FRAC_ASSUMED_HIGH_BIT);

+

+	private static BigInteger getFrac(long rawBits) {

+		return BigInteger.valueOf(rawBits).and(BI_FRAC_MASK).or(BI_IMPLIED_FRAC_MSB).shiftLeft(11);

+	}

+

+

+	public static ExpandedDouble fromRawBitsAndExponent(long rawBits, int exp) {

+		return new ExpandedDouble(getFrac(rawBits), exp);

+	}

+

+	/**

+	 * Always 64 bits long (MSB, bit-63 is '1')

+	 */

+	private final BigInteger _significand;

+	private final int _binaryExponent;

+

+	public ExpandedDouble(long rawBits) {

+		int biasedExp = (int) (rawBits >> 52);

+		if (biasedExp == 0) {

+			// sub-normal numbers

+			BigInteger frac = BigInteger.valueOf(rawBits).and(BI_FRAC_MASK);

+			int expAdj = 64 - frac.bitLength();

+			_significand = frac.shiftLeft(expAdj);

+			_binaryExponent = (biasedExp & 0x07FF) - 1023 - expAdj;

+		} else {

+			BigInteger frac = getFrac(rawBits);

+			_significand = frac;

+			_binaryExponent = (biasedExp & 0x07FF) - 1023;

+		}

+	}

+

+	ExpandedDouble(BigInteger frac, int binaryExp) {

+		if (frac.bitLength() != 64) {

+			throw new IllegalArgumentException("bad bit length");

+		}

+		_significand = frac;

+		_binaryExponent = binaryExp;

+	}

+

+

+	/**

+	 * Convert to an equivalent {@link NormalisedDecimal} representation having 15 decimal digits of precision in the

+	 * non-fractional bits of the significand.

+	 */

+	public NormalisedDecimal normaliseBaseTen() {

+		return NormalisedDecimal.create(_significand, _binaryExponent);

+	}

+

+	/**

+	 * @return the number of non-fractional bits after the MSB of the significand

+	 */

+	public int getBinaryExponent() {

+		return _binaryExponent;

+	}

+

+	public BigInteger getSignificand() {

+		return _significand;

+	}

+}

diff --git a/src/java/org/apache/poi/ss/util/IEEEDouble.java b/src/java/org/apache/poi/ss/util/IEEEDouble.java
new file mode 100644
index 0000000000..f5a42edca6
--- /dev/null
+++ b/src/java/org/apache/poi/ss/util/IEEEDouble.java
@@ -0,0 +1,44 @@
+/* ====================================================================
+   Licensed to the Apache Software Foundation (ASF) under one or more
+   contributor license agreements.  See the NOTICE file distributed with
+   this work for additional information regarding copyright ownership.
+   The ASF licenses this file to You under the Apache License, Version 2.0
+   (the "License"); you may not use this file except in compliance with
+   the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+==================================================================== */
+
+package org.apache.poi.ss.util;
+
+
+/**
+ * For working with the internals of IEEE 754-2008 'binary64' (double precision) floating point numbers
+ *
+ * @author Josh Micich
+ */
+final class IEEEDouble {
+	private static final long EXPONENT_MASK = 0x7FF0000000000000L;
+	private static final int  EXPONENT_SHIFT = 52;
+	public static final long FRAC_MASK = 0x000FFFFFFFFFFFFFL;
+	public static final int  EXPONENT_BIAS  = 1023;
+	public static final long FRAC_ASSUMED_HIGH_BIT = ( 1L<<EXPONENT_SHIFT );
+	/**
+	 * The value the exponent field gets for all <i>NaN</i> and <i>Infinity</i> values
+	 */
+	public static final int BIASED_EXPONENT_SPECIAL_VALUE = 0x07FF;
+
+	/**
+	 * @param rawBits the 64 bit binary representation of the double value
+	 * @return the top 12 bits (sign and biased exponent value)
+	 */
+	public static int getBiasedExponent(long rawBits) {
+		return (int) ((rawBits & EXPONENT_MASK) >> EXPONENT_SHIFT);
+	}
+}
diff --git a/src/java/org/apache/poi/ss/util/MutableFPNumber.java b/src/java/org/apache/poi/ss/util/MutableFPNumber.java
new file mode 100644
index 0000000000..2ae93e675c
--- /dev/null
+++ b/src/java/org/apache/poi/ss/util/MutableFPNumber.java
@@ -0,0 +1,209 @@
+/* ====================================================================

+   Licensed to the Apache Software Foundation (ASF) under one or more

+   contributor license agreements.  See the NOTICE file distributed with

+   this work for additional information regarding copyright ownership.

+   The ASF licenses this file to You under the Apache License, Version 2.0

+   (the "License"); you may not use this file except in compliance with

+   the License.  You may obtain a copy of the License at

+

+       http://www.apache.org/licenses/LICENSE-2.0

+

+   Unless required by applicable law or agreed to in writing, software

+   distributed under the License is distributed on an "AS IS" BASIS,

+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

+   See the License for the specific language governing permissions and

+   limitations under the License.

+==================================================================== */

+

+package org.apache.poi.ss.util;

+

+import java.math.BigInteger;

+

+final class MutableFPNumber {

+

+

+	// TODO - what about values between (10<sup>14</sup>-0.5) and (10<sup>14</sup>-0.05) ?

+	/**

+	 * The minimum value in 'Base-10 normalised form'.<br/>

+	 * When {@link #_binaryExponent} == 46 this is the the minimum {@link #_frac} value

+	 *  (10<sup>14</sup>-0.05) * 2^17

+	 *  <br/>

+	 *  Values between (10<sup>14</sup>-0.05) and 10<sup>14</sup> will be represented as '1'

+	 *  followed by 14 zeros.

+	 *  Values less than (10<sup>14</sup>-0.05) will get shifted by one more power of 10

+	 *

+	 *  This frac value rounds to '1' followed by fourteen zeros with an incremented decimal exponent

+	 */

+	private static final BigInteger BI_MIN_BASE = new BigInteger("0B5E620F47FFFE666", 16);

+	/**

+	 * For 'Base-10 normalised form'<br/>

+	 * The maximum {@link #_frac} value when {@link #_binaryExponent} == 49

+	 * (10^15-0.5) * 2^14

+	 */

+	private static final BigInteger BI_MAX_BASE = new BigInteger("0E35FA9319FFFE000", 16);

+

+	/**

+	 * Width of a long

+	 */

+	private static final int C_64 = 64;

+

+	/**

+	 * Minimum precision after discarding whole 32-bit words from the significand

+	 */

+	private static final int MIN_PRECISION = 72;

+	private BigInteger _significand;

+	private int _binaryExponent;

+	public MutableFPNumber(BigInteger frac, int binaryExponent) {

+		_significand = frac;

+		_binaryExponent = binaryExponent;

+	}

+

+

+	public MutableFPNumber copy() {

+		return new MutableFPNumber(_significand, _binaryExponent);

+	}

+	public void normalise64bit() {

+		int oldBitLen = _significand.bitLength();

+		int sc = oldBitLen - C_64;

+		if (sc == 0) {

+			return;

+		}

+		if (sc < 0) {

+			throw new IllegalStateException("Not enough precision");

+		}

+		_binaryExponent += sc;

+		if (sc > 32) {

+			int highShift = (sc-1) & 0xFFFFE0;

+			_significand = _significand.shiftRight(highShift);

+			sc -= highShift;

+			oldBitLen -= highShift;

+		}

+		if (sc < 1) {

+			throw new IllegalStateException();

+		}

+		_significand = Rounder.round(_significand, sc);

+		if (_significand.bitLength() > oldBitLen) {

+			sc++;

+			_binaryExponent++;

+		}

+		_significand = _significand.shiftRight(sc);

+	}

+	public int get64BitNormalisedExponent() {

+		return _binaryExponent + _significand.bitLength() - C_64;

+

+	}

+

+	@Override

+	public boolean equals(Object obj) {

+		MutableFPNumber other = (MutableFPNumber) obj;

+		if (_binaryExponent != other._binaryExponent) {

+			return false;

+		}

+		return _significand.equals(other._significand);

+	}

+	public boolean isBelowMaxRep() {

+		int sc = _significand.bitLength() - C_64;

+		return _significand.compareTo(BI_MAX_BASE.shiftLeft(sc)) < 0;

+	}

+	public boolean isAboveMinRep() {

+		int sc = _significand.bitLength() - C_64;

+		return _significand.compareTo(BI_MIN_BASE.shiftLeft(sc)) > 0;

+	}

+	public NormalisedDecimal createNormalisedDecimal(int pow10) {

+		// missingUnderBits is (0..3)

+		int missingUnderBits = _binaryExponent-39;

+		int fracPart = (_significand.intValue() << missingUnderBits) & 0xFFFF80;

+		long wholePart = _significand.shiftRight(C_64-_binaryExponent-1).longValue();

+		return new NormalisedDecimal(wholePart, fracPart, pow10);

+	}

+	public void multiplyByPowerOfTen(int pow10) {

+		TenPower tp = TenPower.getInstance(Math.abs(pow10));

+		if (pow10 < 0) {

+			mulShift(tp._divisor, tp._divisorShift);

+		} else {

+			mulShift(tp._multiplicand, tp._multiplierShift);

+		}

+	}

+	private void mulShift(BigInteger multiplicand, int multiplierShift) {

+		_significand = _significand.multiply(multiplicand);

+		_binaryExponent += multiplierShift;

+		// check for too much precision

+		int sc = (_significand.bitLength() - MIN_PRECISION) & 0xFFFFFFE0;

+		// mask makes multiples of 32 which optimises BigInteger.shiftRight

+		if (sc > 0) {

+			// no need to round because we have at least 8 bits of extra precision

+			_significand = _significand.shiftRight(sc);

+			_binaryExponent += sc;

+		}

+	}

+

+	private static final class Rounder {

+		private static final BigInteger[] HALF_BITS;

+

+		static {

+			BigInteger[] bis = new BigInteger[33];

+			long acc=1;

+			for (int i = 1; i < bis.length; i++) {

+				bis[i] = BigInteger.valueOf(acc);

+				acc <<=1;

+			}

+			HALF_BITS = bis;

+		}

+		/**

+		 * @param nBits number of bits to shift right

+		 */

+		public static BigInteger round(BigInteger bi, int nBits) {

+			if (nBits < 1) {

+				return bi;

+			}

+			return bi.add(HALF_BITS[nBits]);

+		}

+	}

+

+	/**

+	 * Holds values for quick multiplication and division by 10

+	 */

+	private static final class TenPower {

+		private static final BigInteger FIVE = new BigInteger("5");

+		private static final TenPower[] _cache = new TenPower[350];

+

+		public final BigInteger _multiplicand;

+		public final BigInteger _divisor;

+		public final int _divisorShift;

+		public final int _multiplierShift;

+

+		private TenPower(int index) {

+			BigInteger fivePowIndex = FIVE.pow(index);

+

+			int bitsDueToFiveFactors = fivePowIndex.bitLength();

+			int px = 80 + bitsDueToFiveFactors;

+			BigInteger fx = BigInteger.ONE.shiftLeft(px).divide(fivePowIndex);

+			int adj = fx.bitLength() - 80;

+			_divisor = fx.shiftRight(adj);

+			bitsDueToFiveFactors -= adj;

+

+			_divisorShift = -(bitsDueToFiveFactors+index+80);

+			int sc = fivePowIndex.bitLength() - 68;

+			if (sc > 0) {

+				_multiplierShift = index + sc;

+				_multiplicand = fivePowIndex.shiftRight(sc);

+			} else {

+				_multiplierShift = index;

+				_multiplicand = fivePowIndex;

+			}

+		}

+

+		static TenPower getInstance(int index) {

+			TenPower result = _cache[index];

+			if (result == null) {

+				result = new TenPower(index);

+				_cache[index] = result;

+			}

+			return result;

+		}

+	}

+

+	public ExpandedDouble createExpandedDouble() {

+		return new ExpandedDouble(_significand, _binaryExponent);

+	}

+}

diff --git a/src/java/org/apache/poi/ss/util/NormalisedDecimal.java b/src/java/org/apache/poi/ss/util/NormalisedDecimal.java
new file mode 100644
index 0000000000..84f4d72851
--- /dev/null
+++ b/src/java/org/apache/poi/ss/util/NormalisedDecimal.java
@@ -0,0 +1,271 @@
+/* ====================================================================

+   Licensed to the Apache Software Foundation (ASF) under one or more

+   contributor license agreements.  See the NOTICE file distributed with

+   this work for additional information regarding copyright ownership.

+   The ASF licenses this file to You under the Apache License, Version 2.0

+   (the "License"); you may not use this file except in compliance with

+   the License.  You may obtain a copy of the License at

+

+       http://www.apache.org/licenses/LICENSE-2.0

+

+   Unless required by applicable law or agreed to in writing, software

+   distributed under the License is distributed on an "AS IS" BASIS,

+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

+   See the License for the specific language governing permissions and

+   limitations under the License.

+==================================================================== */

+

+package org.apache.poi.ss.util;

+

+import java.math.BigDecimal;

+import java.math.BigInteger;

+

+/**

+ * Represents a transformation of a 64 bit IEEE double quantity having a decimal exponent and a

+ * fixed point (15 decimal digit) significand.  Some quirks of Excel's calculation behaviour are

+ * simpler to reproduce with numeric quantities in this format.  This class is currently used to

+ * help:

+ * <ol>

+ * <li>Comparison operations</li>

+ * <li>Conversions to text</li>

+ * </ol>

+ *

+ * <p/>

+ * This class does not handle negative numbers or zero.

+ * <p/>

+ * The value of a {@link NormalisedDecimal} is given by<br/>

+ * <tt> significand &times; 10<sup>decimalExponent</sup></tt>

+ * <br/>

+ * where:<br/>

+ *

+ * <tt>significand</tt> = wholePart + fractionalPart / 2<sup>24</sup><br/>

+ *

+ * @author Josh Micich

+ */

+final class NormalisedDecimal {

+	/**

+	 * Number of powers of ten contained in the significand

+	 */

+	private static final int EXPONENT_OFFSET = 14;

+

+	private static final BigDecimal BD_2_POW_24 = new BigDecimal(BigInteger.ONE.shiftLeft(24));

+

+	/**

+	 * log<sub>10</sub>(2)&times;2<sup>20</sup>

+	 */

+	private static final int LOG_BASE_10_OF_2_TIMES_2_POW_20 = 315653; // 315652.8287

+

+	/**

+	 * 2<sup>19</sup>

+	 */

+	private static final int C_2_POW_19 = 1 << 19;

+

+

+	/**

+	 * the value of {@link #_fractionalPart} that represents 0.5

+	 */

+	private static final int FRAC_HALF = 0x800000;

+

+	/**

+	 * 10<sup>15</sup>

+	 */

+	private static final long MAX_REP_WHOLE_PART = 0x38D7EA4C68000L;

+

+

+

+	public static NormalisedDecimal create(BigInteger frac, int binaryExponent) {

+		// estimate pow2&pow10 first, perform optional mulShift, then normalize

+		int pow10;

+		if (binaryExponent > 49 || binaryExponent < 46) {

+

+			// working with ints (left shifted 20) instead of doubles

+			// x = 14.5 - binaryExponent * log10(2);

+			int x = (29 << 19) - binaryExponent * LOG_BASE_10_OF_2_TIMES_2_POW_20;

+			x += C_2_POW_19; // round

+			pow10 = -(x >> 20);

+		} else {

+			pow10 = 0;

+		}

+		MutableFPNumber cc = new MutableFPNumber(frac, binaryExponent);

+		if (pow10 != 0) {

+			cc.multiplyByPowerOfTen(-pow10);

+		}

+

+		switch (cc.get64BitNormalisedExponent()) {

+			case 46:

+				if (cc.isAboveMinRep()) {

+					break;

+				}

+			case 44:

+			case 45:

+				cc.multiplyByPowerOfTen(1);

+				pow10--;

+				break;

+			case 47:

+			case 48:

+				break;

+			case 49:

+				if (cc.isBelowMaxRep()) {

+					break;

+				}

+			case 50:

+				cc.multiplyByPowerOfTen(-1);

+				pow10++;

+				break;

+

+			default:

+				throw new IllegalStateException("Bad binary exp " + cc.get64BitNormalisedExponent() + ".");

+		}

+		cc.normalise64bit();

+

+		return cc.createNormalisedDecimal(pow10);

+	}

+

+	/**

+	 * Rounds at the digit with value 10<sup>decimalExponent</sup>

+	 */

+	public NormalisedDecimal roundUnits() {

+		long wholePart = _wholePart;

+		if (_fractionalPart >= FRAC_HALF) {

+			wholePart++;

+		}

+

+		int de = _relativeDecimalExponent;

+

+		if (wholePart < MAX_REP_WHOLE_PART) {

+			return new NormalisedDecimal(wholePart, 0, de);

+		}

+		return new NormalisedDecimal(wholePart/10, 0, de+1);

+	}

+

+	/**

+	 * The decimal exponent increased by one less than the digit count of {@link #_wholePart}

+	 */

+	private final int _relativeDecimalExponent;

+	/**

+	 * The whole part of the significand (typically 15 digits).

+	 *

+	 * 47-50 bits long (MSB may be anywhere from bit 46 to 49)

+	 * LSB is units bit.

+	 */

+	private final long _wholePart;

+	/**

+	 * The fractional part of the significand.

+	 * 24 bits (only top 14-17 bits significant): a value between 0x000000 and 0xFFFF80

+	 */

+	private final int _fractionalPart;

+

+

+	NormalisedDecimal(long wholePart, int fracPart, int decimalExponent) {

+		_wholePart = wholePart;

+		_fractionalPart = fracPart;

+		_relativeDecimalExponent = decimalExponent;

+	}

+

+

+	/**

+	 * Convert to an equivalent {@link ExpandedDouble} representation (binary frac and exponent).

+	 * The resulting transformed object is easily converted to a 64 bit IEEE double:

+	 * <ul>

+	 * <li>bits 2-53 of the {@link #getSignificand()} become the 52 bit 'fraction'.</li>

+	 * <li>{@link #getBinaryExponent()} is biased by 1023 to give the 'exponent'.</li>

+	 * </ul>

+	 * The sign bit must be obtained from somewhere else.

+	 * @return a new {@link NormalisedDecimal} normalised to base 2 representation.

+	 */

+	public ExpandedDouble normaliseBaseTwo() {

+		MutableFPNumber cc = new MutableFPNumber(composeFrac(), 39);

+		cc.multiplyByPowerOfTen(_relativeDecimalExponent);

+		cc.normalise64bit();

+		return cc.createExpandedDouble();

+	}

+

+	/**

+	 * @return the significand as a fixed point number (with 24 fraction bits and 47-50 whole bits)

+	 */

+	BigInteger composeFrac() {

+		long wp = _wholePart;

+		int fp = _fractionalPart;

+		return new BigInteger(new byte[] {

+				(byte) (wp >> 56), // N.B. assuming sign bit is zero

+				(byte) (wp >> 48),

+				(byte) (wp >> 40),

+				(byte) (wp >> 32),

+				(byte) (wp >> 24),

+				(byte) (wp >> 16),

+				(byte) (wp >>  8),

+				(byte) (wp >>  0),

+				(byte) (fp >> 16),

+				(byte) (fp >> 8),

+				(byte) (fp >> 0),

+		});

+	}

+

+	public String getSignificantDecimalDigits() {

+		return Long.toString(_wholePart);

+	}

+	/**

+	 * Rounds the first whole digit position (considers only units digit, not frational part).

+	 * Caller should check total digit count of result to see whether the rounding operation caused

+	 * a carry out of the most significant digit

+	 */

+	public String getSignificantDecimalDigitsLastDigitRounded() {

+		long wp = _wholePart + 5; // rounds last digit

+		StringBuilder sb = new StringBuilder(24);

+		sb.append(wp);

+		sb.setCharAt(sb.length()-1, '0');

+		return sb.toString();

+	}

+

+	/**

+	 * @return the number of powers of 10 which have been extracted from the significand and binary exponent.

+	 */

+	public int getDecimalExponent() {

+		return _relativeDecimalExponent+EXPONENT_OFFSET;

+	}

+

+	/**

+	 * assumes both this and other are normalised

+	 */

+	public int compareNormalised(NormalisedDecimal other) {

+		int cmp = _relativeDecimalExponent - other._relativeDecimalExponent;

+		if (cmp != 0) {

+			return cmp;

+		}

+		if (_wholePart > other._wholePart) {

+			return 1;

+		}

+		if (_wholePart < other._wholePart) {

+			return -1;

+		}

+		return _fractionalPart - other._fractionalPart;

+	}

+	public BigDecimal getFractionalPart() {

+		return new BigDecimal(_fractionalPart).divide(BD_2_POW_24);

+	}

+

+	private String getFractionalDigits() {

+		if (_fractionalPart == 0) {

+			return "0";

+		}

+		return getFractionalPart().toString().substring(2);

+	}

+

+	@Override

+	public String toString() {

+

+		StringBuilder sb = new StringBuilder();

+		sb.append(getClass().getName());

+		sb.append(" [");

+		String ws = String.valueOf(_wholePart);

+		sb.append(ws.charAt(0));

+		sb.append('.');

+		sb.append(ws.substring(1));

+		sb.append(' ');

+		sb.append(getFractionalDigits());

+		sb.append("E");

+		sb.append(getDecimalExponent());

+		sb.append("]");

+		return sb.toString();

+	}

+}

diff --git a/src/java/org/apache/poi/ss/util/NumberComparer.java b/src/java/org/apache/poi/ss/util/NumberComparer.java
new file mode 100644
index 0000000000..49a27d2aab
--- /dev/null
+++ b/src/java/org/apache/poi/ss/util/NumberComparer.java
@@ -0,0 +1,173 @@
+/* ====================================================================
+   Licensed to the Apache Software Foundation (ASF) under one or more
+   contributor license agreements.  See the NOTICE file distributed with
+   this work for additional information regarding copyright ownership.
+   The ASF licenses this file to You under the Apache License, Version 2.0
+   (the "License"); you may not use this file except in compliance with
+   the License.  You may obtain a copy of the License at
+
+	   http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+==================================================================== */
+
+package org.apache.poi.ss.util;
+
+import static org.apache.poi.ss.util.IEEEDouble.*;
+
+/**
+ * Excel compares numbers using different rules to those of java, so
+ *  {@link Double#compare(double, double)} won't do.
+ *
+ *
+ * @author Josh Micich
+ */
+public final class NumberComparer {
+
+	/**
+	 * This class attempts to reproduce Excel's behaviour for comparing numbers.  Results are
+	 * mostly the same as those from {@link Double#compare(double, double)} but with some
+	 * rounding.  For numbers that are very close, this code converts to a format having 15
+	 * decimal digits of precision and a decimal exponent, before completing the comparison.
+	 * <p/>
+	 * In Excel formula evaluation, expressions like "(0.06-0.01)=0.05" evaluate to "TRUE" even
+	 * though the equivalent java expression is <code>false</code>.  In examples like this,
+	 * Excel achieves the effect by having additional logic for comparison operations.
+	 * <p/>
+	 * <p/>
+	 * Note - Excel also gives special treatment to expressions like "0.06-0.01-0.05" which
+	 * evaluates to "0" (in java, rounding anomalies give a result of 6.9E-18).  The special
+	 * behaviour here is for different reasons to the example above:  If the last operator in a
+	 * cell formula is '+' or '-' and the result is less than 2<sup>50</sup> times smaller than
+	 * first operand, the result is rounded to zero.
+	 * Needless to say, the two rules are not consistent and it is relatively easy to find
+	 * examples that satisfy<br/>
+	 * "A=B" is "TRUE" but "A-B" is not "0"<br/>
+	 * and<br/>
+	 * "A=B" is "FALSE" but "A-B" is "0"<br/>
+	 * <br/>
+	 * This rule (for rounding the result of a final addition or subtraction), has not been
+	 * implemented in POI (as of Jul-2009).
+	 *
+	 * @return <code>negative, 0, or positive</code> according to the standard Excel comparison
+	 * of values <tt>a</tt> and <tt>b</tt>.
+	 */
+	public static int compare(double a, double b) {
+		long rawBitsA = Double.doubleToLongBits(a);
+		long rawBitsB = Double.doubleToLongBits(b);
+
+		int biasedExponentA = getBiasedExponent(rawBitsA);
+		int biasedExponentB = getBiasedExponent(rawBitsB);
+
+		if (biasedExponentA == BIASED_EXPONENT_SPECIAL_VALUE) {
+			throw new IllegalArgumentException("Special double values are not allowed: " + toHex(a));
+		}
+		if (biasedExponentB == BIASED_EXPONENT_SPECIAL_VALUE) {
+			throw new IllegalArgumentException("Special double values are not allowed: " + toHex(a));
+		}
+
+		int cmp;
+
+		// sign bit is in the same place for long and double:
+		boolean aIsNegative = rawBitsA < 0;
+		boolean bIsNegative = rawBitsB < 0;
+
+		// compare signs
+		if (aIsNegative != bIsNegative) {
+			// Excel seems to have 'normal' comparison behaviour around zero (no rounding)
+			// even -0.0 < +0.0 (which is not quite the initial conclusion of bug 47198)
+			return aIsNegative ? -1 : +1;
+		}
+
+		// then compare magnitudes (IEEE 754 has exponent bias specifically to allow this)
+		cmp = biasedExponentA - biasedExponentB;
+		int absExpDiff = Math.abs(cmp);
+		if (absExpDiff > 1) {
+			return aIsNegative ? -cmp : cmp;
+		}
+
+		if (absExpDiff == 1) {
+			// special case exponent differs by 1.  There is still a chance that with rounding the two quantities could end up the same
+
+		} else {
+			// else - sign and exponents equal
+			if (rawBitsA == rawBitsB) {
+				// fully equal - exit here
+				return 0;
+			}
+		}
+		if (biasedExponentA == 0) {
+			if (biasedExponentB == 0) {
+				return compareSubnormalNumbers(rawBitsA & FRAC_MASK, rawBitsB & FRAC_MASK, aIsNegative);
+			}
+			// else biasedExponentB is 1
+			return -compareAcrossSubnormalThreshold(rawBitsB, rawBitsA, aIsNegative);
+		}
+		if (biasedExponentB == 0) {
+			// else biasedExponentA is 1
+			return +compareAcrossSubnormalThreshold(rawBitsA, rawBitsB, aIsNegative);
+		}
+
+		// sign and exponents same, but fractional bits are different
+
+		ExpandedDouble edA = ExpandedDouble.fromRawBitsAndExponent(rawBitsA, biasedExponentA - EXPONENT_BIAS);
+		ExpandedDouble edB = ExpandedDouble.fromRawBitsAndExponent(rawBitsB, biasedExponentB - EXPONENT_BIAS);
+		NormalisedDecimal ndA = edA.normaliseBaseTen().roundUnits();
+		NormalisedDecimal ndB = edB.normaliseBaseTen().roundUnits();
+		cmp = ndA.compareNormalised(ndB);
+		if (aIsNegative) {
+			return -cmp;
+		}
+		return cmp;
+	}
+
+	/**
+	 * If both numbers are subnormal, Excel seems to use standard comparison rules
+	 */
+	private static int compareSubnormalNumbers(long fracA, long fracB, boolean isNegative) {
+		int cmp = fracA > fracB ? +1 : fracA < fracB ? -1 : 0;
+
+		return isNegative ? -cmp : cmp;
+	}
+
+
+
+	/**
+	 * Usually any normal number is greater (in magnitude) than any subnormal number.
+	 * However there are some anomalous cases around the threshold where Excel produces screwy results
+	 * @param isNegative both values are either negative or positive. This parameter affects the sign of the comparison result
+	 * @return usually <code>isNegative ? -1 : +1</code>
+	 */
+	private static int compareAcrossSubnormalThreshold(long normalRawBitsA, long subnormalRawBitsB, boolean isNegative) {
+		long fracB = subnormalRawBitsB & FRAC_MASK;
+		if (fracB == 0) {
+			// B is zero, so A is definitely greater than B
+			return isNegative ? -1 : +1;
+		}
+		long fracA = normalRawBitsA & FRAC_MASK;
+		if (fracA <= 0x0000000000000007L && fracB >= 0x000FFFFFFFFFFFFAL) {
+			// Both A and B close to threshold - weird results
+			if (fracA == 0x0000000000000007L && fracB == 0x000FFFFFFFFFFFFAL) {
+				// special case
+				return 0;
+			}
+			// exactly the opposite
+			return isNegative ? +1 : -1;
+		}
+		// else - typical case A and B is not close to threshold
+		return isNegative ? -1 : +1;
+	}
+
+
+
+	/**
+	 * for formatting double values in error messages
+	 */
+	private static String toHex(double a) {
+		return "0x" + Long.toHexString(Double.doubleToLongBits(a)).toUpperCase();
+	}
+}
diff --git a/src/java/org/apache/poi/ss/util/NumberToTextConverter.java b/src/java/org/apache/poi/ss/util/NumberToTextConverter.java
index efcb012fcc..c5b8d936b7 100644
--- a/src/java/org/apache/poi/ss/util/NumberToTextConverter.java
+++ b/src/java/org/apache/poi/ss/util/NumberToTextConverter.java
@@ -17,8 +17,6 @@
 
 package org.apache.poi.ss.util;
 
-import java.math.BigDecimal;
-import java.math.BigInteger;
 
 /**
  * Excel converts numbers to text with different rules to those of java, so
@@ -113,21 +111,9 @@ import java.math.BigInteger;
  */
 public final class NumberToTextConverter {
 
-	private static final long expMask  = 0x7FF0000000000000L;
-	private static final long FRAC_MASK= 0x000FFFFFFFFFFFFFL;
-	private static final int  EXPONENT_SHIFT = 52;
-	private static final int  FRAC_BITS_WIDTH = EXPONENT_SHIFT;
-	private static final int  EXPONENT_BIAS  = 1023;
-	private static final long FRAC_ASSUMED_HIGH_BIT = ( 1L<<EXPONENT_SHIFT );
-
 	private static final long EXCEL_NAN_BITS = 0xFFFF0420003C0000L;
 	private static final int MAX_TEXT_LEN = 20;
 
-	private static final int DEFAULT_COUNT_SIGNIFICANT_DIGITS = 15;
-	private static final int MAX_EXTRA_ZEROS = MAX_TEXT_LEN - DEFAULT_COUNT_SIGNIFICANT_DIGITS;
-	private static final float LOG2_10 = 3.32F;
-
-
 	private NumberToTextConverter() {
 		// no instances of this class
 	}
@@ -149,186 +135,110 @@ public final class NumberToTextConverter {
 		if (isNegative) {
 			rawBits &= 0x7FFFFFFFFFFFFFFFL;
 		}
-
-		int biasedExponent = (int) ((rawBits & expMask) >> EXPONENT_SHIFT);
-		if (biasedExponent == 0) {
+		if (rawBits == 0) {
+			return isNegative ? "-0" : "0";
+		}
+		ExpandedDouble ed = new ExpandedDouble(rawBits);
+		if (ed.getBinaryExponent() < -1022) {
 			// value is 'denormalised' which means it is less than 2^-1022
 			// excel displays all these numbers as zero, even though calculations work OK
 			return isNegative ? "-0" : "0";
 		}
-
-		int exponent = biasedExponent - EXPONENT_BIAS;
-
-		long fracBits = FRAC_ASSUMED_HIGH_BIT | rawBits & FRAC_MASK;
-
-
-		// Start by converting double value to BigDecimal
-		BigDecimal bd;
-		if (biasedExponent == 0x07FF) {
+		if (ed.getBinaryExponent() == 1024) {
 			// Special number NaN /Infinity
+			// Normally one would not create HybridDecimal objects from these values
+			// except in these cases Excel really tries to render them as if they were normal numbers
 			if(rawBits == EXCEL_NAN_BITS) {
 				return "3.484840871308E+308";
 			}
 			// This is where excel really gets it wrong
-			// Special numbers like Infinity and Nan are interpreted according to
+			// Special numbers like Infinity and NaN are interpreted according to
 			// the standard rules below.
 			isNegative = false; // except that the sign bit is ignored
 		}
-		bd = convertToBigDecimal(exponent, fracBits);
-
-		return formatBigInteger(isNegative, bd.unscaledValue(), bd.scale());
-	}
-
-	private static BigDecimal convertToBigDecimal(int exponent, long fracBits) {
-		byte[] joob = {
-				(byte) (fracBits >> 48),
-				(byte) (fracBits >> 40),
-				(byte) (fracBits >> 32),
-				(byte) (fracBits >> 24),
-				(byte) (fracBits >> 16),
-				(byte) (fracBits >>  8),
-				(byte) (fracBits >>  0),
-		};
-
-		BigInteger bigInt = new BigInteger(joob);
-		int lastSigBitIndex = exponent-FRAC_BITS_WIDTH;
-		if(lastSigBitIndex < 0) {
-			BigInteger shifto = new BigInteger("1").shiftLeft(-lastSigBitIndex);
-			int scale = 1 -(int) (lastSigBitIndex/LOG2_10);
-			BigDecimal bd1 = new BigDecimal(bigInt);
-			BigDecimal bdShifto = new BigDecimal(shifto);
-			return bd1.divide(bdShifto, scale, BigDecimal.ROUND_HALF_UP);
+		NormalisedDecimal nd = ed.normaliseBaseTen();
+		StringBuilder sb = new StringBuilder(MAX_TEXT_LEN+1);
+		if (isNegative) {
+			sb.append('-');
 		}
-		BigInteger sl = bigInt.shiftLeft(lastSigBitIndex);
-		return new BigDecimal(sl);
+		convertToText(sb, nd);
+		return sb.toString();
 	}
-
-	private static String formatBigInteger(boolean isNegative, BigInteger unscaledValue, int scale) {
-
-		if (scale < 0) {
-			throw new RuntimeException("negative scale");
-		}
-
-		StringBuffer sb = new StringBuffer(unscaledValue.toString());
-		int numberOfLeadingZeros = -1;
-
-		int unscaledLength = sb.length();
-		if (scale > 0 && scale >= unscaledLength) {
-			// less than one
-			numberOfLeadingZeros = scale-unscaledLength;
-			formatLessThanOne(sb, numberOfLeadingZeros+1);
+	private static void convertToText(StringBuilder sb, NormalisedDecimal pnd) {
+		NormalisedDecimal rnd = pnd.roundUnits();
+		int decExponent = rnd.getDecimalExponent();
+		String decimalDigits;
+		if (Math.abs(decExponent)>98) {
+			decimalDigits = rnd.getSignificantDecimalDigitsLastDigitRounded();
+			if (decimalDigits.length() == 16) {
+				// rounding caused carry
+				decExponent++;
+			}
 		} else {
-			int decimalPointIndex = unscaledLength - scale;
-			formatGreaterThanOne(sb, decimalPointIndex);
-		}
-		if(isNegative) {
-			sb.insert(0, '-');
+			decimalDigits = rnd.getSignificantDecimalDigits();
 		}
-		return sb.toString();
-	}
-
-	private static int getNumberOfSignificantFiguresDisplayed(int exponent) {
-		int nLostDigits; // number of significand digits lost due big exponents
-		if(exponent > 99) {
-			// any exponent greater than 99 has 3 digits instead of 2
-			nLostDigits = 1;
-		} else if (exponent < -98) {
-			// For some weird reason on the negative side
-			// step is occurs from -98 to -99 (not from -99 to -100)
-			nLostDigits = 1;
+		int countSigDigits = countSignifantDigits(decimalDigits);
+		if (decExponent < 0) {
+			formatLessThanOne(sb, decimalDigits, decExponent, countSigDigits);
 		} else {
-			nLostDigits = 0;
+			formatGreaterThanOne(sb, decimalDigits, decExponent, countSigDigits);
 		}
-		return DEFAULT_COUNT_SIGNIFICANT_DIGITS - nLostDigits;
-	}
-
-	private static boolean needsScientificNotation(int nDigits) {
-		return nDigits > MAX_TEXT_LEN;
 	}
 
-	private static void formatGreaterThanOne(StringBuffer sb, int nIntegerDigits) {
+	private static void formatLessThanOne(StringBuilder sb, String decimalDigits, int decExponent,
+			int countSigDigits) {
+		int nLeadingZeros = -decExponent - 1;
+		int normalLength = 2 + nLeadingZeros + countSigDigits; // 2 == "0.".length()
 
-		int maxSigFigs = getNumberOfSignificantFiguresDisplayed(nIntegerDigits);
-		int decimalPointIndex = nIntegerDigits;
-		boolean roundCausedCarry = performRound(sb, 0, maxSigFigs);
-
-		int endIx = Math.min(maxSigFigs, sb.length()-1);
-
-		int nSigFigures;
-		if(roundCausedCarry) {
-			sb.insert(0, '1');
-			decimalPointIndex++;
-			nSigFigures = 1;
-		} else {
-			nSigFigures = countSignifantDigits(sb, endIx);
-		}
-
-		if(needsScientificNotation(decimalPointIndex)) {
-			sb.setLength(nSigFigures);
-			if (nSigFigures > 1) {
-				sb.insert(1, '.');
+		if (needsScientificNotation(normalLength)) {
+			sb.append(decimalDigits.charAt(0));
+			if (countSigDigits > 1) {
+    			sb.append('.');
+    			sb.append(decimalDigits.subSequence(1, countSigDigits));
 			}
-			sb.append("E+");
-			appendExp(sb, decimalPointIndex-1);
+			sb.append("E-");
+			appendExp(sb, -decExponent);
 			return;
 		}
-		if(isAllZeros(sb, decimalPointIndex, maxSigFigs)) {
-			sb.setLength(decimalPointIndex);
-			return;
+		sb.append("0.");
+		for (int i=nLeadingZeros; i>0; i--) {
+			sb.append('0');
 		}
-		// else some sig-digits after the decimal point
-		sb.setLength(nSigFigures);
-		sb.insert(decimalPointIndex, '.');
+		sb.append(decimalDigits.subSequence(0, countSigDigits));
 	}
 
-	/**
-	 * @param sb initially contains just the significant digits
-	 * @param pAbsExponent to be inserted (after "0.") at the start of the number
-	 */
-	private static void formatLessThanOne(StringBuffer sb, int pAbsExponent) {
-		if (sb.charAt(0) == 0) {
-			throw new IllegalArgumentException("First digit of significand should be non-zero");
+	private static void formatGreaterThanOne(StringBuilder sb, String decimalDigits, int decExponent, int countSigDigits) {
+
+		if (decExponent > 19) {
+			// scientific notation
+			sb.append(decimalDigits.charAt(0));
+			if (countSigDigits>1) {
+				sb.append('.');
+				sb.append(decimalDigits.subSequence(1, countSigDigits));
+			}
+			sb.append("E+");
+			appendExp(sb, decExponent);
+			return;
 		}
-		if (pAbsExponent < 1) {
-			throw new IllegalArgumentException("abs(exponent) must be positive");
+		int nFractionalDigits = countSigDigits - decExponent-1;
+		if (nFractionalDigits > 0) {
+			sb.append(decimalDigits.subSequence(0, decExponent+1));
+			sb.append('.');
+			sb.append(decimalDigits.subSequence(decExponent+1, countSigDigits));
+			return;
 		}
-
-		int numberOfLeadingZeros = pAbsExponent-1;
-		int absExponent = pAbsExponent;
-		int maxSigFigs = getNumberOfSignificantFiguresDisplayed(-absExponent);
-
-		boolean roundCausedCarry = performRound(sb, 0, maxSigFigs);
-		int nRemainingSigFigs;
-		if(roundCausedCarry) {
-			absExponent--;
-			numberOfLeadingZeros--;
-			nRemainingSigFigs = 1;
-			sb.setLength(0);
-			sb.append("1");
-		} else {
-			nRemainingSigFigs = countSignifantDigits(sb, 0 + maxSigFigs);
-			sb.setLength(nRemainingSigFigs);
+		sb.append(decimalDigits.subSequence(0, countSigDigits));
+		for (int i=-nFractionalDigits; i>0; i--) {
+			sb.append('0');
 		}
+	}
 
-		int normalLength = 2 + numberOfLeadingZeros + nRemainingSigFigs; // 2 == "0.".length()
-
-		if (needsScientificNotation(normalLength)) {
-			if (sb.length()>1) {
-				sb.insert(1, '.');
-			}
-			sb.append('E');
-			sb.append('-');
-			appendExp(sb, absExponent);
-		} else {
-			sb.insert(0, "0.");
-			for(int i=numberOfLeadingZeros; i>0; i--) {
-				sb.insert(2, '0');
-			}
-		}
+	private static boolean needsScientificNotation(int nDigits) {
+		return nDigits > MAX_TEXT_LEN;
 	}
 
-	private static int countSignifantDigits(StringBuffer sb, int startIx) {
-		int result=startIx;
+	private static int countSignifantDigits(String sb) {
+		int result=sb.length()-1;
 		while(sb.charAt(result) == '0') {
 			result--;
 			if(result < 0) {
@@ -338,68 +248,12 @@ public final class NumberToTextConverter {
 		return result + 1;
 	}
 
-	private static void appendExp(StringBuffer sb, int val) {
+	private static void appendExp(StringBuilder sb, int val) {
 		if(val < 10) {
 			sb.append('0');
 			sb.append((char)('0' + val));
 			return;
 		}
 		sb.append(val);
-
-	}
-
-
-	private static boolean isAllZeros(StringBuffer sb, int startIx, int endIx) {
-		for(int i=startIx; i<=endIx && i<sb.length(); i++) {
-			if(sb.charAt(i) != '0') {
-				return false;
-			}
-		}
-		return true;
-	}
-
-	/**
-	 * @return <code>true</code> if carry (out of the MS digit) occurred
-	 */
-	private static boolean performRound(StringBuffer sb, int firstSigFigIx, int nSigFigs) {
-		int nextDigitIx = firstSigFigIx + nSigFigs;
-		if(nextDigitIx == sb.length()) {
-			return false; // nothing to do - digit to be rounded is at the end of the buffer
-		}
-		if(nextDigitIx > sb.length()) {
-			throw new RuntimeException("Buffer too small to fit all significant digits");
-		}
-		boolean hadCarryOutOfFirstDigit;
-		if(sb.charAt(nextDigitIx) < '5') {
-			// change to digit
-			hadCarryOutOfFirstDigit = false;
-		} else {
-			hadCarryOutOfFirstDigit = roundAndCarry(sb, nextDigitIx);
-		}
-		// clear out the rest of the digits after the rounded digit
-		// (at least the nearby digits)
-		int endIx = Math.min(nextDigitIx + MAX_EXTRA_ZEROS, sb.length());
-		for(int i = nextDigitIx; i<endIx; i++) {
-			sb.setCharAt(i, '0');
-		}
-		return hadCarryOutOfFirstDigit;
-	}
-
-	private static boolean roundAndCarry(StringBuffer sb, int nextDigitIx) {
-
-		int changeDigitIx = nextDigitIx - 1;
-		while(sb.charAt(changeDigitIx) == '9') {
-			sb.setCharAt(changeDigitIx, '0');
-			changeDigitIx--;
-			// All nines, rounded up.  Notify caller
-			if(changeDigitIx < 0) {
-				return true;
-			}
-		}
-		// no more '9's to round up.
-		// Last digit to be changed is still inside sb
-		char prevDigit = sb.charAt(changeDigitIx);
-		sb.setCharAt(changeDigitIx, (char) (prevDigit + 1));
-		return false;
 	}
 }