Mercurial > projects > decimal

comparison src/decimal/bcd.d @ 4:b37c218c1442

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial development of BCD integers
author Paul (paul.d.anderson@comcast.net)
date Thu, 18 Mar 2010 18:10:25 -0700
parents
children c021ed211f89
comparison
equal deleted inserted replaced
3:bfda0b347c07 4:b37c218c1442
1 /**
2 * A D programming language implementation of the
3 * General Decimal Arithmetic Specification,
4 * Version 1.70, (25 March 2009).
5 *
6 * by Paul D. Anderson
7 *
8 * Boost Software License - Version 1.0 - August 17th, 2003
9 *
10 * Permission is hereby granted, free of charge, to any person or organization
11 * obtaining a copy of the software and accompanying documentation covered by
12 * this license (the "Software") to use, reproduce, display, distribute,
13 * execute, and transmit the Software, and to prepare derivative works of the
14 * Software, and to permit third-parties to whom the Software is furnished to
15 * do so, all subject to the following:
16 *
17 * The copyright notices in the Software and this entire statement, including
18 * the above license grant, this restriction and the following disclaimer,
19 * must be included in all copies of the Software, in whole or in part, and
20 * all derivative works of the Software, unless such copies or derivative
21 * works are solely in the form of machine-executable object code generated by
22 * a source language processor.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
25 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
27 * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
28 * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
29 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
30 * DEALINGS IN THE SOFTWARE.
31 **/
32
33 module decimal.bcd;
34
35 import std.conv: ConvError;
36 import std.math;
37 import std.stdio: write, writeln;
38 import std.string: strip;
39
40 alias ubyte Digit;
41
42 public static immutable Bcd ZERO = { digits:[0] };
43 public static immutable Bcd ONE = { digits:[1] };
44 public static immutable Bcd NEG_ONE = { sign:true, digits:[1] };
45
46 public struct Bcd {
47
48 // members
49 private bool sign = false;
50 private Digit[] digits = [ 0 ];
51
52 // constructors
53 public this(const Bcd bcd) {
54 this = bcd;
55 }
56
57 public this(const Bcd bcd, uint numDigits) {
58 this = bcd;
59 setNumDigits(numDigits);
60 }
61
62 public this(const string str) {
63 this = str;
64 }
65
66 public this(const long n) {
67 this = n;
68 }
69
70 public this(const long n, uint numDigits) {
71 this = n;
72 setNumDigits(numDigits);
73 }
74
75 const string toString() {
76 return format(this);
77 }
78
79 const hash_t toHash() {
80 hash_t hash = 0;
81 foreach(Digit digit; digits) {
82 hash += digit;
83 }
84 return hash;
85 }
86
87 // access methods
88 const uint numDigits() {
89 return digits.length;
90 }
91
92 void setNumDigits(uint n) {
93 digits.length = n;
94 }
95
96 const uint firstDigit() {
97 return digits[$-1];
98 }
99
100 const uint lastDigit() {
101 return digits[0];
102 }
103
104 void setDigit(uint n, Digit value) {
105 digits[$-n-1] = value;
106 }
107
108 const int getDigit(int n) {
109 return digits[$-n-1];
110 }
111
112 unittest {
113 write("digits...");
114 Bcd bcd = Bcd(12345678L);
115 assert(bcd.numDigits() == 8);
116 assert(bcd.firstDigit() == 1);
117 assert(bcd.lastDigit() == 8);
118 assert(bcd.getDigit(3) == 4);
119 bcd.setDigit(3, 7);
120 assert(bcd.getDigit(3) == 7);
121 bcd.setNumDigits(10);
122 assert(bcd.numDigits == 10);
123 assert(bcd.firstDigit() == 0);
124 assert(bcd.getDigit(5) == 7);
125 bcd.setNumDigits(5);
126 assert(bcd.getDigit(2) == 6);
127 // writeln("bcd = ", bcd);
128 writeln("passed!");
129 }
130
131 const bool isSigned() {
132 return sign;
133 }
134
135 const bool isZero() {
136 writeln("stripping");
137 Bcd temp = stripLeadingZeros(this);
138 writeln("stripped");
139 writeln("temp = ", temp);
140 if (temp.numDigits > 1) return false;
141 return temp.lastDigit == 0;
142 }
143
144 const bool hasLeadingZeros() {
145 return numDigits > 0 && firstDigit == 0;
146 }
147
148 void opAssign(const Bcd that) {
149 this.sign = that.sign;
150 this.digits.length = that.digits.length;
151 this.digits[] = that.digits[];
152 }
153
154 void opAssign(const string str) {
155 this = parse(str);
156 }
157
158 void opAssign(const long n) {
159 uint m;
160 if (n < 0) {
161 sign = true;
162 m = std.math.abs(n);
163 }
164 else {
165 sign = false;
166 m = n;
167 }
168 Digit[20] dig;
169 int i = 0;
170 do {
171 uint q = m/10;
172 uint r = m%10;
173 dig[i] = cast(Digit) r;
174 m = q;
175 i++;
176 } while (m > 0);
177 digits = dig[0..i].dup;
178 }
179
180
181 // index operator
182 Digit opIndex(uint index) {
183 return this.digits[index];
184 }
185
186 // index assign operator
187 void opIndexAssign(Digit value, uint index) {
188 this.digits[index] = value;
189 }
190
191 /+ int opApply(int delegate (ref Digit) dg) {
192 int result = 0;
193 for (int i = 0; i < numDigits; i++) {
194 result = dg(digits[i]);
195 if (result) break;
196 }
197 return result;
198 }
199
200 int opApply(int delegate (ref Digit) dg) {
201 int result = 0;
202 for (int i = 0; i < numDigits; i++) {
203 result = dg(digits[i]);
204 if (result) break;
205 }
206 return result;
207 }
208
209 int opApplyReverse(int delegate (ref Digit) dg) {
210 int result = 0;
211 for (int i = 0; i < numDigits; i++) {
212 result = dg(digits[i]);
213 if (result) break;
214 }
215 return result;
216 }+/
217
218 const Bcd dup() {
219 Bcd bcd;
220 bcd.sign = this.sign;
221 bcd.digits.length = this.digits.length;
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() {
228 return this.dup;
229 }
230
231 const Bcd opNeg() {
232 return negate(this);
233 }
234
235 const Bcd opCom() {
236 return complement(this);
237 }
238
239 const Bcd opNot() {
240 return not(this);
241 }
242
243 const Bcd opAnd(const Bcd bcd) {
244 return and(this, bcd);
245 }
246
247 const Bcd opOr(const Bcd bcd) {
248 return or(this, bcd);
249 }
250
251 const Bcd opXor(const Bcd bcd) {
252 return xor(this, bcd);
253 }
254
255 // TODO: what's the matter with the one-digit numbers??
256 const bool opEquals(T:Bcd)(const T that) {
257 // writeln("equating");
258 if (this.sign != that.sign) return false; // what about +/- zero?
259 // writeln("same signs");
260 Bcd thisOne = stripLeadingZeros(this);
261 // writeln("this = ", thisOne);
262 Bcd thatOne = stripLeadingZeros(that);
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 }
276 return true;
277 }
278
279 const bool opEquals(T)(const T that) {
280 return opEquals(Bcd(that));
281 }
282
283 } // end struct Bcd
284
285 private bool isDigit(const char ch) {
286 return (ch >= '0' && ch <= '9');
287 }
288
289 public string format(const Bcd bcd, bool showPlus = false, bool showLeadingZeros = false) {
290 int len = bcd.digits.length;
291 if (bcd.sign) len++;
292 char[] str = new char[len];
293
294 int index = 0;
295 if (bcd.sign) {
296 str[index] = '-';
297 index++;
298 }
299
300 foreach_reverse(Digit digit; bcd.digits) {
301 str[index] = cast(char) digit + '0';
302 index++;
303 }
304 return str.idup;
305 }
306
307 public Bcd parse(string str) {
308 Bcd bcd;
309 // are leading zeros retained?
310 bool lz = false;
311
312 // strip whitespace, convert to char array
313 char[] str1 = str.strip.dup;
314
315 // check for leading '-'
316 if (str1[0] == '-') {
317 bcd.sign = true;
318 str1 = str1[1..$];
319 lz = true;
320 }
321
322 // check for leading '+'
323 if (str1[0] == '+') {
324 bcd.sign = false;
325 str1 = str1[1..$];
326 lz = true;
327 }
328
329 // verify chars are digits, strip out underscores
330 int index = 0;
331 char[] str2 = new char[str1.length];
332 foreach_reverse(char ch; str1) {
333 if (isDigit(ch)) {
334 str2[index] = ch;
335 index++;
336 continue;
337 }
338 if (ch == '_') {
339 continue;
340 }
341 throw (new ConvError("Invalid character: " ~ ch));
342 }
343 str2.length = index;
344
345 bcd.digits.length = index;
346 foreach(int i, char ch; str2) {
347 bcd.digits[i] = cast(Digit)(ch - '0');
348 }
349
350 if (!lz) return stripLeadingZeros(bcd);
351 return bcd;
352 }
353
354 public Bcd copy(const Bcd bcd) {
355 return bcd.dup;
356 }
357
358 public Bcd negate(const Bcd bcd) {
359 Bcd copy = bcd; //.dup;
360 copy.sign = !bcd.sign;
361 return copy;
362 }
363
364 public Bcd abs(const Bcd bcd) {
365 return bcd.isSigned ? -bcd: +bcd;
366 }
367
368 public Bcd stripLeadingZeros(const Bcd bcd) {
369 Bcd result = bcd.dup;
370 if (!bcd.hasLeadingZeros) return result;
371 int len = bcd.numDigits;
372 int i = 0;
373 while(i < len-1 && bcd.getDigit(i) == 0) {
374 i++;
375 }
376 result.setNumDigits(len - i);
377 return result;
378 }
379
380
381 unittest {
382 write("strip...");
383 Bcd bcd;
384 bcd = "+00123";
385 assert(bcd.toString == "00123");
386 bcd = stripLeadingZeros(bcd);
387 writeln("bcd = ", bcd);
388 assert(bcd.toString == "123");
389 bcd = "+000";
390 writeln("bcd = ", bcd);
391 assert(bcd.toString == "000");
392 bcd = stripLeadingZeros(bcd);
393 writeln("bcd = ", bcd);
394 writeln("passed");
395 }
396
397 public bool sameLength(const Bcd a, const Bcd b) {
398 return a.numDigits == b.numDigits;
399 }
400
401 public int setSameLength(ref Bcd a, ref Bcd b) {
402 if (sameLength(a,b)) return a.numDigits;
403 uint alen = a.numDigits;
404 uint blen = b.numDigits;
405 if (alen > blen) {
406 b.setNumDigits(alen);
407 }
408 else {
409 a.setNumDigits(blen);
410 }
411 return a.numDigits();
412 }
413
414 public Bcd complement(const Bcd a) {
415 Bcd b = Bcd(0, a.numDigits);
416 foreach(int i, Digit digit; a.digits) {
417 b.digits[i] = digit == 0 ? 1 : 0 ;
418 }
419 return b;
420 }
421
422 unittest {
423 write("com...");
424 Bcd bcd;
425 bcd = 123;
426 assert(complement(bcd).toString == "000");
427 bcd = 40509;
428 assert(complement(bcd).toString == "01010");
429 // writeln("bcd = ", bcd);
430 // writeln("~bcd = ", complement(bcd));
431 writeln("passed");
432 }
433
434 public int sgn(Bcd bcd) {
435 if (bcd.isZero) return 0;
436 return bcd.isSigned ? -1 : 1;
437 }
438
439 public Bcd not(const Bcd x) {
440 Bcd result = x.dup;
441 for (int i = 0; i < x.numDigits; i++) {
442 result[i] = not(result[i]);
443 }
444 return result;
445 }
446
447 private Digit not(const Digit a) {
448 return a != 0;
449 }
450
451 public Bcd and(const Bcd x, const Bcd y) {
452 Bcd a = x.dup;
453 Bcd b = y.dup;
454 int len = setSameLength(a,b);
455 Bcd result = Bcd(0, len);
456 for (int i = 0; i < len; i++) {
457 result[i] = and(a[i], b[i]);
458 }
459 return result;
460 }
461
462 private Digit and(const Digit a, const Digit b) {
463 return a != 0 && b != 0;
464 }
465
466 unittest {
467 write("and...");
468 Bcd a;
469 Bcd b;
470 a = 123000;
471 b = 123000;
472 assert(and(a,b).toString == "111000");
473 b = 12300;
474 assert(and(a,b).toString == "011000");
475 a = 1234567;
476 b = 7654321;
477 assert(and(a,b).toString == "1111111");
478 a = 1010;
479 b = 101;
480 writeln("a = ", a);
481 writeln("b = ", b);
482 writeln("and = ", and(a,b));
483 assert(and(a,b).isZero);
484 writeln("passed!");
485 }
486
487 // TODO: looks like there's some room for templates or mixins here.
488 public Bcd or(const Bcd x, const Bcd y) {
489 Bcd a = x.dup;
490 Bcd b = y.dup;
491 int len = setSameLength(a,b);
492 Bcd result = Bcd(0, len);
493 for (int i = 0; i < len; i++) {
494 result[i] = or(a[i], b[i]);
495 }
496 return result;
497 }
498
499 private Digit or(const Digit a, const Digit b) {
500 return a != 0 || b != 0;
501 }
502
503
504 public Bcd xor(const Bcd x, const Bcd y) {
505 Bcd a = x.dup;
506 Bcd b = y.dup;
507 int len = setSameLength(a,b);
508 Bcd result = Bcd(0, len);
509 for (int i = 0; i < len; i++) {
510 result[i] = xor(a[i], b[i]);
511 }
512 return result;
513 }
514
515 private Digit xor(const Digit a, const Digit b) {
516 return (a == 0 && b != 0) || (a != 0 && b == 0);
517 }
518
519 public Bcd add(const Bcd a, const Bcd b) {
520 Bcd x = a.dup;
521 Bcd y = b.dup;
522 int len = setSameLength(x, y);
523 Bcd result = Bcd(0, len+1);
524 Digit carry = 0;
525 uint i;
526 for (i = 0; i < len; i++) {
527 result[i] = add(x[i], y[i], carry);
528 }
529 if (carry) {
530 result[i] = 1;
531 }
532 else {
533 result = stripLeadingZeros(result);
534 }
535 return result;
536 }
537
538 private Digit add(const Digit a, const Digit b, ref Digit carry) {
539 Digit sum = a + b + carry;
540 if (sum > 9) {
541 sum -= 10;
542 carry = 1;
543 }
544 else {
545 carry = 0;
546 }
547 return sum;
548 }
549
550 unittest {
551 write("add...");
552 Bcd a, b;
553 a = 123;
554 b = 222;
555 Bcd sum = add(a,b);
556 assert(sum == 345);
557 a = 2;
558 b = 102000;
559 sum = add(a,b);
560 assert(sum == 102002);
561 writeln("passed!");
562 }
563
564 //==========================================
565
566 public void main() {
567 writeln("Hello, world");
568 Bcd bcd;
569 writeln("bcd = ", format(bcd));
570 bcd = parse("12");
571 writeln("bcd = ", format(bcd));
572 bcd = parse("012");
573 writeln("bcd = ", format(bcd));
574 bcd = parse("-012");
575 writeln("bcd = ", format(bcd));
576 bcd = parse("+012");
577 writeln("bcd = ", format(bcd));
578 bcd = parse("-0");
579 writeln("bcd = ", format(bcd));
580 bcd = parse("012_345_678");
581 writeln("bcd = ", format(bcd));
582
583 bcd = 1234;
584 writeln("bcd = ", format(bcd));
585 bcd = 12345678L;
586 writeln("bcd = ", format(bcd));
587 writeln("a == b : ", Bcd(0) == Bcd(0));
588 writeln("a == b : ", Bcd(4) == Bcd(4));
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