/* ***** BEGIN LICENSE BLOCK ***** * Version: MPL 1.1/GPL 2.0/LGPL 2.1 * * The contents of this file are subject to the Mozilla Public License Version * 1.1 (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.mozilla.org/MPL/ * * Software distributed under the License is distributed on an "AS IS" basis, * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License * for the specific language governing rights and limitations under the * License. * * The Original Code is BigDecimal D library. * * The Initial Developer of the Original Code is * Alexander J. Vincent . * Portions created by the Initial Developer are Copyright (C) 2004 * the Initial Developer. All Rights Reserved. * * Contributor(s): * * Alternatively, the contents of this file may be used under the terms of * either the GNU General Public License Version 2 or later (the "GPL"), or * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), * in which case the provisions of the GPL or the LGPL are applicable instead * of those above. If you wish to allow use of your version of this file only * under the terms of either the GPL or the LGPL, and not to allow others to * use your version of this file under the terms of the MPL, indicate your * decision by deleting the provisions above and replace them with the notice * and other provisions required by the GPL or the LGPL. If you do not delete * the provisions above, a recipient may use your version of this file under * the terms of any one of the MPL, the GPL or the LGPL. * * ***** END LICENSE BLOCK ***** */ /* Ported from Alex Vincent's BigDecimal JavaScript library * see http://abacus.mozdev.org for details */ /* Essentially, each BigDecimal object you create is really an array * of digits, each of which is stored as a long type or a cent type. * BigDecimal uses a few simple algorithms to correctly implement the * rules of arithmetic between members of the digit array. * * You can use BigDecimal objects like you would any other numerical * type. Or, if you need fine-grained control, (most probably in * division operations), you can directly call methods of the * BigDecimal object to produce specific results. The following are * all equivalent: * * x += 3; * x = x + 3; * x = x.add(3); * uint rv = x.add(3, BigDecimal y); assert(rv == NS_OK); x = y; * * The last one may seem a bit strange, but it relates to the idea that actual * return values should be saved for error codes. Mozilla XPCOM uses this * extensively, and so these methods are provided for future compatibility as * potential XPCOM components. The actual operations are implemented in these * XPCOM-compatible (?) methods, and all other overloaded methods call them, * asserting for the return error code being NS_OK. * * Do NOT run this code in a production environment with debug code compiled in! * Debug code constrains each digit section to a maximum of four digits. The * purpose of this is to assist the unit test code in brute-force checking of the * BigDecimal library. Under normal operations, each digit section runs with 18 * digits (38 if you set cent instead of long for BigDecimalSection). You will * waste a tremendous amount of memory actively using this library with debug code * enabled. */ /* Still to do: * Implement division and modulus operations. * Support for floating-point types, especially NaN, Infinity and -Infinity. * Support for scientific-notation numbers submitted as strings. * Fix regular-expression detection of NaN at beginning of this(char[] i). * Replace opEquals reference to compareTo with a much simpler algorithm. * Throw InvalidException, not AssertionError, in opCmp(BigDecimal BigN). * Add casting for converting BigDecimal to types other than char[]. * Convert this class into a D module. * Inspect this code very carefully for uses of long-type variables while * iterating through digitArray. uint types would be much better. * Re-examine the use of Mozilla XPCOM error codes as return values. * Strengthen the robustness of the code by adding more in & out contracts. * Give identifiers to all debug{} code within this library. * Find a way to specifically exclude debug code from this library while a * developer using this code can enable their own debug code. * Overload all methods and the constructor to accept long- and ulong-type * arguments simultaneously. * Document this code better. */ import std.stdio; import std.string; import std.conv; import std.regexp; import std.math; import std.intrinsic; /* borrowed from Mozilla Application Suite XPCOM source code, * under mozilla/xpcom/base/nsError.h */ const ulong NS_OK = 0; const ulong NS_ERROR_NOT_YET_IMPLEMENTED = 0x80004001L; class BigDecimal { private bit isNaN; private bit isNegative; private uint decPtAfter; // This controls how many digits we store in each section. // When cent becomes available, change this to cent. alias long BigDecimalSection; private BigDecimalSection[] digitArray; // This code determines the constraints on the digitArray members' values. private ulong section_max_value; private ubyte section_digits; private bit section_info_set; /* Constructors: * this() sets a blank BigDecimal, equal to zero except for isNaN property set. * this(ulong n) sets a BigDecimal equal to n. * this(long n) sets a BigDecimal equal to n. * this(char[] n) sets a BigDecimal with NaN set if n is not a number, else it * returns a BigDecimal equal to n. * * EVERY CONSTRUCTOR MUST CALL setSectionInfo() FIRST! */ this() { setSectionInfo(); } this(long i) { this(std.string.toString(i)); } this(char[] i) { uint errorCode; this(i, errorCode); assert(errorCode == 0); } this(char[] i, out uint errorCode) { setSectionInfo(); // determine if the value passed us is really a number RegExp re = new RegExp("[0-9]*(.[0-9])?", ""); isNaN = !(re.test(i)); if (isNaN) { debug { writef("isNaN\n"); } errorCode = NS_OK; return; } // set isNegative bit isNegative = (std.string.toString(i[0]) == "-"); debug { if (isNegative) { writef("isNegative\n"); } } int decPtIn_I = std.string.find(i, "."); if (decPtIn_I == -1) { decPtIn_I = i.length; } // determine whole number portion and decimal portion char[] wholeNum = i[isNegative..decPtIn_I]; char[] decimals = ""; if (decPtIn_I < i.length) { decimals = i[(decPtIn_I + 1)..i.length]; } while ((wholeNum.length > 1)&&(std.string.toString(wholeNum[0]) == "0")) { wholeNum = wholeNum[1..wholeNum.length]; } if (wholeNum == "") { wholeNum = "0"; } debug { writef("wholeNum:" ~ wholeNum ~ "\n"); } while ((decimals.length > 0) && (std.string.toString(decimals[decimals.length - 1]) == "0")) { decimals.length = decimals.length - 1; } debug { writef("decimals:" ~ decimals ~ "\n"); } // determine where the decimal point goes, and initially set digitArray.length real index = std.math.ceil((wholeNum.length - 1) / section_digits); decPtAfter = rndtol(index); digitArray.length = decPtAfter + 1; debug { writef("decPtAfter: " ~ std.string.toString(decPtAfter) ~ "\n"); } // retrieve whole-number portion int section_index = decPtAfter; uint section_end = wholeNum.length; int section_start; if (section_end > 0) { do { section_start = section_end - section_digits; if (section_start < 0) { section_start = 0; } char[] section = wholeNum[section_start..section_end]; digitArray[section_index] = std.conv.toLong(section); section_index--; section_end -= section_digits; } while (section_index >= 0) } debug { writef("whole numbers parsed\n"); } // retrieve decimal-number portion section_start = 0; while (section_start < decimals.length) { digitArray.length = digitArray.length + 1; section_end = section_start + section_digits; while (section_end > decimals.length) { decimals ~= "0"; } digitArray[digitArray.length - 1] = std.conv.toLong(decimals[section_start..section_end]); section_start = section_end; } debug { writef("decimal numbers parsed\n"); } // -0 == 0 if (isZero()) { isNegative = false; } debug { for (section_index = 0; section_index < digitArray.length; section_index++) { writef("Section " ~ std.string.toString(section_index) ~ ": "); writef(std.string.toString(digitArray[section_index]) ~ "\n"); } writef("End of constructor\n\n"); } errorCode = NS_OK; } this(BigDecimal BigN) { setSectionInfo(); isNaN = BigN.isNaN; isNegative = BigN.isNegative; decPtAfter = BigN.decPtAfter; digitArray = BigN.digitArray.dup; } // This method must be called by all constructors! private void setSectionInfo() { /* This method sets some very serious constraints on what ranges of values * each member of digitArray may have. */ real section_log = std.math.log10(digitArray[0].max); section_log = std.math.floor(section_log); if (section_log % 2 == 1) { section_log--; } debug { // Force much tighter constraints for debugging section_log = 4; } section_max_value = std.math.rndtol(std.math.pow(10, section_log) - 1); section_digits = std.math.rndtol(section_log); section_info_set = true; } /* void addToSection(inout int sectionIndex, in long addValue) * Adds addValue to digitArray[sectionIndex], and performs * carry operations throughout digitArray. If necessary, * flips the isNegative bit. For example, when performing * (a - b) where a < b. * */ private void addToSection(inout long sectionIndex, in BigDecimalSection addValue) in { assert(sectionIndex >= 0); } out { assert(digitArray[sectionIndex] >= 0); assert(digitArray[sectionIndex] <= section_max_value); } body { debug { BigDecimalSection originalAddValue = addValue * 1; writef("in: addToSection(" ~ std.string.toString(sectionIndex) ~ ", "); writef(std.string.toString(originalAddValue) ~ ")\n"); writef("this: " ~ toDebugString() ~ "\n"); } if (sectionIndex >= digitArray.length) { digitArray.length = sectionIndex + 1; } // overflow is a value we pass on to the section "left" of this one. BigDecimalSection overflow = addValue / (section_max_value + 1); addValue -= overflow * (section_max_value + 1); if (addValue < 0) { addValue += (section_max_value + 1); overflow -= 1; } BigDecimalSection margin = section_max_value - digitArray[sectionIndex]; debug { writef("margin: " ~ std.string.toString(margin) ~ "\n"); writef("addValue: " ~ std.string.toString(addValue) ~ "\n"); } if (margin < addValue) { overflow++; digitArray[sectionIndex] = addValue - margin - 1; } else { digitArray[sectionIndex] += addValue; } if (overflow != 0) { debug { writef("overflow == " ~ std.string.toString(overflow) ~ "\n"); writef("this: " ~ toDebugString() ~ "\n"); } if (sectionIndex != 0) { sectionIndex--; addToSection(sectionIndex, overflow); sectionIndex++; } else { if (overflow < 0) { // flip our sign overflow = -overflow - 1; isNegative ^= true; if (margin < addValue) { digitArray[sectionIndex]; } for (uint i = 0; i < digitArray.length; i++) { digitArray[i] = section_max_value - digitArray[i]; } digitArray[digitArray.length - 1]++; debug { writef("isNegative flipped\n"); writef("this: " ~ toDebugString() ~ "\n"); } } // give us room for the overflow BigDecimalSection temp[]; temp.length = 1; temp[0] = 0; digitArray = temp ~ digitArray; decPtAfter++; addToSection(sectionIndex, overflow); sectionIndex++; // ensure sectionIndex still points to its intended section } } // Compensate for when we've accidentally causes a section to be section_max_value + 1 BigDecimalSection subOverflow; for (long i = digitArray.length - 1; i >= 0; i--) { subOverflow = digitArray[i] / (section_max_value + 1); digitArray[i] = digitArray[i] % (section_max_value + 1); if (subOverflow != 0) { i--; addToSection(i, subOverflow); i++; } } // end of addToSection debug { writef("current value: " ~ toDebugString() ~ "\n"); writef("out: addToSection(" ~ std.string.toString(sectionIndex) ~ ", "); writef(std.string.toString(originalAddValue) ~ ")\n"); } } /* bit isZero() returns retval. * int isZero(out retval) returns error code (0 for ok). * * Possible retval values: * true: this number is equal to zero. * false: this number is not equal to zero. */ public bit isZero() { bit retval; uint rv = isZero(retval); assert(rv == NS_OK); return retval; } public uint isZero(out bit retval) { retval = false; if (isNaN) { return NS_OK; } if (digitArray.length != 1) { return NS_OK; } // last check will determine if we have sufficient proof to say "yes" if (digitArray[0] == 0) { retval = true; } return NS_OK; } /* byte compareTo(n) returns retval. * int compareTo(n, out byte retval) returns error code (0 for ok) * * Possible retval values: * -1: this < n * 0: this == n * 1: this > n * 2: ((this == NaN)||(n == NaN)) * */ public byte compareTo(in long n) { BigDecimal Big_n = new BigDecimal(n); byte retval; uint rv = compareTo(Big_n, retval); assert(rv == NS_OK); return retval; } public uint compareTo(in long n, out byte retval) { BigDecimal Big_n = new BigDecimal(n); uint rv = compareTo(Big_n, retval); assert(rv == NS_OK); return retval; } public byte compareTo(in BigDecimal BigN) { byte retval; uint rv = compareTo(BigN, retval); assert(rv == NS_OK); return retval; } public uint compareTo(in BigDecimal BigN, out byte retval) { debug { char[] str = "this: " ~ toString() ~ "\n"; str ~= "BigN: " ~ BigN.toString() ~ "\n"; writef(str); } // NaN checks first! if ((isNaN)||(BigN.isNaN)) { retval = 2; return NS_OK; } retval = 0; // initial conditions bit this_isZero = isZero(); bit BigN_isZero = BigN.isZero(); // sign- and zero-based conditions bit tests[]; tests.length = 2; tests[0] = ((this_isZero)&&(BigN_isZero)); if (tests[0]) { return NS_OK; // 0 == 0, always } tests[0] = ((isNegative)&&(!BigN.isNegative)); // -3 < 3 tests[0] = ((tests[0])||((isNegative)&&(BigN_isZero))); // -3 < 0 tests[0] = ((tests[0])||((this_isZero)&&(!BigN.isNegative))); // 0 < 3 tests[1] = ((!isNegative)&&(BigN.isNegative)); // 3 > -3 tests[1] = ((tests[1])||((!isNegative)&&(BigN_isZero))); // 3 > 0 tests[1] = ((tests[1])||((this_isZero)&&(BigN.isNegative))); // 0 > -3 if (tests[0]) { retval = -1; return NS_OK; } if (tests[1]) { retval = 1; return NS_OK; } bit invertSign = false; if ((isNegative)&&(BigN.isNegative)) { invertSign = true; // (3 < 4) -> (-3 > -4) } // decimal point conditions if (decPtAfter < BigN.decPtAfter) { retval = -1; // 3.000 < 3,000.000 } if (decPtAfter > BigN.decPtAfter) { retval = 1; // 3,000.000 > 3.000 } if (retval != 0) { if (invertSign) { retval *= -1; } return NS_OK; } // Okay, the decimal point for both values are in equal locations within digitArray. // Check section by section. uint minLength; if (digitArray.length < BigN.digitArray.length) { minLength = digitArray.length; } else { minLength = BigN.digitArray.length; } for (uint index = 0; index < minLength; index++) { debug { writef("Comparing " ~ std.string.toString(digitArray[index])); writef(" to " ~ std.string.toString(BigN.digitArray[index]) ~ "\n"); } if (digitArray[index] < BigN.digitArray[index]) { retval = -1; break; } if (digitArray[index] > BigN.digitArray[index]) { retval = 1; break; } } if (retval == 0) { // we still have not proven an inequality if (digitArray.length < BigN.digitArray.length) { retval = -1; // 3.14 < 3.14159 } if (digitArray.length > BigN.digitArray.length) { retval = 1; // 3.14159 > 3.14 } } // if (retval == 0), then this == BigN. // there should be no doubt any longer if (invertSign) { retval *= -1; } return NS_OK; } /* private void assign(BigDecimal BigN) assumes the properties of BigN. * * If we could overload the assignment operator, this would be the intended * call. But the D Language specification explicitly disallows overloading * the assignment operator. */ private void assign(BigDecimal BigN) { isNaN = BigN.isNaN; isNegative = BigN.isNegative; decPtAfter = BigN.decPtAfter; digitArray = BigN.digitArray; } /* public BigDecimal add(n) returns retval. * public uint add(in n, out BigDecimal retval) returns error code (0 for ok). * retval = this + n */ public BigDecimal add(long n) { BigDecimal retval; uint rv = add(n, retval); assert(rv == NS_OK); return retval; } public uint add(in long n, out BigDecimal retval) { BigDecimal BigN = new BigDecimal(n); return add(BigN, retval); } public BigDecimal add(BigDecimal BigN) { BigDecimal retval; uint rv = add(BigN, retval); assert(rv == NS_OK); return retval; } public uint add(in BigDecimal BigN, out BigDecimal retval) { // NaN checks first! if ((isNaN)||(BigN.isNaN)) { retval.isNaN = true; return NS_OK; } byte invert = (isNegative == BigN.isNegative) * 2 - 1; retval = new BigDecimal(this); debug { writef("add called\n"); writef("this: " ~ toDebugString() ~ "\n"); writef("BigN: " ~ BigN.toDebugString() ~ "\n"); writef("retval: " ~ retval.toDebugString() ~ "\n"); } // Make sure we have enough zero sections at start if (retval.decPtAfter < BigN.decPtAfter) { BigDecimalSection[] temp; temp.length = (BigN.decPtAfter - retval.decPtAfter); retval.digitArray = temp ~ retval.digitArray; retval.decPtAfter = BigN.decPtAfter * 1; } /* I chose to use long here because decPtAfter is always uint, and we can get negative * values here which are smaller than 0. */ long offset = retval.decPtAfter - BigN.decPtAfter; long decimals = BigN.digitArray.length - BigN.decPtAfter; // make sure we have enough decimals at end if (retval.digitArray.length < decimals + retval.decPtAfter) { retval.digitArray.length = decimals + retval.decPtAfter; } /* When doing 1 + (-3), the result is -2. This means, among other things, that * the sign has flipped. We want to watch for that, and if it happens, flip the * invert sign as well. We also want to ensure the sign flips no more than once. */ bit wasNegative = (retval.isNegative) ? true : false; bit hasSignFlipped = false; debug { writef("add initial conditions: \n"); writef("invert: " ~ std.string.toString(invert) ~ "\n"); writef("retval: " ~ retval.toDebugString() ~ "\n"); writef("BigN: " ~ BigN.toDebugString() ~ "\n"); writef("offset: " ~ std.string.toString(offset) ~ "\n"); } // Begin adding sequence for (long k = BigN.digitArray.length - 1; k >= 0; k--) { // need an actual value because addToSection's first argument is an inout uint. // also, adjust offset as necessary if we have a carrying operation long kOffset = k + offset; debug { writef("Before addSection\n"); writef("k: " ~ std.string.toString(k) ~ "\n"); writef("offset: " ~ std.string.toString(offset) ~ "\n"); writef("kOffset: " ~ std.string.toString(kOffset) ~ "\n"); writef("BigN: " ~ BigN.toDebugString() ~ "\n"); writef("retval: " ~ retval.toDebugString() ~ "\n"); } retval.addToSection(kOffset, BigN.digitArray[k] * invert); // assume kOffset has changed, and reset offset offset = retval.decPtAfter - BigN.decPtAfter; debug { writef("\nAfter addSection\n"); writef("k: " ~ std.string.toString(k) ~ "\n"); writef("offset: " ~ std.string.toString(offset) ~ "\n"); writef("kOffset: " ~ std.string.toString(kOffset) ~ "\n"); writef("retval: " ~ retval.toDebugString() ~ "\n\n"); } // did retval suddenly flip its isNegative bit? if (retval.isNegative != wasNegative) { debug { writef("retval.isNegative != wasNegative\n"); writef("retval.isNegative: " ~ std.string.toString(retval.isNegative) ~ "\n"); writef("wasNegative: " ~ std.string.toString(wasNegative) ~ "\n"); } // Yes. Flip the invert value. assert(!hasSignFlipped); invert *= -1; wasNegative = (retval.isNegative) ? true : false; debug { writef("wasNegative is now: " ~ std.string.toString(wasNegative) ~ "\n"); } hasSignFlipped = true; } } // clean up leading zero sections long k = 0; while ((retval.digitArray[k] == 0)&&(k < retval.decPtAfter)) { k++; } retval.digitArray = retval.digitArray[k..(retval.digitArray.length)]; retval.decPtAfter -= k; debug { writef("Final retval: " ~ retval.toString() ~ "\n"); } return NS_OK; } /* public BigDecimal subtract(n) returns retval. * public uint subtract(n, BigDecimal retval) returns error code (0 for ok). * retval = this - n */ public BigDecimal subtract(long n) { BigDecimal BigN = new BigDecimal(-n); return add(BigN); } public uint subtract(long n, out BigDecimal retval) { BigDecimal BigN = new BigDecimal(-n); return add(BigN, retval); } public BigDecimal subtract(BigDecimal BigN) { return add(-BigN); } public uint subtract(in BigDecimal BigN, out BigDecimal retval) { return add(-BigN, retval); } /* public BigDecimal multiply(n) returns retval. * public uint multiply(n, BigDecimal retval) returns error code (0 for ok). * retval = this * n */ public BigDecimal multiply(long n) { BigDecimal retval; uint rv = multiply(n, retval); assert(rv == NS_OK); return retval; } public uint multiply(long n, out BigDecimal retval) { BigDecimal BigN = new BigDecimal(n); return multiply(BigN, retval); } public BigDecimal multiply(BigDecimal BigN) { BigDecimal retval; uint rv = multiply(BigN, retval); assert(rv == NS_OK); return retval; } public uint multiply(in BigDecimal BigN, out BigDecimal retval) { // set up initial conditions retval = new BigDecimal(); retval.isNegative = (isNegative != BigN.isNegative); retval.decPtAfter = decPtAfter + BigN.decPtAfter; long digitOffset = (digitArray.length - decPtAfter) + (BigN.digitArray.length - BigN.decPtAfter); retval.digitArray.length = retval.decPtAfter + digitOffset - 1; debug { writef("retval: " ~ retval.toDebugString() ~ "\n"); } for (long i = digitArray.length - 1; i >= 0; i--) { for (long BigN_i = BigN.digitArray.length - 1; BigN_i >= 0; BigN_i--) { digitOffset = (i - decPtAfter) + (BigN_i - BigN.decPtAfter); /* Alas, we cannot just multiply the two sections together and pass the value to * addSection. The product of two long values can very easily be larger than the * maximum value a long will accept. * * (ax + b) * (cx + d) == ax^2 + (ad + bc)x + (bd). * Assume x == 10 ^ (section_digits / 2). * * This means with a given section p = (ax + b), * a == p / x, and b = p % x when a and b are defined as integral types. * * Also, the x^2 bit is equal to 10 ^ section_digits, which is equal to * section_max_value + 1. So we simply shift the value of a * c into * the next leftmost section and avoid the overflow problem there. */ debug { writef("Starting calculations...\n"); } real halfDigits = section_digits / 2; BigDecimalSection x = std.math.rndtol(std.math.pow(10, halfDigits)); BigDecimalSection a = digitArray[i] / x; BigDecimalSection b = digitArray[i] % x; BigDecimalSection c = BigN.digitArray[BigN_i] / x; BigDecimalSection d = BigN.digitArray[BigN_i] % x; long sectionIndex = retval.decPtAfter + digitOffset - 1; if (sectionIndex == -1) { debug { writef("sectionIndex == -1\n"); writef("retval before shift: " ~ retval.toDebugString() ~ "\n"); } BigDecimalSection[] temp; temp.length = 1; temp[0] = 0; retval.digitArray = temp ~ retval.digitArray; retval.decPtAfter++; debug { writef("retval after shift: " ~ retval.toDebugString() ~ "\n"); } sectionIndex++; } debug { writef("a: " ~ std.string.toString(a) ~ "\n"); writef("b: " ~ std.string.toString(b) ~ "\n"); writef("c: " ~ std.string.toString(c) ~ "\n"); writef("d: " ~ std.string.toString(d) ~ "\n"); writef("sectionIndex: " ~ std.string.toString(sectionIndex) ~ "\n"); } debug { writef("in: retval.addToSection(sectionIndex, a * c);\n"); writef("sectionIndex: " ~ std.string.toString(sectionIndex) ~ "\n"); writef("retval: " ~ retval.toDebugString() ~ "\n"); } retval.addToSection(sectionIndex, a * c); debug { writef("out: retval.addToSection(sectionIndex, a * c);\n"); } sectionIndex++; debug { writef("in: retval.addToSection(sectionIndex, a * d * x);\n"); writef("sectionIndex: " ~ std.string.toString(sectionIndex) ~ "\n"); writef("retval: " ~ retval.toDebugString() ~ "\n"); } retval.addToSection(sectionIndex, a * d * x); debug { writef("out: retval.addToSection(sectionIndex, a * d * x);\n"); writef("in: retval.addToSection(sectionIndex, b * c * x);\n"); writef("sectionIndex: " ~ std.string.toString(sectionIndex) ~ "\n"); writef("retval: " ~ retval.toDebugString() ~ "\n"); } retval.addToSection(sectionIndex, b * c * x); debug { writef("out: retval.addToSection(sectionIndex, b * c * x);\n"); writef("in: retval.addToSection(sectionIndex, b * d);\n"); writef("sectionIndex: " ~ std.string.toString(sectionIndex) ~ "\n"); writef("retval: " ~ retval.toDebugString() ~ "\n"); } retval.addToSection(sectionIndex, b * d); debug { writef("out: retval.addToSection(sectionIndex, b * d);\n"); } } } debug { writef("Finished doing calculations\n"); } // clean up leading zero sections long k = 0; while ((retval.digitArray[k] == 0)&&(k < retval.decPtAfter)) { k++; } if (k != 0) { retval.digitArray = retval.digitArray.dup[k..(retval.digitArray.length)]; retval.decPtAfter -= k; } debug { writef("Final retval: " ~ retval.toDebugString() ~ "\n"); } return NS_OK; } /* bit opEquals(long n); * bit opEquals(BigDecimal BigN); * * returns true if this == n */ bit opEquals(long n) { BigDecimal BigN = new BigDecimal(n); return opEquals(BigN); } bit opEquals(BigDecimal BigN) { byte response = compareTo(BigN); return (response == 0); } /* byte opCmp(long n); * byte opCmp(BigDecimal BigN); * * Throws an exception if this is NaN or BigN is NaN. * Otherwise, returns compareTo(BigN). */ byte opCmp(long n) { BigDecimal BigN = new BigDecimal(n); return opCmp(BigN); } byte opCmp(BigDecimal BigN) { byte retval = compareTo(BigN); assert(retval != 2); // we really should throw an InvalidException instead here return retval; } /* BigDecimal opNeg() * returns -this */ BigDecimal opNeg() { BigDecimal retval = new BigDecimal(this); retval.isNegative ^= true; return retval; } /* BigDecimal opPos() * returns new(this) */ BigDecimal opPos() { BigDecimal retval = new BigDecimal(this); return retval; } /* opPostInc() calls opAddAssign(1) */ void opPostInc() { opAddAssign(1); } /* opPostDec() calls opSubAssign(1) */ void opPostDec() { opSubAssign(1); } /* opAddAssign(n) changes this to this + n * */ void opAddAssign(long n) { BigDecimal BigN = new BigDecimal(n); opAddAssign(BigN); } void opAddAssign(BigDecimal BigN) { BigDecimal retval; uint rv = add(BigN, retval); assert(rv == NS_OK); assign(BigN); } /* opSubAssign(n) changes this to this - n * */ void opSubAssign(long n) { BigDecimal BigN = new BigDecimal(-n); opAddAssign(BigN); } void opSubAssign(BigDecimal BigN) { BigDecimal retval; uint rv = add(-BigN, retval); assert(rv == NS_OK); assign(BigN); } /* opMulAssign(n) changes this to this * n * */ void opMulAssign(long n) { BigDecimal BigN = new BigDecimal(n); opMulAssign(BigN); } void opMulAssign(BigDecimal BigN) { BigDecimal retval; uint rv = multiply(BigN, retval); assert(rv == NS_OK); assign(BigN); } /* char[] opCast() returns toString(). * integral types opCast() checks toString() to see if it can convert. * floating types opCast() checks toString() to see if it can convert. */ char[] opCast() { return toString(); } /* BigDecimal opAdd(n) returns this.add(n). */ BigDecimal opAdd(long n) { BigDecimal BigN = new BigDecimal(n); return opAdd(BigN); } BigDecimal opAdd(BigDecimal BigN) { BigDecimal retval; uint rv = add(BigN, retval); assert(rv == NS_OK); return retval; } /* BigDecimal opSub(n) returns this.add(-n). */ BigDecimal opSub(long n) { BigDecimal BigN = new BigDecimal(-n); return opAdd(BigN); } BigDecimal opSub(BigDecimal BigN) { return opAdd(-BigN); } /* BigDecimal opMul(n) returns this.add(n). */ BigDecimal opMul(long n) { BigDecimal BigN = new BigDecimal(n); return opMul(BigN); } BigDecimal opMul(BigDecimal BigN) { BigDecimal retval; uint rv = multiply(BigN, retval); assert(rv == NS_OK); return retval; } /* char[] toString() returns string value of this. * int toString(out char[] response) returns error code (0 if ok). */ public char[] toString() { char[] response; uint rv = toString(response); assert(rv == NS_OK); return response; } public uint toString(out char[] response) { if (isNaN) { response = "NaN"; return NS_OK; } if (isZero()) { response = "0"; return NS_OK; } response = ""; // include minus sign if (isNegative) { response = "-"; } bit decimalNotAtEnd = false; // add digits for (uint i = 0; i < digitArray.length; i++) { char[] section = std.string.toString(digitArray[i]); // insert prevailing zeros if (i <> 0) { while (section.length < section_digits) { section = "0" ~ section; } } response ~= section; if ((i == decPtAfter)&&(i != digitArray.length - 1)) { response ~= "."; decimalNotAtEnd = true; } } // clean up trailing zeros if (decimalNotAtEnd) { while (std.string.toString(response[response.length - 1]) == "0") { response.length = response.length - 1; } // remove the decimal point if it's the last character if (std.string.toString(response[response.length - 1]) == ".") { response.length = response.length - 1; } } return NS_OK; } debug { private char[] toDebugString() { if (isNaN) { return "NaN"; } char[] response; if (isNegative) { response = "-["; } else { response = "+["; } for (ulong i = 0; i < digitArray.length; i++) { response ~= std.string.toString(digitArray[i]); if (i == decPtAfter) { response ~= "."; } if (i < digitArray.length - 1) { response ~= " "; } } response ~= "]"; return response; } } invariant { /* If this assert fails, then something is really crazy. * Given digitArray is an array of ulong types (18 digits * per section), and decPtAfter is of type int (2147483648 * sections), this means a total of 38,654,705,664 digits * are not enough for our user! * * By the way, this works out to a maximum number of bytes * actually within the digitArray's contents of 8,589,934,592. * Unless you have 8 gigabytes of RAM to use in your * calculations, it's fairly unlikely you'll ever hit this limit! */ assert(digitArray.length <= decPtAfter.max); } unittest { writef("Executing unittest\n"); BigDecimal test; char[] testStr; test = new BigDecimal("123456789123456789"); /* digitSectionLength is used to determine which sets of unit tests we actually run. * Some unit tests (such as tests on what toString() returns) are unconditionally run. * * A value of 4 means we're in debug mode, and we will do special integrity checks on * all operations. * * A value of 18 means digitArray is a long[]. So run assertions programmed to 18 digits. * * A value of 38 means digitArray is a cent[]. So run assertions programmed to 38 digits. */ ubyte digitSectionLength = test.section_digits; switch (digitSectionLength) { case 4: case 18: break; case 38: assert(false); // we haven't written unit tests for cent[] yet! default: assert(false); // We got an unexpected number of digits per section! } testStr = test.toString(); writef(testStr ~ "\n"); switch (digitSectionLength) { case 4: assert(test.digitArray.length == 5); break; case 18: assert(test.digitArray.length == 1); } assert(testStr == "123456789123456789"); test = new BigDecimal(".123456789123456789"); testStr = test.toString(); writef(testStr ~ "\n"); switch(digitSectionLength) { case 4: assert(test.digitArray.length == 6); break; case 18: assert(test.digitArray.length == 2); } assert(testStr == "0.123456789123456789"); test = new BigDecimal(".000123456123456789000123456123456789"); testStr = test.toString(); writef(testStr ~ "\n"); switch(digitSectionLength) { case 4: assert(test.digitArray.length == 10); break; case 18: assert(test.digitArray.length == 3); } assert(testStr == "0.000123456123456789000123456123456789"); test = new BigDecimal( "-123456789123456789000111222333444555.123456789123456789000111222333444555"); testStr = test.toString(); writef(testStr ~ "\n"); assert(test.isNegative); switch(digitSectionLength) { case 4: assert(test.digitArray.length == 18); assert(test.decPtAfter == 8); assert(test.digitArray[0] == 1234); assert(test.digitArray[1] == 5678); assert(test.digitArray[2] == 9123); assert(test.digitArray[3] == 4567); assert(test.digitArray[4] == 8900); assert(test.digitArray[5] == 111); assert(test.digitArray[6] == 2223); assert(test.digitArray[7] == 3344); assert(test.digitArray[8] == 4555); assert(test.digitArray[0+9] == 1234); assert(test.digitArray[1+9] == 5678); assert(test.digitArray[2+9] == 9123); assert(test.digitArray[3+9] == 4567); assert(test.digitArray[4+9] == 8900); assert(test.digitArray[5+9] == 111); assert(test.digitArray[6+9] == 2223); assert(test.digitArray[7+9] == 3344); assert(test.digitArray[8+9] == 4555); break; case 18: assert(test.digitArray.length == 4); assert(test.decPtAfter == 1); assert(test.digitArray[0] == 123456789123456789); assert(test.digitArray[1] == 111222333444555); assert(test.digitArray[2] == 123456789123456789); assert(test.digitArray[3] == 111222333444555); } assert(testStr == "-123456789123456789000111222333444555.123456789123456789000111222333444555"); test = new BigDecimal("-000000.000000000000000000"); testStr = test.toString(); writef(testStr ~ "\n"); assert(testStr == "0"); assert(test.digitArray.length == 1); assert(test.decPtAfter == 0); assert(!test.isNegative); assert(test.isZero()); /* test = new BigDecimal("x"); assert(test.isNaN); assert(test.toString() == "NaN"); */ test = new BigDecimal(4); assert(!test.isZero()); BigDecimal test2 = new BigDecimal(test); test.isNegative == true; assert(!test2.isNegative); test.isNegative = false; test.digitArray[0] = 5; assert(test2.digitArray[0] == 4); byte compare; int rv = test2.compareTo(test, compare); assert(rv == NS_OK); writef("Expect -1, received: " ~ std.string.toString(compare) ~ "\n"); assert(compare == -1); compare = test2.compareTo(test2); writef("Expect 0, received: " ~ std.string.toString(compare) ~ "\n"); assert(compare == 0); compare = test.compareTo(test2); writef("Expect 1, received: " ~ std.string.toString(compare) ~ "\n"); assert(compare == 1); assert(test2 == test2); assert(test != test2); assert(test > test2); assert(test >= test2); assert(test <> test2); assert(test2 < test); assert(test2 <= test); assert(test2 <> test); assert(test <>= test2); assert(test2 <>= test); if (digitSectionLength == 4) { /* Here, we run special tests to ensure addition, subtraction, multiplication, * division, and modulus operations act correctly. Because the results from these * operations are highly sensitive to the number of digits requested (particularly * multiplication and division), these tests compare the results of operations * involving long and real values against what BigDecimal will generate for numbers * of equal digits. Essentially, we use BigDecimal under extreme, debug-only * constraints to check its performance against what the program would do without * BigDecimal implemented. * * If these tests pass, then we know BigDecimal can be scaled up to 18 digits per * section with long[] for digitArray, or 38 digits per section with cent[] for * digitArray. */ void debugTests(in long a, in long b) { char[] testStr; long c; BigDecimal BigA = new BigDecimal(a); BigDecimal BigB = new BigDecimal(b); BigDecimal BigC; writef("Running + test\n"); writef("a = " ~ std.string.toString(a) ~ ", "); writef("b = " ~ std.string.toString(b) ~ "\n"); c = a + b; BigC = BigA + BigB; testStr = BigC.toString(); writef("+: " ~ testStr ~ "\n"); writef("=: " ~ std.string.toString(c) ~ "\n"); assert(testStr == std.string.toString(c)); writef("\n"); writef("Running - test\n"); writef("a = " ~ std.string.toString(a) ~ ", "); writef("b = " ~ std.string.toString(b) ~ "\n"); c = a - b; BigC = BigA - BigB; testStr = BigC.toString(); writef("-: " ~ testStr ~ "\n"); writef("=: " ~ std.string.toString(c) ~ "\n"); assert(testStr == std.string.toString(c)); writef("\n"); writef("Running * test\n"); writef("a = " ~ std.string.toString(a) ~ ", "); writef("b = " ~ std.string.toString(b) ~ "\n"); c = a * b; BigC = BigA * BigB; testStr = BigC.toString(); writef("*: " ~ testStr ~ "\n"); writef("=: " ~ std.string.toString(c) ~ "\n"); assert(testStr == std.string.toString(c)); writef("\n"); /* NS_ERROR_NOT_YET_IMPLEMENTED writef("Running / test\n"); writef("a = " ~ std.string.toString(a) ~ ", "); writef("b = " ~ std.string.toString(b) ~ "\n"); real d = a / b; BigC = BigA / BigB; testStr = BigC.toString(); writef("/: " ~ testStr ~ "\n"); writef("=: " ~ std.string.toString(d) ~ "\n"); assert(testStr == std.string.toString(d)); writef("\n"); writef("Running % test\n"); writef("a = " ~ std.string.toString(a) ~ ", "); writef("b = " ~ std.string.toString(b) ~ "\n"); c = a % b; BigC = BigA % BigB; testStr = BigC.toString(); writef("%: " ~ testStr ~ "\n"); writef("=: " ~ std.string.toString(c) ~ "\n"); assert(testStr == std.string.toString(c)); writef("\n"); */ writef("passed debugTests, "); writef("a = " ~ std.string.toString(a) ~ ", "); writef("b = " ~ std.string.toString(b) ~ "\n"); } const long tenTo9th = 1000000000; const long[6] testSet = [-1, 0, 1, tenTo9th / 2 - 1, tenTo9th / 2, tenTo9th - 1]; for (byte a = 0; a < testSet.length; a++) { test = new BigDecimal(testSet[a]); assert(test == testSet[a]); for (byte b = 0; b < testSet.length; b++) { debugTests(testSet[a], testSet[b]); } } } writef("Finishing unittest\n\n"); } } int main(char[][] args) { BigDecimal k = new BigDecimal(args[1]); char[] kStr; assert(k.toString(kStr) == 0); writef(kStr ~ "\n"); return NS_OK; }