Mercurial > projects > decimal

comparison src/decimal/bcd.d @ 5:c021ed211f89

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
bcd add, sub, multiply, logic and shift operations
author Paul (paul.d.anderson@comcast.net)
date Sat, 20 Mar 2010 21:38:22 -0700
parents b37c218c1442
children 14badf9104b9
comparison
equal deleted inserted replaced
4:b37c218c1442 5:c021ed211f89
30 * DEALINGS IN THE SOFTWARE. 30 * DEALINGS IN THE SOFTWARE.
31 **/ 31 **/
32 32
33 module decimal.bcd; 33 module decimal.bcd;
34 34
35 import std.algorithm: max;
35 import std.conv: ConvError; 36 import std.conv: ConvError;
36 import std.math; 37 import std.math;
37 import std.stdio: write, writeln; 38 import std.stdio: write, writeln;
38 import std.string: strip; 39 import std.string: strip;
39 40
40 alias ubyte Digit; 41 alias ubyte Digit;
41 42
42 public static immutable Bcd ZERO = { digits:[0] }; 43 public immutable Bcd ZERO = { digits:[0] };
43 public static immutable Bcd ONE = { digits:[1] }; 44 public immutable Bcd ONE = { digits:[1] };
44 public static immutable Bcd NEG_ONE = { sign:true, digits:[1] }; 45 public immutable Bcd NEG_ONE = { sign:true, digits:[1] };
45 46
47 /**
48 * Provides BCD-encoded integral values of arbitrary length.
49 *
50 * Advantages of BCD:
51 * To/from string is easy.
52 * Easy to pull values of individual digits.
53 * Easy to multiply and divide by powers of 10.
54 *
55 * Disadvantages of BCD:
56 * Significantly less compact representation.
57 * Operations are carried out bytewise, requiring more iterations.
58 * Extra steps required for addition.
59 *
60 */
46 public struct Bcd { 61 public struct Bcd {
47 62
48 // members 63 //--------------------------------
64 // members
65 //--------------------------------
66
67 /**
68 * The sign of the BCD integer. Sign is kept explicitly
69 * and not encoded in the number.
70 **/
49 private bool sign = false; 71 private bool sign = false;
72
73 /**
74 * An array of decimal digits in reverse (right-to-left) order
75 * representing an integral value.
76 * Trailing zeros have no effect on the value of the number;
77 * they correspond to leading zeros in a left-to-right representation.
78 **/
50 private Digit[] digits = [ 0 ]; 79 private Digit[] digits = [ 0 ];
51 80
52 // constructors 81 //--------------------------------
82 // construction
83 //--------------------------------
84
85 //--------------------------------
86 // copy construction
87 //--------------------------------
88
89
90 /**
91 * Copy constructor. Returns a (non-const) copy of the argument.
92 */
53 public this(const Bcd bcd) { 93 public this(const Bcd bcd) {
54 this = bcd; 94 sign = bcd.sign;
55 } 95 digits = bcd.digits.dup;
56 96 }
97
98 /**
99 * Copies a BCD integer and adjusts the number of digits,
100 * padding or turncating, if necessary.
101 */
57 public this(const Bcd bcd, uint numDigits) { 102 public this(const Bcd bcd, uint numDigits) {
58 this = bcd; 103 this(bcd);
59 setNumDigits(numDigits); 104 setNumDigits(numDigits);
60 } 105 }
61 106
62 public this(const string str) { 107 //--------------------------------
63 this = str; 108 // construction from integer types.
64 } 109 //--------------------------------
65 110
111 /**
112 * Constructs a BCD integer from a (signed) byte, short, int or long value.
113 */
66 public this(const long n) { 114 public this(const long n) {
67 this = n; 115 ulong m;
116 if (n < 0) {
117 sign = true;
118 m = std.math.abs(n);
119 }
120 else {
121 sign = false;
122 m = n;
123 }
124 Digit[20] dig;
125 int i = 0;
126 do {
127 ulong q = m/10;
128 ulong r = m%10;
129 dig[i] = cast(Digit) r;
130 m = q;
131 i++;
132 } while (m > 0);
133 digits = dig[0..i].dup;
68 } 134 }
69 135
136 /**
137 * Constructs a BCD integer from a (signed) byte, short,
138 * int or long value, and then adjusts the number of digits,
139 * padding or truncating as needed.
140 */
70 public this(const long n, uint numDigits) { 141 public this(const long n, uint numDigits) {
71 this = n; 142 this = n;
72 setNumDigits(numDigits); 143 setNumDigits(numDigits);
73 } 144 }
74 145
75 const string toString() { 146 unittest {
76 return format(this); 147 write("this(long)..");
77 } 148 Bcd p;
78 149 p = -1234;
79 const hash_t toHash() { 150 assert(p == Bcd("-1234"));
80 hash_t hash = 0; 151 p = 12345678L;
81 foreach(Digit digit; digits) { 152 assert(p == Bcd("12345678"));
82 hash += digit; 153 p = Bcd(-19166586400L);
83 } 154 assert(p == Bcd("-19166586400"));
84 return hash; 155 p = Bcd(139676498390L);
85 } 156 assert(p == Bcd("139676498390"));
86 157 writeln("passed");
87 // access methods 158 }
159
160 //--------------------------------
161 // construction from a string.
162 //--------------------------------
163
164 /**
165 * Constructs a BCD integer from a string representation.
166 * If the string has leading zeros they are retained internally.
167 */
168 public this(const string str) {
169 this = parse(str);
170 }
171
172 //--------------------------------
173 // member access functions
174 //--------------------------------
175
176 //--------------------------------
177 // access to the sign of the number
178 //--------------------------------
179
180 const bool isSigned() {
181 return sign;
182 }
183
184 void setSign(bool sign) {
185 this.sign = sign;
186 }
187
188 //--------------------------------
189 // access to the digits
190 //--------------------------------
191
192 /**
193 * Returns the number of digits in this BCD integer.
194 * Includes leading zero digits.
195 */
88 const uint numDigits() { 196 const uint numDigits() {
89 return digits.length; 197 return digits.length;
90 } 198 }
91 199
200 /**
201 * Adjusts the number of digits in this BCD integer,
202 * padding or truncating if necessary.
203 */
92 void setNumDigits(uint n) { 204 void setNumDigits(uint n) {
93 digits.length = n; 205 digits.length = n;
94 } 206 }
95 207
208 /**
209 * Returns the first digit of this BCD integer. If the
210 * integer has leading zeros this function will return
211 * zero, but the value of the number is not necessarily zero.
212 */
96 const uint firstDigit() { 213 const uint firstDigit() {
97 return digits[$-1]; 214 return digits[$-1];
98 } 215 }
99 216
217 /**
218 * Returns the last digit of this BCD integer.
219 */
100 const uint lastDigit() { 220 const uint lastDigit() {
101 return digits[0]; 221 return digits[0];
102 } 222 }
103 223
104 void setDigit(uint n, Digit value) { 224 /**
105 digits[$-n-1] = value; 225 * Returns the specified digit of this BCD integer. The index is
106 } 226 * zero based, i.e., getDigit(0) returns the first digit.
107 227 */
108 const int getDigit(int n) { 228 const int getDigit(int n) {
109 return digits[$-n-1]; 229 return digits[$-n-1];
230 }
231
232 /**
233 * Sets the specified digit of this BCD integer to the specified value.
234 * The index is zero based, i.e., getDigit(0) returns the first digit.
235 */
236 void setDigit(uint n, Digit value) {
237 assert(value < 10);
238 digits[$-n-1] = value;
110 } 239 }
111 240
112 unittest { 241 unittest {
113 write("digits..."); 242 write("digits...");
114 Bcd bcd = Bcd(12345678L); 243 Bcd bcd = Bcd(12345678L);
123 assert(bcd.firstDigit() == 0); 252 assert(bcd.firstDigit() == 0);
124 assert(bcd.getDigit(5) == 7); 253 assert(bcd.getDigit(5) == 7);
125 bcd.setNumDigits(5); 254 bcd.setNumDigits(5);
126 assert(bcd.getDigit(2) == 6); 255 assert(bcd.getDigit(2) == 6);
127 // writeln("bcd = ", bcd); 256 // writeln("bcd = ", bcd);
128 writeln("passed!"); 257 writeln("passed");
129 } 258 }
130 259
131 const bool isSigned() { 260 //--------------------------------
132 return sign; 261 // Common object functions.
133 } 262 //--------------------------------
134 263
264 /**
265 * Returns a string representation of this BCD integer.
266 * Leading zeros are displayed. The sign is displayed if
267 * the number is negative.
268 */
269 const string toString() {
270 return format(this);
271 }
272
273 unittest {
274 write("toString...");
275 writeln("passed");
276 }
277
278 /**
279 * Returns a hash code for this BCD integer.
280 */
281 const hash_t toHash() {
282 hash_t hash = 0;
283 foreach(Digit digit; digits) {
284 hash += digit;
285 }
286 return hash;
287 }
288
289 unittest {
290 write("toHash...");
291 writeln("passed");
292 }
293
294 /**
295 * Returns a mutable copy of this BCD integer.
296 */
297 const Bcd dup() {
298 Bcd bcd;
299 bcd.sign = this.sign;
300 bcd.digits = digits.dup;
301 return bcd;
302 }
303
304 //--------------------------------
305 // Utility functions.
306 //--------------------------------
307
308 /**
309 * Returns true if the internal representation of
310 * this BCD integer has leading zeros.
311 */
312 const bool hasLeadingZeros() {
313 return numDigits > 0 && firstDigit == 0;
314 }
315
316 /**
317 * Returns true if the value of this BCD integer is zero.
318 * Ignores and leading zeros and the sign of the number.
319 */
135 const bool isZero() { 320 const bool isZero() {
136 writeln("stripping");
137 Bcd temp = stripLeadingZeros(this); 321 Bcd temp = stripLeadingZeros(this);
138 writeln("stripped");
139 writeln("temp = ", temp);
140 if (temp.numDigits > 1) return false; 322 if (temp.numDigits > 1) return false;
141 return temp.lastDigit == 0; 323 return temp.lastDigit == 0;
142 } 324 }
143 325
144 const bool hasLeadingZeros() { 326 //--------------------------------
145 return numDigits > 0 && firstDigit == 0; 327 // Assignment operators.
146 } 328 //--------------------------------
147 329
148 void opAssign(const Bcd that) { 330 /**
331 * Assignment operator for BCD integer to BCD integer operations.
332 */
333 Bcd opAssign(const Bcd that) {
149 this.sign = that.sign; 334 this.sign = that.sign;
150 this.digits.length = that.digits.length; 335 this.digits = that.digits.dup;
151 this.digits[] = that.digits[]; 336 return this;
152 } 337 }
153 338
339 /**
340 * Converts the string argument into a BCD integer and assigns it
341 * to this BCD integer.
342 */
154 void opAssign(const string str) { 343 void opAssign(const string str) {
155 this = parse(str); 344 this = Bcd(str);
156 } 345 }
157 346
347 /**
348 * Converts the integer argument into a BCD integer and assigns it
349 * to this BCD integer.
350 */
158 void opAssign(const long n) { 351 void opAssign(const long n) {
159 uint m; 352 this = Bcd(n);
353 /+ uint m;
160 if (n < 0) { 354 if (n < 0) {
161 sign = true; 355 sign = true;
162 m = std.math.abs(n); 356 m = std.math.abs(n);
163 } 357 }
164 else { 358 else {
172 uint r = m%10; 366 uint r = m%10;
173 dig[i] = cast(Digit) r; 367 dig[i] = cast(Digit) r;
174 m = q; 368 m = q;
175 i++; 369 i++;
176 } while (m > 0); 370 } while (m > 0);
177 digits = dig[0..i].dup; 371 digits = dig[0..i].dup;+/
178 } 372 }
179 373
180 374
181 // index operator 375 // index operator
182 Digit opIndex(uint index) { 376 Digit opIndex(uint index) {
212 result = dg(digits[i]); 406 result = dg(digits[i]);
213 if (result) break; 407 if (result) break;
214 } 408 }
215 return result; 409 return result;
216 }+/ 410 }+/
217 411
218 const Bcd dup() { 412 //--------------------------------
219 Bcd bcd; 413 // unary operators
220 bcd.sign = this.sign; 414 //--------------------------------
221 bcd.digits.length = this.digits.length; 415
222 bcd.digits[] = this.digits[];
223 return bcd;
224 }
225
226 // TODO: always uncertain how this is done...will it make an unnecessary copy?
227 const Bcd opPos() { 416 const Bcd opPos() {
228 return this.dup; 417 return this.dup;
229 } 418 }
230 419
231 const Bcd opNeg() { 420 const Bcd opNeg() {
232 return negate(this); 421 Bcd copy = this.dup;
422 copy.sign = !this.sign;
423 return copy;
233 } 424 }
234 425
235 const Bcd opCom() { 426 const Bcd opCom() {
236 return complement(this); 427 return twosComp(this);
237 } 428 }
238 429
239 const Bcd opNot() { 430 const Bcd opNot() {
240 return not(this); 431 return not(this);
241 } 432 }
242 433
243 const Bcd opAnd(const Bcd bcd) { 434 Bcd opPostInc() {
244 return and(this, bcd); 435 return this + ONE;
245 } 436 }
246 437
247 const Bcd opOr(const Bcd bcd) { 438 Bcd opPostDec() {
248 return or(this, bcd); 439 return this - ONE;
249 } 440 }
250 441
251 const Bcd opXor(const Bcd bcd) { 442 //--------------------------------
252 return xor(this, bcd); 443 // binary operators
253 } 444 //--------------------------------
254 445
255 // TODO: what's the matter with the one-digit numbers?? 446 const Bcd opAdd(T:Bcd)(const T addend) {
447 return add(this, addend);
448 }
449
450 const Bcd opAdd(T)(const T addend) {
451 return add(this, Bcd(addend));
452 }
453
454 Bcd opAddAssign(T)(const T addend) {
455 this = this + addend;
456 return this;
457 }
458
459 const Bcd opSub(T:Bcd)(const T addend) {
460 return subtract(this, addend);
461 }
462
463 const Bcd opSub(T)(const T addend) {
464 return subtract(this, Bcd(addend));
465 }
466
467 Bcd opSubAssign(T)(const T addend) {
468 this = this - addend;
469 return this;
470 }
471
472 const Bcd opMul(T:Bcd)(const T b) {
473 return multiply(this, b);
474 }
475
476 const Bcd opMul(T)(const T b) {
477 return multiply(this, Bcd(b));
478 }
479
480 Bcd opMulAssign(T)(const T b) {
481 this = this * b;
482 return this;
483 }
484
485 unittest {
486 write("multiply...");
487 Bcd a, b, c;
488 a = 105, b = -22;
489 c = a * b;
490 assert(c == -2310);
491 c = 45;
492 c *= 1205;
493 // writeln("c = ", c);
494 assert(c == 54225);
495 writeln("passed");
496 }
497
498 const Bcd opAnd(const Bcd a) {
499 return and(this, a);
500 }
501
502 Bcd opAndAssign(const Bcd a) {
503 this = this & a;
504 return this;
505 }
506
507 const Bcd opOr(const Bcd a) {
508 return or(this, a);
509 }
510
511 Bcd opOrAssign(const Bcd a) {
512 this = this | a;
513 return this;
514 }
515
516 const Bcd opXor(const Bcd a) {
517 return xor(this, a);
518 }
519
520 Bcd opXorAssign(const Bcd a) {
521 this = this ^ a;
522 return this;
523 }
524
525 //--------------------------------
526 // comparison, equality operators
527 //--------------------------------
528
529 const int opCmp(T:Bcd)(const T that) {
530 return compare(this, that);
531 }
532
533 unittest {
534 write("compare...");
535 Bcd a,b;
536 a = 100;
537 b = 5;
538 assert(a > b);
539 a = 5;
540 b = 100;
541 assert(a < b);
542 assert(b > a);
543 writeln("passed");
544 }
545
546 const int opCmp(T)(const T that) {
547 return opCmp(Bcd(that));
548 }
549
256 const bool opEquals(T:Bcd)(const T that) { 550 const bool opEquals(T:Bcd)(const T that) {
257 // writeln("equating"); 551 Bcd a = stripLeadingZeros(this);
258 if (this.sign != that.sign) return false; // what about +/- zero? 552 Bcd b = stripLeadingZeros(that);
259 // writeln("same signs"); 553 if (this.sign != that.sign) return false;
260 Bcd thisOne = stripLeadingZeros(this); 554 if (a.digits.length != b.digits.length) return false;
261 // writeln("this = ", thisOne); 555 foreach_reverse(int i, Digit digit; a.digits) {
262 Bcd thatOne = stripLeadingZeros(that); 556 if (digit != b.digits[i]) return false;
263 // writeln("that = ", thatOne);
264 if (thisOne.digits.length != thatOne.digits.length) return false;
265 // writeln("length = ", thisOne.digits.length);
266 // foreach(int i, Digit digit; thisOne) { // todo: have to make opApply here.
267 // }
268 foreach_reverse(int i, Digit digit; thisOne.digits) {
269 /+ writeln("i = ", i);
270 writeln("this[i] = ", thisOne.digits[i]);
271 writeln("that[i] = ", thatOne.digits[i]);
272 writeln("this = ", thisOne.digits);
273 writeln("that = ", thatOne.digits);+/
274 if (digit != thatOne.digits[i]) return false;
275 } 557 }
276 return true; 558 return true;
559 // return compare(this, that) == 0;
277 } 560 }
278 561
279 const bool opEquals(T)(const T that) { 562 const bool opEquals(T)(const T that) {
280 return opEquals(Bcd(that)); 563 return opEquals(Bcd(that));
281 } 564 }
565
566 unittest {
567 write("equals...");
568 assert(Bcd(0) == Bcd(0));
569 assert(Bcd(4) == Bcd(4));
570 assert(Bcd(40) == Bcd(40));
571 assert(Bcd(-400) == Bcd(-400));
572 assert(Bcd(12345678) == Bcd(+12345678));
573 assert(Bcd(40) != Bcd(53));
574 assert(Bcd(402) != Bcd(531));
575 assert(Bcd(402) != Bcd(-402));
576 assert(Bcd(65432) != Bcd(65431));
577 assert(Bcd(2) != Bcd(1));
578 assert(Bcd(1) != Bcd(2));
579 writeln("passed");
580 }
282 581
283 } // end struct Bcd 582 } // end struct Bcd
284 583
285 private bool isDigit(const char ch) { 584 //public string format(const Bcd bcd, bool showPlus = false, bool showLeadingZeros = false) {
286 return (ch >= '0' && ch <= '9'); 585 public string format(const Bcd bcd) {
287 }
288
289 public string format(const Bcd bcd, bool showPlus = false, bool showLeadingZeros = false) {
290 int len = bcd.digits.length; 586 int len = bcd.digits.length;
291 if (bcd.sign) len++; 587 if (bcd.isSigned) len++;
588 // if (bcd.isSigned || bcd.hasLeadingZeros) len++;
292 char[] str = new char[len]; 589 char[] str = new char[len];
293 590
294 int index = 0; 591 int index = 0;
295 if (bcd.sign) { 592 if (bcd.sign) {
296 str[index] = '-'; 593 str[index] = '-';
297 index++; 594 index++;
298 } 595 }
299 596 /+ if (bcd.hasLeadingZeros) {
597 str[index] = '+';
598 index++;
599 }+/
300 foreach_reverse(Digit digit; bcd.digits) { 600 foreach_reverse(Digit digit; bcd.digits) {
301 str[index] = cast(char) digit + '0'; 601 str[index] = cast(char) digit + '0';
302 index++; 602 index++;
303 } 603 }
304 return str.idup; 604 return str.idup;
345 bcd.digits.length = index; 645 bcd.digits.length = index;
346 foreach(int i, char ch; str2) { 646 foreach(int i, char ch; str2) {
347 bcd.digits[i] = cast(Digit)(ch - '0'); 647 bcd.digits[i] = cast(Digit)(ch - '0');
348 } 648 }
349 649
350 if (!lz) return stripLeadingZeros(bcd); 650 if (!lz) return stripLeadingZeros(bcd);
351 return bcd; 651 return bcd;
352 } 652 }
353 653
354 public Bcd copy(const Bcd bcd) { 654 private bool isDigit(const char ch) {
355 return bcd.dup; 655 return (ch >= '0' && ch <= '9');
356 } 656 }
357 657
358 public Bcd negate(const Bcd bcd) { 658 public Bcd negate(const Bcd a) {
359 Bcd copy = bcd; //.dup; 659 return -a;
360 copy.sign = !bcd.sign; 660 }
361 return copy; 661
362 } 662 public Bcd abs(const Bcd a) {
363 663 return a.isSigned ? -a: +a;
364 public Bcd abs(const Bcd bcd) { 664 }
365 return bcd.isSigned ? -bcd: +bcd; 665
366 } 666 public int compare(const Bcd m, const Bcd n) {
367 667 Bcd a = stripLeadingZeros(m);
368 public Bcd stripLeadingZeros(const Bcd bcd) { 668 Bcd b = stripLeadingZeros(n);
369 Bcd result = bcd.dup; 669 if (!a.isSigned && b.isSigned) return 1;
370 if (!bcd.hasLeadingZeros) return result; 670 if (a.isSigned && !b.isSigned) return -1;
371 int len = bcd.numDigits; 671 if (a.digits.length > b.digits.length) return 1;
672 if (a.digits.length < b.digits.length) return -1;
673 foreach_reverse(int i, Digit digit; a.digits) {
674 if (digit > b.digits[i]) return 1;
675 if (digit < b.digits[i]) return -1;
676 }
677 return 0;
678 }
679
680 public Bcd stripLeadingZeros(const Bcd a) {
681 Bcd d = a.dup;
682 if (!a.hasLeadingZeros) return d;
683 int len = a.numDigits;
372 int i = 0; 684 int i = 0;
373 while(i < len-1 && bcd.getDigit(i) == 0) { 685 while(i < len-1 && a.getDigit(i) == 0) {
374 i++; 686 i++;
375 } 687 }
376 result.setNumDigits(len - i); 688 d.setNumDigits(len - i);
377 return result; 689 if (d.numDigits == 1 && d.firstDigit == 0) {
378 } 690 d.sign = false;
379 691 }
692 return d;
693 }
380 694
381 unittest { 695 unittest {
382 write("strip..."); 696 write("strip...");
383 Bcd bcd; 697 Bcd bcd;
384 bcd = "+00123"; 698 bcd = "+00123";
385 assert(bcd.toString == "00123"); 699 assert(bcd.toString == "00123");
386 bcd = stripLeadingZeros(bcd); 700 bcd = stripLeadingZeros(bcd);
387 writeln("bcd = ", bcd); 701 // writeln("bcd = ", bcd);
388 assert(bcd.toString == "123"); 702 assert(bcd.toString == "123");
389 bcd = "+000"; 703 bcd = "+000";
390 writeln("bcd = ", bcd); 704 // writeln("bcd = ", bcd);
391 assert(bcd.toString == "000"); 705 assert(bcd.toString == "000");
392 bcd = stripLeadingZeros(bcd); 706 bcd = stripLeadingZeros(bcd);
393 writeln("bcd = ", bcd); 707 // writeln("bcd = ", bcd);
394 writeln("passed"); 708 writeln("passed");
395 } 709 }
396 710
397 public bool sameLength(const Bcd a, const Bcd b) { 711 public bool sameLength(const Bcd a, const Bcd b) {
398 return a.numDigits == b.numDigits; 712 return a.numDigits == b.numDigits;
399 } 713 }
400 714
401 public int setSameLength(ref Bcd a, ref Bcd b) { 715 public int setSameLength(ref Bcd a, ref Bcd b) {
402 if (sameLength(a,b)) return a.numDigits; 716 if (sameLength(a, b)) return a.numDigits;
403 uint alen = a.numDigits; 717 uint alen = a.numDigits;
404 uint blen = b.numDigits; 718 uint blen = b.numDigits;
405 if (alen > blen) { 719 if (alen > blen) {
406 b.setNumDigits(alen); 720 b.setNumDigits(alen);
407 } 721 }
409 a.setNumDigits(blen); 723 a.setNumDigits(blen);
410 } 724 }
411 return a.numDigits(); 725 return a.numDigits();
412 } 726 }
413 727
414 public Bcd complement(const Bcd a) { 728 public Bcd twosComp(const Bcd a) {
415 Bcd b = Bcd(0, a.numDigits); 729 Bcd b = Bcd(0, a.numDigits);
416 foreach(int i, Digit digit; a.digits) { 730 foreach(int i, Digit digit; a.digits) {
417 b.digits[i] = digit == 0 ? 1 : 0 ; 731 b.digits[i] = digit == 0 ? 1 : 0 ;
418 } 732 }
419 return b; 733 return b;
421 735
422 unittest { 736 unittest {
423 write("com..."); 737 write("com...");
424 Bcd bcd; 738 Bcd bcd;
425 bcd = 123; 739 bcd = 123;
426 assert(complement(bcd).toString == "000"); 740 assert(twosComp(bcd).toString == "000");
427 bcd = 40509; 741 bcd = 40509;
428 assert(complement(bcd).toString == "01010"); 742 assert(twosComp(bcd).toString == "01010");
429 // writeln("bcd = ", bcd); 743 // writeln("bcd = ", bcd);
430 // writeln("~bcd = ", complement(bcd)); 744 // writeln("~bcd = ", twosComp(bcd));
431 writeln("passed"); 745 writeln("passed");
432 } 746 }
433 747
434 public int sgn(Bcd bcd) { 748 public int sgn(const Bcd bcd) {
435 if (bcd.isZero) return 0; 749 if (bcd.isZero) return 0;
436 return bcd.isSigned ? -1 : 1; 750 return bcd.isSigned ? -1 : 1;
437 } 751 }
438 752
439 public Bcd not(const Bcd x) { 753 public Bcd not(const Bcd x) {
440 Bcd result = x.dup; 754 Bcd result = cast(Bcd) x;
441 for (int i = 0; i < x.numDigits; i++) { 755 for (int i = 0; i < x.numDigits; i++) {
442 result[i] = not(result[i]); 756 result[i] = not(result[i]);
443 } 757 }
444 return result; 758 return result;
445 } 759 }
475 a = 1234567; 789 a = 1234567;
476 b = 7654321; 790 b = 7654321;
477 assert(and(a,b).toString == "1111111"); 791 assert(and(a,b).toString == "1111111");
478 a = 1010; 792 a = 1010;
479 b = 101; 793 b = 101;
480 writeln("a = ", a); 794 // writeln("a = ", a);
481 writeln("b = ", b); 795 // writeln("b = ", b);
482 writeln("and = ", and(a,b)); 796 // writeln("and = ", and(a,b));
483 assert(and(a,b).isZero); 797 assert(and(a,b).isZero);
484 writeln("passed!"); 798 writeln("passed");
485 } 799 }
486 800
487 // TODO: looks like there's some room for templates or mixins here. 801 // TODO: looks like there's some room for templates or mixins here.
488 public Bcd or(const Bcd x, const Bcd y) { 802 public Bcd or(const Bcd x, const Bcd y) {
489 Bcd a = x.dup; 803 Bcd a = x.dup;
498 812
499 private Digit or(const Digit a, const Digit b) { 813 private Digit or(const Digit a, const Digit b) {
500 return a != 0 || b != 0; 814 return a != 0 || b != 0;
501 } 815 }
502 816
503
504 public Bcd xor(const Bcd x, const Bcd y) { 817 public Bcd xor(const Bcd x, const Bcd y) {
505 Bcd a = x.dup; 818 Bcd a = x.dup;
506 Bcd b = y.dup; 819 Bcd b = y.dup;
507 int len = setSameLength(a,b); 820 int len = setSameLength(a,b);
508 Bcd result = Bcd(0, len); 821 Bcd result = Bcd(0, len);
514 827
515 private Digit xor(const Digit a, const Digit b) { 828 private Digit xor(const Digit a, const Digit b) {
516 return (a == 0 && b != 0) || (a != 0 && b == 0); 829 return (a == 0 && b != 0) || (a != 0 && b == 0);
517 } 830 }
518 831
519 public Bcd add(const Bcd a, const Bcd b) { 832 public Bcd add(const Bcd x, const Bcd y) {
833 Bcd a = x.dup;
834 Bcd b = y.dup;
835 Bcd sum;
836 if (a.sign == b.sign) {
837 sum = simpleAdd(a, b);
838 sum = stripLeadingZeros(sum);
839 sum.sign = a.sign;
840 return sum;
841 }
842 else { // signs differ
843 bool sign;
844 switch (compare(abs(a), abs(b))) {
845 case 0:
846 return ZERO.dup;
847 case 1:
848 sign = a.isSigned;
849 break;
850 case -1:
851 sign = b.isSigned;
852 break;
853 }
854 setSameLength(a, b);
855 sum = simpleAdd(a, tensComp(b));
856 if (sum.firstDigit == 1) {
857 sum.digits = sum.digits[0..$-1];
858 }
859 else {
860 sum = tensComp(sum);
861 sum = stripLeadingZeros(sum);
862 }
863 sum.sign = sign;
864 }
865 return sum;
866 }
867
868 unittest {
869 write("add....");
870 Bcd a, b;
871 a = 1234;
872 b = 4321;
873 assert(a + b == 5555);
874 a = 2000;
875 b = 1;
876 assert(a + b == 2001);
877 a = -2000;
878 b = -1;
879 assert(a + b == -2001);
880 a = 2000;
881 b = -1;
882 assert(a + b == 1999);
883 a = -123;
884 b = 1;
885 assert(a + b == -122);
886 a = 123;
887 b = -1;
888 assert(a + b == 122);
889 a = -1;
890 b = 123;
891 // writeln();
892 // writeln("a + b = ", a + b);
893 assert(a + b == 122);
894 a = -123;
895 b = 1;
896 assert(a + b == -122);
897 a = 1;
898 b = -123;
899 assert(a + b == -122);
900 writeln("passed");
901 }
902
903 Bcd subtract(const Bcd a, const Bcd b) {
904 return add(a, negate(b));
905 }
906
907 /**
908 * Adds two BCD integers without regard to sign
909 **/
910 private Bcd simpleAdd(const Bcd a, const Bcd b) {
520 Bcd x = a.dup; 911 Bcd x = a.dup;
521 Bcd y = b.dup; 912 Bcd y = b.dup;
522 int len = setSameLength(x, y); 913 int len = setSameLength(x, y);
523 Bcd result = Bcd(0, len+1); 914 Bcd sum = Bcd(0, len+1);
524 Digit carry = 0; 915 Digit carry = 0;
525 uint i; 916 uint i;
917 // TODO: this is the place to stop adding zeros and
918 // just copy the rest of the digits.
526 for (i = 0; i < len; i++) { 919 for (i = 0; i < len; i++) {
527 result[i] = add(x[i], y[i], carry); 920 sum[i] = add(x[i], y[i], carry);
528 } 921 }
529 if (carry) { 922 if (carry) {
530 result[i] = 1; 923 sum[i] = 1;
531 } 924 }
532 else { 925 else {
533 result = stripLeadingZeros(result); 926 sum = stripLeadingZeros(sum);
534 } 927 }
535 return result; 928 return sum;
536 } 929 }
537 930
931 /**
932 * Adds two digits and a carry digit.
933 * Returns the (single-digit) sum and sets or resets the carry digit.
934 **/
538 private Digit add(const Digit a, const Digit b, ref Digit carry) { 935 private Digit add(const Digit a, const Digit b, ref Digit carry) {
539 Digit sum = a + b + carry; 936 Digit sum = a + b + carry;
540 if (sum > 9) { 937 carry = sum > 9;
541 sum -= 10; 938 if (carry) sum -= 10;
542 carry = 1;
543 }
544 else {
545 carry = 0;
546 }
547 return sum; 939 return sum;
548 } 940 }
549 941
550 unittest { 942 unittest {
551 write("add..."); 943 write("simpleAdd...");
552 Bcd a, b; 944 Bcd a, b;
553 a = 123; 945 a = 123;
554 b = 222; 946 b = 222;
555 Bcd sum = add(a,b); 947 Bcd sum = simpleAdd(a,b);
556 assert(sum == 345); 948 assert(sum == 345);
557 a = 2; 949 a = 2;
558 b = 102000; 950 b = 102000;
559 sum = add(a,b); 951 sum = simpleAdd(a,b);
560 assert(sum == 102002); 952 assert(sum == 102002);
561 writeln("passed!"); 953 writeln("passed");
954 }
955
956 private Bcd tensComp(const Bcd a) {
957 /+ foreach(Digit digit; a.digits) {
958 digit = 9 - digit;
959 }
960 a = simpleAdd(a, ONE);
961 return a;+/
962
963 Bcd x = Bcd(0, a.numDigits);
964 foreach (int i, digit; a.digits) {
965 x[i] = 9 - digit;
966 }
967 return simpleAdd(x, ONE);
968 }
969
970 unittest {
971 write("tensComp...");
972 Bcd a, b, c;
973 a = 123456;
974 b = tensComp(a);
975 // writeln("a = ", a);
976 // writeln("b = ", b);
977 c = 876544;
978 assert(b == c);
979 a = Bcd(0, 4);
980 b = tensComp(a);
981 c = 10000;
982 assert(b == c);
983 a = Bcd(1, 4);
984 b = tensComp(a);
985 c = 9999;
986 assert(b == c);
987 a = 9999;
988 b = tensComp(a);
989 c = 1;
990 assert(b == c);
991 a = 10000;
992 b = tensComp(a);
993 c = 90000;
994 assert(b == c);
995 a = 1;
996 b = tensComp(a);
997 c = 9;
998 // writeln("a = ", a);
999 // writeln("b = ", b);
1000 assert(b == c);
1001 writeln("passed");
1002 }
1003
1004 // TODO: there are lots of ways to speed this up.
1005 public Bcd multiply(const Bcd a, const Bcd b) {
1006 Bcd n, m;
1007 Bcd p = Bcd(0, a.numDigits + b.numDigits);
1008 if (a.numDigits > b.numDigits) {
1009 n = stripLeadingZeros(a);
1010 m = stripLeadingZeros(b);
1011 }
1012 else {
1013 n = stripLeadingZeros(b);
1014 m = stripLeadingZeros(a);
1015 }
1016 foreach(uint i, Digit d; m.digits) {
1017 if (d == 0) continue;
1018 // writeln("mul(n, m[i]) = ", mul(n, m[i]));
1019 // writeln("pow10(mul(n, m[i]), i) = ", pow10(mul(n, m[i]), i));
1020 p = simpleAdd(p, pow10(mul(n, m[i]), i));
1021 }
1022 p.sign = a.sign ^ b.sign;
1023 return p;
1024 }
1025
1026 unittest {
1027 write("mul...");
1028 Bcd a, b, p;
1029 a = 2105, b = 301;
1030 p = multiply(a, b);
1031 assert(p == Bcd(633605));
1032 b = 800, a = 23958233;
1033 p = multiply(a, b);
1034 assert(p == Bcd("19166586400"));
1035 b = 5830, a = 23958233;
1036 p = multiply(a, b);
1037 assert(p == Bcd("139676498390"));
1038 writeln("passed");
1039 }
1040
1041 private Bcd mul(const Bcd a, Digit m) {
1042 Bcd p = Bcd(0, a.numDigits+1);
1043 Digit c = 0;
1044 int i = 0;
1045 foreach (Digit d; a.digits) {
1046 p[i] = mul(m, d, c);
1047 i++;
1048 }
1049 if (c) p[i] = c;
1050 return p;
1051 }
1052
1053 unittest {
1054 write("mul...");
1055 Bcd a, p;
1056 Digit m;
1057 a = 2105, m = 3;
1058 p = mul(a, m);
1059 assert(p == Bcd(6315));
1060 writeln("passed");
1061 }
1062
1063 private Digit mul(Digit a, Digit b, ref Digit c) {
1064 Digit p = a * b + c;
1065 c = p / 10;
1066 return p % 10;
1067 }
1068
1069 unittest {
1070 write("mul...");
1071 Digit a, b, c, d;
1072 a = 2, b = 3, c = 0;
1073 d = mul(a,b,c);
1074 assert(d == 6);
1075 assert(c == 0);
1076 a = 9, b = 8, c = 0;
1077 d = mul(a,b,c);
1078 assert(d == 2);
1079 assert(c == 7);
1080 writeln("passed");
1081 }
1082
1083 public Bcd pow10(const Bcd a, uint n) {
1084 Bcd b = a.dup;
1085 if (n == 0) return b;
1086 Digit[] zeros = new Digit[n];
1087 b.digits = zeros ~ b.digits;
1088 return b;
1089 }
1090
1091 public Bcd pow10(uint n) {
1092 return pow10(ONE, n);
1093 }
1094
1095 unittest {
1096 write("pow10...");
1097 Bcd a, b;
1098 a = 21345;
1099 a = pow10(a, 12);
1100 assert(a == Bcd("21345000000000000"));
1101 a = pow10(a, 0);
1102 assert(a == "21345000000000000");
1103 a = pow10(9);
1104 assert(a == Bcd("1000000000"));
1105 writeln("passed");
1106 }
1107
1108 public Bcd shift(const Bcd a, int n) {
1109 if (n == 0) return a.dup;
1110 Bcd b = Bcd(0, a.numDigits);
1111 if (std.math.abs(n) >= a.numDigits) return b;
1112 if (n > 0) { // shift left
1113 b.digits[0..$-n] = a.digits[n..$];
1114 }
1115 else { // shift right
1116 n = -n;
1117 b.digits[n..$] = a.digits[0..$-n];
1118 }
1119 return b;
1120 }
1121
1122 unittest {
1123 write("shift...");
1124 Bcd a, b;
1125 a = 1234;
1126 b = shift(a, 1);
1127 assert(b.toString == "0123");
1128 b = shift(a, 2);
1129 assert(b.toString == "0012");
1130 b = shift(a, -1);
1131 assert(b.toString == "2340");
1132 b = shift(a, 0);
1133 assert(b.toString == "1234");
1134 b = shift(a, 12);
1135 assert(b.toString == "0000");
1136 b = shift(a, -4);
1137 assert(b.toString == "0000");
1138 writeln("passed");
1139 }
1140
1141 public Bcd rotate(const Bcd a, int n) {
1142 if (n == 0) return a.dup;
1143 Bcd b = Bcd(0, a.numDigits);
1144 if (std.math.abs(n) >= a.numDigits) {
1145 bool sign = n < 0;
1146 n = std.math.abs(n) % a.numDigits;
1147 if (sign) n = -n;
1148 }
1149 if (n > 0) { // rotate left
1150 b.digits[0..$-n] = a.digits[n..$];
1151 b.digits[$-n..$] = a.digits[0..n];
1152 }
1153 else { // rotate right
1154 n = -n;
1155 b.digits[n..$] = a.digits[0..$-n];
1156 b.digits[0..n] = a.digits[$-n..$];
1157 }
1158 return b;
1159 }
1160
1161 unittest {
1162 write("rotate...");
1163 Bcd a, b;
1164 a = 1234;
1165 b = rotate(a, 1);
1166 assert(b.toString == "4123");
1167 b = rotate(a, 2);
1168 assert(b.toString == "3412");
1169 b = rotate(a, -1);
1170 assert(b.toString == "2341");
1171 b = rotate(a, 0);
1172 assert(b.toString == "1234");
1173 b = rotate(a, 12);
1174 assert(b.toString == "1234");
1175 b = rotate(a, -4);
1176 assert(b.toString == "1234");
1177 writeln("passed");
562 } 1178 }
563 1179
564 //========================================== 1180 //==========================================
565 1181
566 public void main() { 1182 public void main() {
567 writeln("Hello, world"); 1183 writeln();
1184 writeln("If you got this far all the unit tests were successful.");
1185 writeln();
1186 writeln(" Congratulations!");
568 Bcd bcd; 1187 Bcd bcd;
569 writeln("bcd = ", format(bcd)); 1188 writeln("bcd = ", format(bcd));
570 bcd = parse("12"); 1189 bcd = parse("12");
571 writeln("bcd = ", format(bcd)); 1190 writeln("bcd = ", format(bcd));
572 bcd = parse("012"); 1191 bcd = parse("012");
578 bcd = parse("-0"); 1197 bcd = parse("-0");
579 writeln("bcd = ", format(bcd)); 1198 writeln("bcd = ", format(bcd));
580 bcd = parse("012_345_678"); 1199 bcd = parse("012_345_678");
581 writeln("bcd = ", format(bcd)); 1200 writeln("bcd = ", format(bcd));
582 1201
583 bcd = 1234; 1202 /+
584 writeln("bcd = ", format(bcd)); 1203 writeln("OK!");+/
585 bcd = 12345678L; 1204 }
586 writeln("bcd = ", format(bcd)); 1205
587 writeln("a == b : ", Bcd(0) == Bcd(0)); 1206
588 writeln("a == b : ", Bcd(4) == Bcd(4)); 1207
589 writeln("a == b : ", Bcd(40) == Bcd(40));
590 writeln("a == b : ", Bcd(-400) == Bcd(-400));
591 writeln("a == b : ", Bcd(12345678) == Bcd(+12345678));
592 writeln("a != b : ", Bcd(40) == Bcd(53));
593 writeln("a != b : ", Bcd(402) == Bcd(531));
594 writeln("a != b : ", Bcd(402) == Bcd(-402));
595 writeln("a != b : ", Bcd(65432) == Bcd(65431));
596 writeln("a != b : ", Bcd(2) == Bcd(1));
597 writeln("a != b : ", Bcd(1) == Bcd(2));
598 writeln("OK!");
599 }
600
601
602