|
Home
Problem Archive Grades Tools Music |
Large Number LibraryThe goal of this library is to produce all the utility routines necessary to work with arbitrarily large numbers.
Large Number Library Source Code
1 // 2 // LargeNumber library 3 // 4 // authors: Isaac Traxler & students 5 // 6 // This is a project started back in 2000 that was not finished 7 // and forgotten. It has now been resurrected. 8 // 9 // The goal of this project is to produce a usable c source library 10 // for large number arithmetic. 11 // 12 // Students in my Psychology of Programming class in 2000 contributed. 13 // Since I have largely restructured it, individual names have been 14 // removed from the individual routines. So here are the names of the 15 // original contributing students: 16 // - Paul Miller 17 // - Wojciech Stryjewski 18 // - Phil Bordelon 19 // - John Walker 20 // - Erin Valentine 21 // - Jay Ponville 22 // - Jamie Ahmad 23 // - Helen 24 // 25 // Contributed to revamped version: 26 // - Josh Abadie 27 // 28 #include <ctype.h> 29 // 30 // Make sure that LN_MAX_DIGITS is large enough to handle worst case. 31 // Be aware that as many as 5 LN instances might exist in a routine. 32 // Be aware that excessively large values will result in CPU consumption 33 // in certain situations (like division of repeating decimals). 34 // 35 #define LN_MAX_DIGITS 1000 36 37 typedef struct LARGE_NUMBER_STRUCT 38 { 39 unsigned short int array[LN_MAX_DIGITS]; // might consider unsigned char here 40 // to reduce storage by 50% 41 signed short int sign; 42 signed long int exponent; 43 signed short int digitCount; 44 } 45 LARGE_NUMBER_STRUCT; 46 // 47 // ASSUMPTIONS: 48 // 1) That no value sent to the library will exceed bounds 49 // a) Exponent will fit into a signed long at ALL times 50 // b) Significant digit count will not exceed LN_MAX_DIGITS 51 // 52 // 2) LN instances are ALWAYS normalized when passed into a routine 53 // 54 // 3) Adding or subtracting two 501 digit numbers can exceed 1000 digits 55 // 56 // 4) No bounds checking is done against LN_MAX_DIGITS 57 // 58 // 5) Normalization does the following: 59 // a) Adjusts exponent, adjusts digitCount, and removes leading zeroes 60 // b) Adjusts digitCount and removes trailing zeroes 61 // c) Leaves number so that a decimal point is implied before the first digit 62 // 63 // 64 // ******************************************************************************** 65 // rules: 66 // - all routines return 0 if everything is okay, a different positive number 67 // for each different error 68 // - Any result passed back (except from LNshift) is normalized 69 // - LNadd adds any two numbers with same sign (calls subtract if signs differ) 70 // - LNsubtract subtracts any two numbers with same sign (calls add if signs differ) 71 // 72 // a = 1 73 // b = -1 74 // add(a,b,c) ==> subtract(a,(-b),c) 75 // subtract(a,b,c) ==> add(a,(-b),c) 76 // 77 // - 0 ALWAYS has a + sign and an exponent of 0 78 // 79 // 80 81 void LNprint(LARGE_NUMBER_STRUCT *n) 82 // simple routine to print large number 83 { // BEGIN function LNprint -- (200302) 84 char str[LN_MAX_DIGITS+25]; 85 86 LNarr2strExp(n, str); 87 printf("[%s]\n", str); 88 } // END function LNprint -- (200302) 89 90 int LNnegate(LARGE_NUMBER_STRUCT *ln1) 91 // changes sign of ln1 92 { // BEGIN function LNnegate -- (200302) 93 if (0 != ln1->digitCount) 94 ln1->sign *= -1; 95 return 0; 96 } // END function LNnegate -- (200302) 97 98 int LNcompare(LARGE_NUMBER_STRUCT *ln1, LARGE_NUMBER_STRUCT *ln2) 99 // compares to see if a<b (-1), a=b (0), a>b (1); assumes both numbers 100 // are normalized (have first digit non-zero and no trailing zeros) 101 { // BEGIN function LNcompare -- (200303) 102 int toReturn = 0; 103 104 // XOR the two, if same 0 (false) results, if different -2 (true) 105 if (ln1->sign ^ ln2->sign) // signs are same, result is 0 106 { // have different signs 107 toReturn = (0 > ln1->sign) ? -1 : 1; 108 } // have different signs 109 else 110 { // have same sign 111 if (ln1->exponent != ln2->exponent) 112 { // exponents not equal, return 1 (1st one) or -1 (2nd one) to show larger 113 toReturn = (ln1->exponent > ln2->exponent) ? 1 : -1; 114 } // exponents not equal, return 1 (1st one) or -1 (2nd one) to show larger 115 else 116 { // numbers have same exponent 117 int i, t; 118 119 t = (ln1->digitCount > ln2->digitCount) ? ln2->digitCount : ln1->digitCount; 120 for (i=0; (i<t) && (0 == toReturn) ; i++) 121 { // for - compare each digit 122 if (ln1->array[i] != ln2->array[i]) 123 toReturn = (ln1->array[i] > ln2->array[i]) ? ln1->sign : - ln2->sign; 124 } // for - compare each digit 125 // digits identical, but one number has extra digits, so number with extra digits 126 // is bigger if positive, smaller if negative. 127 if ((0 == toReturn) && (ln1->digitCount != ln2->digitCount)) 128 toReturn = (ln1->digitCount > ln2->digitCount) ? ln1->sign : - ln2->sign; 129 } // numbers have same exponent 130 } // have same sign 131 return toReturn; 132 } // END function LNcompare -- (200303) 133 134 int LNstr2arr(char str[], LARGE_NUMBER_STRUCT *ln) 135 // convert from string into LN data structure 136 // assume no invalid characters in string (but skip over leading and trailing blanks) 137 // 138 // State diagram: 139 // 140 // state | val | whitespace | - | + | . | digit | Ee | end of string` 141 // ------+-----+------------+------+------+------+-------+------+-------------- 142 // start | 1 | start | num1 | num1 | dec1 | num2 | err | 0 143 // num1 | 2 | err | err | err | dec1 | num2 | err | err 144 // num2 | 3 | normalize | err | err | dec2 | num2 | exp1 | normalize 145 // dec1 | 4 | err | err | err | err | dec2 | err | err 146 // dec2 | 5 | normalize | err | err | err | dec2 | exp1 | normalize 147 // exp1 | 6 | err | exp2 | exp2 | err | exp3 | err | err 148 // exp2 | 7 | err | err | err | err | exp3 | err | err 149 // exp3 | 8 | normalize | err | err | err | exp3 | err | normalize 150 { // BEGIN function LNstr2arr -- (200302) 151 #define START 1 152 #define NUM1 2 153 #define NUM2 3 154 #define DEC1 4 155 #define DEC2 5 156 #define EXP1 6 157 #define EXP2 7 158 #define EXP3 8 159 // 160 // status - (succes/failure) flag (init to SUCCESS) 161 // done - are we done yet? (init to NO) 162 // dpflag - decimal point flag - Have we encountered one yet? (init to NO) 163 // numflag - number flag - Have we encountered any NON-ZERO digits yet? (init to NO) 164 // n - counter/subscript for large number (init to start) 165 // ch - point to main string 166 // These next two need not be used if their values are stored directly into large number. 167 // sign 168 // exp 169 // 170 int state = START, done = 0, n = 0; 171 signed short int dpflag = 0, numflag = 0, sign = 1; 172 signed long int exp; 173 char *ch = str; 174 175 // skip leading blanks and leading zeroes (start < > start) 176 while ( (isspace(*ch)) || ('0' == *ch) ) ch++; 177 178 if (0 != *ch) // is it end of string? 179 { // not empty string 180 // do we have a sign (must be first char) 181 if ('-' == *ch) 182 { // negative - state is NUM1 183 sign = -1; 184 ch++; 185 } // negative - state is NUM1 186 else 187 // Check for plus sign: Not really necessary...(these 4 lines may 188 // be omitted) if numbers are not going to have unary pluses 189 if (*ch == '+') 190 { // positive (the default) - state is NUM1 191 ch++; 192 } // positive (the default) - state is NUM1 193 194 // now get digits until the decimal point or exponent 195 while (isdigit(*ch)) 196 { // process digits -- into state NUM2 197 state = NUM2; 198 ln->array[n++] = *ch - '0'; 199 ch++; // move to next char in string 200 } // process digits -- into state NUM2 201 exp = n; 202 203 if ('.' == *ch) 204 { // decimal point 205 // set state to DEC1 if no digits, DEC2 if digits already 206 state = (NUM2 != state) ? DEC1 : DEC2; 207 ch++; 208 209 // now get digits after the decimal point 210 if (isdigit(*ch)) state = DEC2; 211 while (isdigit(*ch)) 212 { // process digits -- into state NUM2 213 ln->array[n++] = *ch - '0'; 214 ch++; // move to next char in string 215 } // process digits -- into state NUM2 216 } // decimal point 217 218 // only things left are Ee (exponent), whitespace and end of string 219 if (('E' == *ch) || ('e' == *ch)) 220 { // okay we have an exponent 221 signed long int texp; 222 223 state = EXP2; 224 ch++; 225 sscanf(ch, "%d", &texp); 226 exp += texp; 227 } // okay we have an exponent 228 } // not empty string 229 230 if ((EXP2 == state) || (DEC2 == state) || (NUM2 == state)) 231 { // normalize number 232 ln->sign = sign; 233 ln->exponent = exp; 234 ln->digitCount = n; 235 state = 0; 236 } // normalize number 237 return state; 238 } // END function LNstr2arr -- (200302) 239 240 int LNicnvrt(long int number, LARGE_NUMBER_STRUCT *n) 241 // convert a long int to Large Number 242 { // BEGIN function LNicnvrt -- (200302) 243 int idx, digit, j; 244 245 // do sign 246 n->sign = (number < 0) ? -1 : 1; 247 248 // set mantissa and exponent 249 n->exponent = 0; 250 idx = LN_MAX_DIGITS; 251 while (number > 0) 252 { // while 253 digit = number % 10; 254 n->array[--idx] = digit; 255 number /= 10; 256 } // while 257 n->exponent = LN_MAX_DIGITS - idx; 258 n->digitCount = n->exponent; 259 for (j=0; LN_MAX_DIGITS > (j + idx); j++) 260 { // for 261 n->array[j] = n->array[idx+j]; 262 } // for 263 return 0; 264 } // END function LNicnvrt -- (200302) 265 266 int LNarr2strExp(LARGE_NUMBER_STRUCT *ln, char str[]) 267 // convert the ln struct to a string in scientific notation 268 { // BEGIN function LNarr2strExp -- (200302) 269 int i, cnt = 0; 270 271 if (0 == ln->digitCount) 272 { // handle zero 273 strncpy("+0E0", str); 274 } // handle zero 275 else 276 { // handle non-zero 277 str[cnt++] = (0 > ln->sign) ? '-' : '+'; 278 str[cnt++] = '0' + ln->array[0]; 279 str[cnt++] = '.'; 280 for (i = 1; i < ln->digitCount; i++) 281 str[cnt++] = '0' + ln->array[i]; 282 str[cnt++] = 'E'; 283 sprintf(&(str[cnt]), "%+ld", (ln->exponent-1)); 284 } // handle non-zero 285 return 0; 286 } // END function LNarr2strExp -- (200302) 287 288 int LNarr2strInt(LARGE_NUMBER_STRUCT *ln, char str[]) 289 // convert the ln struct to a string n integer format with truncate 290 { // BEGIN function LNarr2strInt -- (200302) 291 int i, cnt = 0; 292 293 if ((0 > ln->exponent) || (0 >= ln->digitCount)) 294 { // abs(number) less than 0 or number is zero 295 strncpy("+0", str); 296 } // abs(number) less than 0 or number is zero 297 else 298 { // something to convert 299 int x; 300 301 str[cnt++] = (0 > ln->sign) ? '-' : '+'; 302 x = (ln->exponent > ln->digitCount) ? ln->digitCount : ln->exponent; 303 for (i = 0; i < x; i++) 304 str[cnt++] = '0' + ln->array[i]; 305 x = ln->exponent - ln->digitCount; 306 for (i=0; i < x; i++) 307 str[cnt++] = '0'; 308 str[cnt] = 0; 309 } // something to convert 310 return 0; 311 } // END function LNstrInt -- (200302) 312 313 int LNln2strFloat(LARGE_NUMBER_STRUCT *ln, char str[]) 314 // convert the ln struct to a string in float format 315 { // BEGIN function LNln2strFloat -- (200302) 316 int i, cnt = 0; 317 318 if (0 == ln->digitCount) 319 { // hadle 0 320 strncpy("+0.0", str); 321 } // hadle 0 322 else 323 { // not zero 324 int x1, x2; 325 326 str[cnt++] = (0 > ln->sign) ? '-' : '+'; 327 x1 = (ln->exponent > ln->digitCount) ? ln->digitCount : ln->exponent; 328 for (i = 0; i < x1; i++) 329 str[cnt++] = '0' + ln->array[i]; 330 x2 = ln->exponent - ln->digitCount; 331 if (0 > x2) 332 { // digitCount larger 333 str[cnt++] = '.'; 334 for (i = x1; i < ln->digitCount; i++) 335 str[cnt++] = '0' + ln->array[i]; 336 } // digitCount larger 337 else 338 { // exponent larger 339 for (i=0; i < x2; i++) 340 str[cnt++] = '0'; 341 str[cnt++] = '.'; 342 str[cnt++] = '0'; 343 } // exponent larger 344 str[cnt++] = 0; 345 } // not zero 346 return 0; 347 } // END function LNstrFloat -- (200302) 348 349 int LNshift(LARGE_NUMBER_STRUCT *ln, int cnt) 350 // shift the implied decimal point 351 { // BEGIN function LiNshift -- (200302) 352 // errorLevel - Errorlevel to return. 353 // i - Loop variable. 354 int i, errorLevel = 0; 355 356 if (0 < ln->digitCount) 357 if (0 < cnt) 358 { // non-negative - do the shift 359 for ((i = ln->digitCount - 1); i >= 0 ; i --) 360 ln->array[i + cnt] = ln->array[i]; 361 for (i = 0; i < cnt; i ++) 362 ln->array[i] = 0; 363 ln->exponent += cnt; 364 ln->digitCount += cnt; 365 } // non-negative - do the shift 366 else 367 if (0 != cnt) 368 { // can't do it 369 fprintf (stderr, "Error: Cannot shift negative bits.\n"); 370 errorLevel = 1; 371 } // can't do it 372 return errorLevel; 373 } // END function LNshift -- (200302) 374 375 int LNnormalize(LARGE_NUMBER_STRUCT *ln) 376 // fix LN so that arr[0] <> 0 (if possible) 377 { // BEGIN function LNnormalize -- (200302) 378 // errorLevel - Errorlevel to return. 379 // zeroCount - How many zeroes? 380 // i - Loop variable 381 int i, errorLevel = 0, zeroCount = 0; 382 383 if (0 < ln->digitCount) 384 { // digits to process 385 while ((ln->array[zeroCount] == 0) && (zeroCount < ln->digitCount)) 386 { // count leading zeroes 387 zeroCount ++; 388 } // count leading zeroes 389 if (0 < zeroCount) 390 { // found leading zeroes 391 if (zeroCount == ln->digitCount) 392 { // entire number is zero 393 ln->exponent = 0; 394 ln->digitCount = 0; 395 ln->sign = 1; 396 } // entire number is zero 397 else 398 { // digits to shift 399 ln->digitCount -= zeroCount; 400 ln->exponent -= zeroCount; 401 for (i = 0; i < ln->digitCount; i++) 402 { // shift them 403 ln->array[i] = ln->array[i + zeroCount]; 404 } // shift them 405 } // digits to shift 406 } // found leading zeroes 407 // handle railing zeroes 408 i = ln->digitCount - 1; 409 while ((i >= 0) && (0 == ln->array[i])) 410 { // while 411 ln->digitCount--; 412 i--; 413 } // while 414 if (0 == ln->digitCount) 415 { // entire number is zero 416 ln->exponent = 0; 417 ln->sign = 1; 418 } // entire number is zero 419 } // digits to process 420 return (errorLevel); 421 } // END function LNnormalize -- (200302) 422 423 int LNadd(LARGE_NUMBER_STRUCT *lna, LARGE_NUMBER_STRUCT *lnb, 424 LARGE_NUMBER_STRUCT *ln3) 425 // ln3=ln1+ln2 426 { // BEGIN function LNadd -- (200302) 427 int i, cnt, state = 0, carry = 0; 428 LARGE_NUMBER_STRUCT ln1, ln2; 429 430 if (0 == lna->digitCount) 431 *ln3 = *lnb; 432 else 433 if (0 == lnb->digitCount) 434 *ln3 = *lna; 435 else 436 { // add non-zero numbers 437 ln1 = *lna; 438 ln2 = *lnb; 439 if (ln1.sign != ln2.sign) 440 { // signs different 441 LNnegate(&ln2); 442 state = LNsubtract(&ln1, &ln2, ln3); 443 } // signs different 444 else 445 { // signs are same -- continue adding 446 if (ln1.exponent > ln2.exponent) 447 { // ln1 is biger 448 LNshift(&ln1, 1); 449 LNshift(&ln2, (ln1.exponent - ln2.exponent)); 450 } // ln1 is biger 451 else 452 { // ln2 is biger 453 LNshift(&ln2, 1); 454 LNshift(&ln1, (ln2.exponent - ln1.exponent)); 455 } // ln2 is biger 456 457 if (ln1.digitCount > ln2.digitCount) 458 { // 1 has more digits 459 for (i = ln1.digitCount - 1; i >= ln2.digitCount; i--) 460 ln3->array[i] = ln1.array[i]; 461 cnt = ln2.digitCount; 462 ln3->digitCount = ln1.digitCount; 463 } // 1 has more digits 464 else 465 { // 2 has more digits 466 for (i = ln2.digitCount - 1; i >= ln1.digitCount; i--) 467 ln3->array[i] = ln2.array[i]; 468 cnt = ln1.digitCount; 469 ln3->digitCount = ln2.digitCount; 470 } // 2 has more digits 471 // now actually add 472 ln3->exponent = ln1.exponent; 473 for (i = cnt - 1; i >= 0; i--) 474 { // for 475 ln3->array[i] = ln1.array[i] + ln2.array[i] + carry; 476 if (ln3->array[i] > 9) 477 { // set carry 478 carry = 1; 479 ln3->array[i] -= 10; 480 } // set carry 481 else 482 { // reset carry 483 carry = 0; 484 } // reset carry 485 } // for 486 LNnormalize(ln3); 487 } // signs are same -- continue adding 488 } // add non-zero numbers 489 return state; 490 } // END function LNadd -- (200302) 491 492 int LNsubtract(LARGE_NUMBER_STRUCT *lna, LARGE_NUMBER_STRUCT *lnb, 493 LARGE_NUMBER_STRUCT *ln3) 494 // ln3=ln1-ln2 495 { // BEGIN function LNsubtract -- (200303) 496 int toReturn = 0; 497 LARGE_NUMBER_STRUCT ln1, ln2; 498 499 ln1 = *lna; 500 ln2 = *lnb; 501 502 if (0 == lna->digitCount) 503 { // first number is zero 504 *ln3 = *lnb; 505 LNnegate(ln3); 506 } // first number is zero 507 else 508 if (0 == lnb->digitCount) 509 *ln3 = *lna; 510 else 511 { // subtract non-zero numbers 512 if (ln1.sign != ln2.sign) 513 { // signs different 514 LNnegate(&ln2); 515 toReturn = LNadd(&ln1, &ln2, ln3); 516 } // signs different 517 else 518 { // signs are same - so subtract 519 int t, i, tmp, borrow = 0; 520 521 t = LNcompare(&ln1, &ln2); 522 if (0 == t) 523 { // same number - return 9 524 ln3->sign = 1; 525 ln3->exponent = 0; 526 ln3->digitCount = 0; 527 } // same number - return 9 528 else 529 if (0 > t) 530 { // first number smaller 531 toReturn = LNsubtract(&ln2, &ln1, ln3); 532 ln3->sign = -1 * ln3->sign; 533 } // first number smaller 534 else 535 { // everything okay - actually subtract 536 ln3->sign = ln1.sign; 537 ln3->exponent = ln1.exponent; 538 LNshift(&ln2, (ln1.exponent - ln2.exponent)); 539 if (ln1.digitCount != ln2.digitCount) 540 if (ln1.digitCount > ln2.digitCount) 541 { // add zeroes to ln2 542 for (i=ln2.digitCount; i < ln1.digitCount; i++) 543 ln2.array[i] = 0; 544 ln2.digitCount = ln1.digitCount; 545 } // add zeroes to ln2 546 else 547 { // add zeroes to ln1 548 for (i=ln1.digitCount; i < ln2.digitCount; i++) 549 ln1.array[i] = 0; 550 ln1.digitCount = ln2.digitCount; 551 } // add zeroes to ln1 552 553 for (i = ln1.digitCount - 1; i >= 0; i--) 554 { // loop through each digit 555 tmp = borrow + ln2.array[i]; 556 if (ln1.array[i] > tmp) 557 { // no borrow 558 ln3->array[i] = ln1.array[i] - tmp; 559 borrow = 0; 560 } // no borrow 561 else 562 { // have to borrow 563 ln3->array[i] = (10 + ln1.array[i]) - tmp; 564 borrow = 1; 565 } // have to borrow 566 } // loop through each digit 567 LNnormalize(ln3); 568 } // everything okay - actually subtract 569 } // signs are same - so subtract 570 } // subtract non-zero numbers 571 return toReturn; 572 } // END function LNsubtract -- (200303) 573 574 int LNmultiply(LARGE_NUMBER_STRUCT *ln1, LARGE_NUMBER_STRUCT *ln2, 575 LARGE_NUMBER_STRUCT *ln3) 576 // ln3=ln1*ln2 577 { // BEGIN function LNmultiply -- (200303) 578 if ((0 == ln1->digitCount) || (0 == ln2->digitCount)) 579 { // multiply by 0 and get 0 580 ln3->digitCount = 0; 581 ln3->sign = 0; 582 ln3->exponent = 0; 583 ln3->array[0] = 0; 584 } // multiply by 0 and get 0 585 else 586 { // guess we have to multiply 587 int i1, i2, i3, dig, tmp, carry; 588 589 ln3->sign = ln1->sign * ln2->sign; 590 ln3->exponent = ln1->exponent + ln2->exponent; 591 ln3->digitCount = ln1->digitCount + ln2->digitCount; 592 dig = ln3->digitCount - 1; 593 // zero out ln3 so that it can be summed into 594 for (i3=0; i3 <= dig; i3++) 595 ln3->array[i3] = 0; 596 for (i2=ln2->digitCount - 1; i2 >= 0; i2--) 597 { // loop through the second numbers digits 598 carry = 0; 599 i3 = dig--; 600 for (i1=ln1->digitCount - 1; i1 >= 0; i1--) 601 { // process first number 602 tmp = (ln1->array[i1] * ln2->array[i2]) + carry + ln3->array[i3]; 603 if (tmp > 9) 604 { // deal with overflow 605 carry = tmp / 10; 606 ln3->array[i3] = (tmp % 10); 607 } // deal with overflow 608 else 609 { // no overflow 610 carry = 0; 611 ln3->array[i3] = tmp; 612 } // no overflow 613 i3--; 614 } // process first number 615 ln3->array[i3] = ln3->array[i3] + carry; 616 } // loop through the second numbers digits 617 LNnormalize(ln3); 618 } // guess we have to multiply 619 return 0; 620 } // END function LNmultiply -- (200303) 621 622 int LNdivide(LARGE_NUMBER_STRUCT *ln1, long int i2, LARGE_NUMBER_STRUCT *ln3) 623 // ln3=ln1/i2 624 { // BEGIN function LNdivide -- (200303) 625 int i, tot = 0; 626 627 ln3->exponent = ln1->exponent; 628 ln3->sign = ln1->sign * ((0 < i2) ? 1 : -1); 629 for (i=0; i < ln1->digitCount; i++) 630 { // for each digit 631 tot += ln1->array[i]; 632 if (tot >= i2) 633 { // we can divide 634 ln3->array[i] = tot / i2; 635 tot = (tot % i2) * 10; 636 } // we can divide 637 else 638 { // can't divide yet, so add a zero 639 ln3->array[i] = 0; 640 tot *= 10; 641 } // can't divide yet, so add a zero 642 } // for each digit 643 644 ln3->digitCount = i; 645 while ((LN_MAX_DIGITS > ln3->digitCount) && (0 < tot)) 646 { // add zeroes on right 647 if (tot >= i2) 648 { // we can divide 649 ln3->array[ln3->digitCount] = tot / i2; 650 tot = (tot % i2) * 10; 651 } // we can divide 652 else 653 { // can't divide yet, so add a zero 654 ln3->array[ln3->digitCount] = 0; 655 tot *= 10; 656 } // can't divide yet, so add a zero 657 ln3->digitCount++; 658 } // add zeroes on right 659 LNnormalize(ln3); 660 return 0; 661 } // END function LNdivide -- (200303) 662 663 int LNdcnvrt(double d, LARGE_NUMBER_STRUCT *n) 664 // convert a double to Large Number 665 { // BEGIN function LNdcnvrt -- (200303) 666 char str[LN_MAX_DIGITS]; 667 668 sprintf(str, "%ld:", d); 669 return LNstr2arr(str, n); 670 } // END function LNdcnvrt -- (200303) 671 672 int LNcopy(LARGE_NUMBER_STRUCT *ln1, LARGE_NUMBER_STRUCT *ln2) 673 // copy from ln1 to ln2 674 { // BEGIN function LNcopy -- (200302) 675 int i; 676 677 ln2->sign = ln1->sign; 678 ln2->exponent = ln1->exponent; 679 ln2->digitCount = ln1->digitCount; 680 for (i=0; i < ln1->digitCount; i++) 681 ln2->array[i] = ln1->array[i]; 682 return 0; 683 } // END function LNcopy -- (200302)
Large Number Example Source Code
1 #include <stdio.h> 2 #define DEBUG1 (1 != 1) 3 4 #include "LargeNumber.c" 5 6 int main () 7 { /* begin FUNCTION main */ 8 int i; 9 LARGE_NUMBER_STRUCT a; 10 LARGE_NUMBER_STRUCT b; 11 LARGE_NUMBER_STRUCT c; 12 int res; 13 long int ii; 14 char num[1000]; 15 char tmp[1000]; 16 17 ii = 123456789; 18 if (DEBUG1) printf ("A\n"); 19 res = LNicnvrt(ii, &a); 20 printf("------- Display Test ----------\n"); 21 LNarr2strExp(&a, num); 22 printf("LNarr2strExp(a)=%s\n",num); 23 LNarr2strInt(&a, num); 24 printf("LNarr2strInt(a)=%s\n",num); 25 LNln2strFloat(&a, num); 26 printf("LNln2strFloat(a)=%s\n",num); 27 LNprint(&a); 28 printf("-------------------------------\n"); 29 30 printf("------- Multiply Test ---------\n"); 31 LNicnvrt(123, &a); 32 LNicnvrt(12, &b); 33 LNmultiply(&a, &b, &c); 34 LNarr2strInt(&a, num); 35 printf("a(%s) * ", num); 36 LNarr2strInt(&b, num); 37 printf("b(%s) ", num); 38 LNarr2strInt(&c, num); 39 printf(" = c(%s)\n", num); 40 printf("\n"); 41 42 printf("-------------------------------\n"); 43 44 printf("------- Divide Test ---------\n"); 45 LNicnvrt(1224, &a); 46 LNdivide(&a, 12, &c); 47 LNarr2strInt(&a, num); 48 printf("a(%s) / 12 ", num); 49 LNarr2strExp(&c, num); 50 printf(" = c(%s)\n", num); 51 printf("\n"); 52 53 LNicnvrt(12, &a); 54 LNdivide(&a, 12, &c); 55 LNarr2strInt(&a, num); 56 printf("a(%s) / 12 ", num); 57 LNarr2strExp(&c, num); 58 printf(" = c(%s)\n", num); 59 printf("\n"); 60 61 LNicnvrt(1, &a); 62 LNdivide(&a, 1, &c); 63 LNarr2strInt(&a, num); 64 printf("a(%s) / 1 ", num); 65 LNarr2strExp(&c, num); 66 printf(" = c(%s)\n", num); 67 printf("\n"); 68 69 LNicnvrt(1, &a); 70 LNdivide(&a, 12, &c); 71 LNarr2strInt(&a, num); 72 printf("a(%s) / 12 ", num); 73 LNarr2strExp(&c, num); 74 printf(" = c(%s)\n", num); 75 printf("\n"); 76 77 LNicnvrt(1, &a); 78 LNdivide(&a, 125, &c); 79 LNarr2strInt(&a, num); 80 printf("a(%s) / 125 ", num); 81 LNarr2strExp(&c, num); 82 printf(" = c(%s)\n", num); 83 84 for (i=100000; i > 0; i = i / 10) { 85 LNstr2arr("1111.111111111", &a); 86 LNdivide(&a, i, &c); 87 LNarr2strInt(&a, num); 88 printf("a(%s) / %d ", num, i); 89 LNarr2strExp(&c, num); 90 printf(" = c(%s)\n", num); } 91 92 tmp = "0.000000000000000000000000000000000000000000000"; 93 strcat(tmp, "0000000000000000000000000001111111111111"); 94 LNstr2arr(tmp, &a); 95 LNdivide(&a, 10, &c); 96 LNarr2strInt(&a, num); 97 printf("a(%s) / 10 ", num); 98 LNarr2strExp(&c, num); 99 printf(" = c(%s)\n", num); 100 101 tmp ="30765988567369.34938637363858653405834085348673"; 102 strcat(tmp, "4086334739573957397534757357345973497375"); 103 strcat(tmp, "734573453957"); 104 LNstr2arr(tmp, &a); 105 LNdivide(&a, 123456789, &c); 106 LNarr2strInt(&a, num); 107 printf("a(%s) / 123456789 ", num); 108 LNarr2strExp(&c, num); 109 printf(" = c(%s)\n", num); 110 111 printf("\n"); 112 113 printf("-------------------------------\n"); 114 LNicnvrt(123, &a); 115 if (DEBUG1) printf ("B\n"); 116 printf("\n"); 117 118 printf("-------------------------------\n"); 119 LNicnvrt(123, &a); 120 if (DEBUG1) printf ("B\n"); 121 res = LNcopy(&a,&b); 122 b.array[b.exponent] = 3; 123 if (DEBUG1) printf ("C\n"); 124 LNprint(&a); 125 printf("%d - %d\n",a.exponent,a.digitCount); 126 LNprint(&b); 127 printf("%d - %d\n",b.exponent,b.digitCount); 128 if (DEBUG1) printf ("D\n"); 129 a.array[0] = 2; 130 LNarr2strExp(&a, num); 131 printf("arr2str: [%s]\n", num); 132 133 a.array[0] = 3; 134 LNarr2strExp(&a, num); 135 printf("ln2strExp: [%s]\n", num); 136 137 a.array[0] = 4; 138 LNarr2strInt(&a, num); 139 printf("ln2strInt: [%s]\n", num); 140 141 a.array[0] = 5; 142 a.exponent = 3; 143 LNarr2strInt(&a, num); 144 printf("ln2strInt: [%s]\n", num); 145 146 a.array[0] = 6; 147 a.exponent = 15; 148 LNarr2strInt(&a, num); 149 printf("ln2strInt: [%s]\n", num); 150 151 a.array[0] = 7; 152 a.exponent = 7; 153 LNln2strFloat(&a, num); 154 printf("ln2strFloat: [%s]\n", num); 155 156 LNadd(&a, &b, &c); 157 LNarr2strExp(&a, num); 158 printf("[%s] + ", num); 159 LNarr2strExp(&b, num); 160 printf("[%s] = ", num); 161 LNarr2strExp(&c, num); 162 printf("[%s]\n", num); 163 164 LNsubtract(&a, &b, &c); 165 LNarr2strExp(&a, num); 166 printf("[%s] - ", num); 167 LNarr2strExp(&b, num); 168 printf("[%s] = ", num); 169 LNarr2strExp(&c, num); 170 printf("[%s]\n", num); 171 172 LNsubtract(&b, &a, &c); 173 LNarr2strExp(&b, num); 174 printf("[%s] - ", num); 175 LNarr2strExp(&a, num); 176 printf("[%s] = ", num); 177 LNarr2strExp(&c, num); 178 printf("[%s]\n", num); 179 180 } /* end FUNCTION main */
Large Number Reduced Source Code
1 #include <ctype.h> 2 #define LN_MAX_DIGITS 1000 3 4 typedef struct LARGE_NUMBER_STRUCT 5 { 6 unsigned short int array[LN_MAX_DIGITS]; 7 signed short int sign; 8 signed long int exponent; 9 signed short int digitCount; 10 } 11 LARGE_NUMBER_STRUCT; 12 13 void LNprint(LARGE_NUMBER_STRUCT *n) 14 { 15 char str[LN_MAX_DIGITS+25]; 16 17 LNarr2strExp(n, str); 18 printf("[%s]\n", str); 19 } 20 21 int LNnegate(LARGE_NUMBER_STRUCT *ln1) 22 { 23 if (0 != ln1->digitCount) 24 ln1->sign *= -1; 25 return 0; 26 } 27 28 int LNcompare(LARGE_NUMBER_STRUCT *ln1, LARGE_NUMBER_STRUCT *ln2) 29 { 30 int toReturn = 0; 31 32 if (ln1->sign ^ ln2->sign) 33 { 34 toReturn = (0 > ln1->sign) ? -1 : 1; 35 } 36 else 37 { 38 if (ln1->exponent != ln2->exponent) 39 { 40 toReturn = (ln1->exponent > ln2->exponent) ? 1 : -1; 41 } 42 else 43 { 44 int i, t; 45 46 t = (ln1->digitCount > ln2->digitCount) ? ln2->digitCount : ln1->digitCount; 47 for (i=0; (i<t) && (0 == toReturn) ; i++) 48 { 49 if (ln1->array[i] != ln2->array[i]) 50 toReturn = (ln1->array[i] > ln2->array[i]) ? ln1->sign : - ln2->sign; 51 } 52 if ((0 == toReturn) && (ln1->digitCount != ln2->digitCount)) 53 toReturn = (ln1->digitCount > ln2->digitCount) ? ln1->sign : - ln2->sign; 54 } 55 } 56 return toReturn; 57 } 58 59 int LNstr2arr(char str[], LARGE_NUMBER_STRUCT *ln) 60 { 61 #define START 1 62 #define NUM1 2 63 #define NUM2 3 64 #define DEC1 4 65 #define DEC2 5 66 #define EXP1 6 67 #define EXP2 7 68 #define EXP3 8 69 int state = START, done = 0, n = 0; 70 signed short int dpflag = 0, numflag = 0, sign = 1; 71 signed long int exp; 72 char *ch = str; 73 74 while ( (isspace(*ch)) || ('0' == *ch) ) ch++; 75 76 if (0 != *ch) 77 { 78 if ('-' == *ch) 79 { 80 sign = -1; 81 ch++; 82 } 83 else 84 if (*ch == '+') 85 { 86 ch++; 87 } 88 89 while (isdigit(*ch)) 90 { 91 state = NUM2; 92 ln->array[n++] = *ch - '0'; 93 ch++; 94 } 95 exp = n; 96 97 if ('.' == *ch) 98 { 99 state = (NUM2 != state) ? DEC1 : DEC2; 100 ch++; 101 102 if (isdigit(*ch)) state = DEC2; 103 while (isdigit(*ch)) 104 { 105 ln->array[n++] = *ch - '0'; 106 ch++; 107 } 108 } 109 110 if (('E' == *ch) || ('e' == *ch)) 111 { 112 signed long int texp; 113 114 state = EXP2; 115 ch++; 116 sscanf(ch, "%d", &texp); 117 exp += texp; 118 } 119 } 120 121 if ((EXP2 == state) || (DEC2 == state) || (NUM2 == state)) 122 { 123 ln->sign = sign; 124 ln->exponent = exp; 125 ln->digitCount = n; 126 state = 0; 127 } 128 return state; 129 } 130 131 int LNicnvrt(long int number, LARGE_NUMBER_STRUCT *n) 132 { 133 int idx, digit, j; 134 135 n->sign = (number < 0) ? -1 : 1; 136 137 n->exponent = 0; 138 idx = LN_MAX_DIGITS; 139 while (number > 0) 140 { 141 digit = number % 10; 142 n->array[--idx] = digit; 143 number /= 10; 144 } 145 n->exponent = LN_MAX_DIGITS - idx; 146 n->digitCount = n->exponent; 147 for (j=0; LN_MAX_DIGITS > (j + idx); j++) 148 { 149 n->array[j] = n->array[idx+j]; 150 } 151 return 0; 152 } 153 154 int LNarr2strExp(LARGE_NUMBER_STRUCT *ln, char str[]) 155 { 156 int i, cnt = 0; 157 158 if (0 == ln->digitCount) 159 { 160 strncpy("+0E0", str); 161 } 162 else 163 { 164 str[cnt++] = (0 > ln->sign) ? '-' : '+'; 165 str[cnt++] = '0' + ln->array[0]; 166 str[cnt++] = '.'; 167 for (i = 1; i < ln->digitCount; i++) 168 str[cnt++] = '0' + ln->array[i]; 169 str[cnt++] = 'E'; 170 sprintf(&(str[cnt]), "%+ld", (ln->exponent-1)); 171 } 172 return 0; 173 } 174 175 int LNarr2strInt(LARGE_NUMBER_STRUCT *ln, char str[]) 176 { 177 int i, cnt = 0; 178 179 if ((0 > ln->exponent) || (0 >= ln->digitCount)) 180 { 181 strncpy("+0", str); 182 } 183 else 184 { 185 int x; 186 187 str[cnt++] = (0 > ln->sign) ? '-' : '+'; 188 x = (ln->exponent > ln->digitCount) ? ln->digitCount : ln->exponent; 189 for (i = 0; i < x; i++) 190 str[cnt++] = '0' + ln->array[i]; 191 x = ln->exponent - ln->digitCount; 192 for (i=0; i < x; i++) 193 str[cnt++] = '0'; 194 str[cnt] = 0; 195 } 196 return 0; 197 } 198 199 int LNln2strFloat(LARGE_NUMBER_STRUCT *ln, char str[]) 200 { 201 int i, cnt = 0; 202 203 if (0 == ln->digitCount) 204 { 205 strncpy("+0.0", str); 206 } 207 else 208 { 209 int x1, x2; 210 211 str[cnt++] = (0 > ln->sign) ? '-' : '+'; 212 x1 = (ln->exponent > ln->digitCount) ? ln->digitCount : ln->exponent; 213 for (i = 0; i < x1; i++) 214 str[cnt++] = '0' + ln->array[i]; 215 x2 = ln->exponent - ln->digitCount; 216 if (0 > x2) 217 { 218 str[cnt++] = '.'; 219 for (i = x1; i < ln->digitCount; i++) 220 str[cnt++] = '0' + ln->array[i]; 221 } 222 else 223 { 224 for (i=0; i < x2; i++) 225 str[cnt++] = '0'; 226 str[cnt++] = '.'; 227 str[cnt++] = '0'; 228 } 229 str[cnt++] = 0; 230 } 231 return 0; 232 } 233 234 int LNshift(LARGE_NUMBER_STRUCT *ln, int cnt) 235 { 236 int i, errorLevel = 0; 237 238 if (0 < ln->digitCount) 239 if (0 < cnt) 240 { 241 for ((i = ln->digitCount - 1); i >= 0 ; i --) 242 ln->array[i + cnt] = ln->array[i]; 243 for (i = 0; i < cnt; i ++) 244 ln->array[i] = 0; 245 ln->exponent += cnt; 246 ln->digitCount += cnt; 247 } 248 else 249 if (0 != cnt) 250 { 251 fprintf (stderr, "Error: Cannot shift negative bits.\n"); 252 errorLevel = 1; 253 } 254 return errorLevel; 255 } 256 257 int LNnormalize(LARGE_NUMBER_STRUCT *ln) 258 { 259 int i, errorLevel = 0, zeroCount = 0; 260 261 if (0 < ln->digitCount) 262 { 263 while ((ln->array[zeroCount] == 0) && (zeroCount < ln->digitCount)) 264 { 265 zeroCount ++; 266 } 267 if (0 < zeroCount) 268 { 269 if (zeroCount == ln->digitCount) 270 { 271 ln->exponent = 0; 272 ln->digitCount = 0; 273 ln->sign = 1; 274 } 275 else 276 { 277 ln->digitCount -= zeroCount; 278 ln->exponent -= zeroCount; 279 for (i = 0; i < ln->digitCount; i++) 280 { 281 ln->array[i] = ln->array[i + zeroCount]; 282 } 283 } 284 } 285 i = ln->digitCount - 1; 286 while ((i >= 0) && (0 == ln->array[i])) 287 { 288 ln->digitCount--; 289 i--; 290 } 291 if (0 == ln->digitCount) 292 { 293 ln->exponent = 0; 294 ln->sign = 1; 295 } 296 } 297 return (errorLevel); 298 } 299 300 int LNadd(LARGE_NUMBER_STRUCT *lna, LARGE_NUMBER_STRUCT *lnb, 301 LARGE_NUMBER_STRUCT *ln3) 302 { 303 int i, cnt, state = 0, carry = 0; 304 LARGE_NUMBER_STRUCT ln1, ln2; 305 306 if (0 == lna->digitCount) 307 *ln3 = *lnb; 308 else 309 if (0 == lnb->digitCount) 310 *ln3 = *lna; 311 else 312 { 313 ln1 = *lna; 314 ln2 = *lnb; 315 if (ln1.sign != ln2.sign) 316 { 317 LNnegate(&ln2); 318 state = LNsubtract(&ln1, &ln2, ln3); 319 } 320 else 321 { 322 if (ln1.exponent > ln2.exponent) 323 { 324 LNshift(&ln1, 1); 325 LNshift(&ln2, (ln1.exponent - ln2.exponent)); 326 } 327 else 328 { 329 LNshift(&ln2, 1); 330 LNshift(&ln1, (ln2.exponent - ln1.exponent)); 331 } 332 333 if (ln1.digitCount > ln2.digitCount) 334 { 335 for (i = ln1.digitCount - 1; i >= ln2.digitCount; i--) 336 ln3->array[i] = ln1.array[i]; 337 cnt = ln2.digitCount; 338 ln3->digitCount = ln1.digitCount; 339 } 340 else 341 { 342 for (i = ln2.digitCount - 1; i >= ln1.digitCount; i--) 343 ln3->array[i] = ln2.array[i]; 344 cnt = ln1.digitCount; 345 ln3->digitCount = ln2.digitCount; 346 } 347 ln3->exponent = ln1.exponent; 348 for (i = cnt - 1; i >= 0; i--) 349 { 350 ln3->array[i] = ln1.array[i] + ln2.array[i] + carry; 351 if (ln3->array[i] > 9) 352 { 353 carry = 1; 354 ln3->array[i] -= 10; 355 } 356 else 357 { 358 carry = 0; 359 } 360 } 361 LNnormalize(ln3); 362 } 363 } 364 return state; 365 } 366 367 int LNsubtract(LARGE_NUMBER_STRUCT *lna, LARGE_NUMBER_STRUCT *lnb, 368 LARGE_NUMBER_STRUCT *ln3) 369 { 370 int toReturn = 0; 371 LARGE_NUMBER_STRUCT ln1, ln2; 372 373 ln1 = *lna; 374 ln2 = *lnb; 375 376 if (0 == lna->digitCount) 377 { 378 *ln3 = *lnb; 379 LNnegate(ln3); 380 } 381 else 382 if (0 == lnb->digitCount) 383 *ln3 = *lna; 384 else 385 { 386 if (ln1.sign != ln2.sign) 387 { 388 LNnegate(&ln2); 389 toReturn = LNadd(&ln1, &ln2, ln3); 390 } 391 else 392 { 393 int t, i, tmp, borrow = 0; 394 395 t = LNcompare(&ln1, &ln2); 396 if (0 == t) 397 { 398 ln3->sign = 1; 399 ln3->exponent = 0; 400 ln3->digitCount = 0; 401 } 402 else 403 if (0 > t) 404 { 405 toReturn = LNsubtract(&ln2, &ln1, ln3); 406 ln3->sign = -1 * ln3->sign; 407 } 408 else 409 { 410 ln3->sign = ln1.sign; 411 ln3->exponent = ln1.exponent; 412 LNshift(&ln2, (ln1.exponent - ln2.exponent)); 413 if (ln1.digitCount != ln2.digitCount) 414 if (ln1.digitCount > ln2.digitCount) 415 { 416 for (i=ln2.digitCount; i < ln1.digitCount; i++) 417 ln2.array[i] = 0; 418 ln2.digitCount = ln1.digitCount; 419 } 420 else 421 { 422 for (i=ln1.digitCount; i < ln2.digitCount; i++) 423 ln1.array[i] = 0; 424 ln1.digitCount = ln2.digitCount; 425 } 426 427 for (i = ln1.digitCount - 1; i >= 0; i--) 428 { 429 tmp = borrow + ln2.array[i]; 430 if (ln1.array[i] > tmp) 431 { 432 ln3->array[i] = ln1.array[i] - tmp; 433 borrow = 0; 434 } 435 else 436 { 437 ln3->array[i] = (10 + ln1.array[i]) - tmp; 438 borrow = 1; 439 } 440 } 441 LNnormalize(ln3); 442 } 443 } 444 } 445 return toReturn; 446 } 447 448 int LNmultiply(LARGE_NUMBER_STRUCT *ln1, LARGE_NUMBER_STRUCT *ln2, 449 LARGE_NUMBER_STRUCT *ln3) 450 { 451 if ((0 == ln1->digitCount) || (0 == ln2->digitCount)) 452 { 453 ln3->digitCount = 0; 454 ln3->sign = 0; 455 ln3->exponent = 0; 456 ln3->array[0] = 0; 457 } 458 else 459 { 460 int i1, i2, i3, dig, tmp, carry; 461 462 ln3->sign = ln1->sign * ln2->sign; 463 ln3->exponent = ln1->exponent + ln2->exponent; 464 ln3->digitCount = ln1->digitCount + ln2->digitCount; 465 dig = ln3->digitCount - 1; 466 for (i3=0; i3 <= dig; i3++) 467 ln3->array[i3] = 0; 468 for (i2=ln2->digitCount - 1; i2 >= 0; i2--) 469 { 470 carry = 0; 471 i3 = dig--; 472 for (i1=ln1->digitCount - 1; i1 >= 0; i1--) 473 { 474 tmp = (ln1->array[i1] * ln2->array[i2]) + carry + ln3->array[i3]; 475 if (tmp > 9) 476 { 477 carry = tmp / 10; 478 ln3->array[i3] = (tmp % 10); 479 } 480 else 481 { 482 carry = 0; 483 ln3->array[i3] = tmp; 484 } 485 i3--; 486 } 487 ln3->array[i3] = ln3->array[i3] + carry; 488 } 489 LNnormalize(ln3); 490 } 491 return 0; 492 } 493 494 int LNdivide(LARGE_NUMBER_STRUCT *ln1, long int i2, LARGE_NUMBER_STRUCT *ln3) 495 { 496 int i, tot = 0; 497 498 ln3->exponent = ln1->exponent; 499 ln3->sign = ln1->sign * ((0 < i2) ? 1 : -1); 500 for (i=0; i < ln1->digitCount; i++) 501 { 502 tot += ln1->array[i]; 503 if (tot >= i2) 504 { 505 ln3->array[i] = tot / i2; 506 tot = (tot % i2) * 10; 507 } 508 else 509 { 510 ln3->array[i] = 0; 511 tot *= 10; 512 } 513 } 514 515 ln3->digitCount = i; 516 while ((LN_MAX_DIGITS > ln3->digitCount) && (0 < tot)) 517 { 518 if (tot >= i2) 519 { 520 ln3->array[ln3->digitCount] = tot / i2; 521 tot = (tot % i2) * 10; 522 } 523 else 524 { 525 ln3->array[ln3->digitCount] = 0; 526 tot *= 10; 527 } 528 ln3->digitCount++; 529 } 530 LNnormalize(ln3); 531 return 0; 532 } 533 534 int LNdcnvrt(double d, LARGE_NUMBER_STRUCT *n) 535 { 536 char str[LN_MAX_DIGITS]; 537 538 sprintf(str, "%ld:", d); 539 return LNstr2arr(str, n); 540 } 541 542 int LNcopy(LARGE_NUMBER_STRUCT *ln1, LARGE_NUMBER_STRUCT *ln2) 543 { 544 int i; 545 546 ln2->sign = ln1->sign; 547 ln2->exponent = ln1->exponent; 548 ln2->digitCount = ln1->digitCount; 549 for (i=0; i < ln1->digitCount; i++) 550 ln2->array[i] = ln1->array[i]; 551 return 0; 552 }
Large Number Minimized Code
1 #include <ctype.h> 2 #define LMD 1000 3 4 typedef struct LNS 5 { 6 unsigned short int a[LMD]; 7 signed short int sign; 8 signed long int exp; 9 signed short int dc; 10 } 11 LNS; 12 13 void LNprint(LNS *n) 14 { 15 char str[LMD+25]; 16 17 LNarr2strExp(n, str); 18 printf("[%s]\n", str); 19 } 20 21 int LNnegate(LNS *ln1) 22 { 23 if (0 != ln1->dc) 24 ln1->sign *= -1; 25 return 0; 26 } 27 28 int LNcompare(LNS *ln1, LNS *ln2) 29 { 30 int ret = 0; 31 32 if (ln1->sign ^ ln2->sign) 33 { 34 ret = (0 > ln1->sign) ? -1 : 1; 35 } 36 else 37 { 38 if (ln1->exp != ln2->exp) 39 { 40 ret = (ln1->exp > ln2->exp) ? 1 : -1; 41 } 42 else 43 { 44 int i, t; 45 46 t = (ln1->dc > ln2->dc) ? ln2->dc : ln1->dc; 47 for (i=0; (i<t) && (0 == ret) ; i++) 48 { 49 if (ln1->a[i] != ln2->a[i]) 50 ret = (ln1->a[i] > ln2->a[i]) ? ln1->sign : - ln2->sign; 51 } 52 if ((0 == ret) && (ln1->dc != ln2->dc)) 53 ret = (ln1->dc > ln2->dc) ? ln1->sign : - ln2->sign; 54 } 55 } 56 return ret; 57 } 58 59 int LNstr2arr(char str[], LNS *ln) 60 { 61 #define START 1 62 #define NUM1 2 63 #define NUM2 3 64 #define DEC1 4 65 #define DEC2 5 66 #define EXP1 6 67 #define EXP2 7 68 #define EXP3 8 69 int state = START, done = 0, n = 0; 70 signed short int dpflag = 0, numflag = 0, sign = 1; 71 signed long int exp; 72 char *ch = str; 73 74 while ( (isspace(*ch)) || ('0' == *ch) ) ch++; 75 76 if (0 != *ch) 77 { 78 if ('-' == *ch) 79 { 80 sign = -1; 81 ch++; 82 } 83 else 84 if (*ch == '+') 85 { 86 ch++; 87 } 88 89 while (isdigit(*ch)) 90 { 91 state = NUM2; 92 ln->a[n++] = *ch - '0'; 93 ch++; 94 } 95 exp = n; 96 97 if ('.' == *ch) 98 { 99 state = (NUM2 != state) ? DEC1 : DEC2; 100 ch++; 101 102 if (isdigit(*ch)) state = DEC2; 103 while (isdigit(*ch)) 104 { 105 ln->a[n++] = *ch - '0'; 106 ch++; 107 } 108 } 109 110 if (('E' == *ch) || ('e' == *ch)) 111 { 112 signed long int texp; 113 114 state = EXP2; 115 ch++; 116 sscanf(ch, "%d", &texp); 117 exp += texp; 118 } 119 } 120 121 if ((EXP2 == state) || (DEC2 == state) || (NUM2 == state)) 122 { 123 ln->sign = sign; 124 ln->exp = exp; 125 ln->dc = n; 126 state = 0; 127 } 128 return state; 129 } 130 131 int LNicnvrt(long int number, LNS *n) 132 { 133 int idx, digit, j; 134 135 n->sign = (number < 0) ? -1 : 1; 136 137 n->exp = 0; 138 idx = LMD; 139 while (number > 0) 140 { 141 digit = number % 10; 142 n->a[--idx] = digit; 143 number /= 10; 144 } 145 n->exp = LMD - idx; 146 n->dc = n->exp; 147 for (j=0; LMD > (j + idx); j++) 148 { 149 n->a[j] = n->a[idx+j]; 150 } 151 return 0; 152 } 153 154 int LNarr2strExp(LNS *ln, char str[]) 155 { 156 int i, cnt = 0; 157 158 if (0 == ln->dc) 159 { 160 strncpy("+0E0", str); 161 } 162 else 163 { 164 str[cnt++] = (0 > ln->sign) ? '-' : '+'; 165 str[cnt++] = '0' + ln->a[0]; 166 str[cnt++] = '.'; 167 for (i = 1; i < ln->dc; i++) 168 str[cnt++] = '0' + ln->a[i]; 169 str[cnt++] = 'E'; 170 sprintf(&(str[cnt]), "%+ld", (ln->exp-1)); 171 } 172 return 0; 173 } 174 175 int LNarr2strInt(LNS *ln, char str[]) 176 { 177 int i, cnt = 0; 178 179 if ((0 > ln->exp) || (0 >= ln->dc)) 180 { 181 strncpy("+0", str); 182 } 183 else 184 { 185 int x; 186 187 str[cnt++] = (0 > ln->sign) ? '-' : '+'; 188 x = (ln->exp > ln->dc) ? ln->dc : ln->exp; 189 for (i = 0; i < x; i++) 190 str[cnt++] = '0' + ln->a[i]; 191 x = ln->exp - ln->dc; 192 for (i=0; i < x; i++) 193 str[cnt++] = '0'; 194 str[cnt] = 0; 195 } 196 return 0; 197 } 198 199 int LNln2strFloat(LNS *ln, char str[]) 200 { 201 int i, cnt = 0; 202 203 if (0 == ln->dc) 204 { 205 strncpy("+0.0", str); 206 } 207 else 208 { 209 int x1, x2; 210 211 str[cnt++] = (0 > ln->sign) ? '-' : '+'; 212 x1 = (ln->exp > ln->dc) ? ln->dc : ln->exp; 213 for (i = 0; i < x1; i++) 214 str[cnt++] = '0' + ln->a[i]; 215 x2 = ln->exp - ln->dc; 216 if (0 > x2) 217 { 218 str[cnt++] = '.'; 219 for (i = x1; i < ln->dc; i++) 220 str[cnt++] = '0' + ln->a[i]; 221 } 222 else 223 { 224 for (i=0; i < x2; i++) 225 str[cnt++] = '0'; 226 str[cnt++] = '.'; 227 str[cnt++] = '0'; 228 } 229 str[cnt++] = 0; 230 } 231 return 0; 232 } 233 234 int LNshift(LNS *ln, int cnt) 235 { 236 int i, errorLevel = 0; 237 238 if (0 < ln->dc) 239 if (0 < cnt) 240 { 241 for ((i = ln->dc - 1); i >= 0 ; i --) 242 ln->a[i + cnt] = ln->a[i]; 243 for (i = 0; i < cnt; i ++) 244 ln->a[i] = 0; 245 ln->exp += cnt; 246 ln->dc += cnt; 247 } 248 else 249 if (0 != cnt) 250 { 251 fprintf (stderr, "Error: Cannot shift negative bits.\n"); 252 errorLevel = 1; 253 } 254 return errorLevel; 255 } 256 257 int LNnormalize(LNS *ln) 258 { 259 int i, errorLevel = 0, zeroCount = 0; 260 261 if (0 < ln->dc) 262 { 263 while ((ln->a[zeroCount] == 0) && (zeroCount < ln->dc)) 264 { 265 zeroCount ++; 266 } 267 if (0 < zeroCount) 268 { 269 if (zeroCount == ln->dc) 270 { 271 ln->exp = 0; 272 ln->dc = 0; 273 ln->sign = 1; 274 } 275 else 276 { 277 ln->dc -= zeroCount; 278 ln->exp -= zeroCount; 279 for (i = 0; i < ln->dc; i++) 280 { 281 ln->a[i] = ln->a[i + zeroCount]; 282 } 283 } 284 } 285 i = ln->dc - 1; 286 while ((i >= 0) && (0 == ln->a[i])) 287 { 288 ln->dc--; 289 i--; 290 } 291 if (0 == ln->dc) 292 { 293 ln->exp = 0; 294 ln->sign = 1; 295 } 296 } 297 return (errorLevel); 298 } 299 300 int LNadd(LNS *lna, LNS *lnb, 301 LNS *ln3) 302 { 303 int i, cnt, state = 0, carry = 0; 304 LNS ln1, ln2; 305 306 if (0 == lna->dc) 307 *ln3 = *lnb; 308 else 309 if (0 == lnb->dc) 310 *ln3 = *lna; 311 else 312 { 313 ln1 = *lna; 314 ln2 = *lnb; 315 if (ln1.sign != ln2.sign) 316 { 317 LNnegate(&ln2); 318 state = LNsubtract(&ln1, &ln2, ln3); 319 } 320 else 321 { 322 if (ln1.exp > ln2.exp) 323 { 324 LNshift(&ln1, 1); 325 LNshift(&ln2, (ln1.exp - ln2.exp)); 326 } 327 else 328 { 329 LNshift(&ln2, 1); 330 LNshift(&ln1, (ln2.exp - ln1.exp)); 331 } 332 333 if (ln1.dc > ln2.dc) 334 { 335 for (i = ln1.dc - 1; i >= ln2.dc; i--) 336 ln3->a[i] = ln1.a[i]; 337 cnt = ln2.dc; 338 ln3->dc = ln1.dc; 339 } 340 else 341 { 342 for (i = ln2.dc - 1; i >= ln1.dc; i--) 343 ln3->a[i] = ln2.a[i]; 344 cnt = ln1.dc; 345 ln3->dc = ln2.dc; 346 } 347 ln3->exp = ln1.exp; 348 for (i = cnt - 1; i >= 0; i--) 349 { 350 ln3->a[i] = ln1.a[i] + ln2.a[i] + carry; 351 if (ln3->a[i] > 9) 352 { 353 carry = 1; 354 ln3->a[i] -= 10; 355 } 356 else 357 { 358 carry = 0; 359 } 360 } 361 LNnormalize(ln3); 362 } 363 } 364 return state; 365 } 366 367 int LNsubtract(LNS *lna, LNS *lnb, 368 LNS *ln3) 369 { 370 int ret = 0; 371 LNS ln1, ln2; 372 373 ln1 = *lna; 374 ln2 = *lnb; 375 376 if (0 == lna->dc) 377 { 378 *ln3 = *lnb; 379 LNnegate(ln3); 380 } 381 else 382 if (0 == lnb->dc) 383 *ln3 = *lna; 384 else 385 { 386 if (ln1.sign != ln2.sign) 387 { 388 LNnegate(&ln2); 389 ret = LNadd(&ln1, &ln2, ln3); 390 } 391 else 392 { 393 int t, i, tmp, borrow = 0; 394 395 t = LNcompare(&ln1, &ln2); 396 if (0 == t) 397 { 398 ln3->sign = 1; 399 ln3->exp = 0; 400 ln3->dc = 0; 401 } 402 else 403 if (0 > t) 404 { 405 ret = LNsubtract(&ln2, &ln1, ln3); 406 ln3->sign = -1 * ln3->sign; 407 } 408 else 409 { 410 ln3->sign = ln1.sign; 411 ln3->exp = ln1.exp; 412 LNshift(&ln2, (ln1.exp - ln2.exp)); 413 if (ln1.dc != ln2.dc) 414 if (ln1.dc > ln2.dc) 415 { 416 for (i=ln2.dc; i < ln1.dc; i++) 417 ln2.a[i] = 0; 418 ln2.dc = ln1.dc; 419 } 420 else 421 { 422 for (i=ln1.dc; i < ln2.dc; i++) 423 ln1.a[i] = 0; 424 ln1.dc = ln2.dc; 425 } 426 427 for (i = ln1.dc - 1; i >= 0; i--) 428 { 429 tmp = borrow + ln2.a[i]; 430 if (ln1.a[i] > tmp) 431 { 432 ln3->a[i] = ln1.a[i] - tmp; 433 borrow = 0; 434 } 435 else 436 { 437 ln3->a[i] = (10 + ln1.a[i]) - tmp; 438 borrow = 1; 439 } 440 } 441 LNnormalize(ln3); 442 } 443 } 444 } 445 return ret; 446 } 447 448 int LNmultiply(LNS *ln1, LNS *ln2, 449 LNS *ln3) 450 { 451 if ((0 == ln1->dc) || (0 == ln2->dc)) 452 { 453 ln3->dc = 0; 454 ln3->sign = 0; 455 ln3->exp = 0; 456 ln3->a[0] = 0; 457 } 458 else 459 { 460 int i1, i2, i3, dig, tmp, carry; 461 462 ln3->sign = ln1->sign * ln2->sign; 463 ln3->exp = ln1->exp + ln2->exp; 464 ln3->dc = ln1->dc + ln2->dc; 465 dig = ln3->dc - 1; 466 for (i3=0; i3 <= dig; i3++) 467 ln3->a[i3] = 0; 468 for (i2=ln2->dc - 1; i2 >= 0; i2--) 469 { 470 carry = 0; 471 i3 = dig--; 472 for (i1=ln1->dc - 1; i1 >= 0; i1--) 473 { 474 tmp = (ln1->a[i1] * ln2->a[i2]) + carry + ln3->a[i3]; 475 if (tmp > 9) 476 { 477 carry = tmp / 10; 478 ln3->a[i3] = (tmp % 10); 479 } 480 else 481 { 482 carry = 0; 483 ln3->a[i3] = tmp; 484 } 485 i3--; 486 } 487 ln3->a[i3] = ln3->a[i3] + carry; 488 } 489 LNnormalize(ln3); 490 } 491 return 0; 492 } 493 494 int LNdivide(LNS *ln1, long int i2, LNS *ln3) 495 { 496 int i, tot = 0; 497 498 ln3->exp = ln1->exp; 499 ln3->sign = ln1->sign * ((0 < i2) ? 1 : -1); 500 for (i=0; i < ln1->dc; i++) 501 { 502 tot += ln1->a[i]; 503 if (tot >= i2) 504 { 505 ln3->a[i] = tot / i2; 506 tot = (tot % i2) * 10; 507 } 508 else 509 { 510 ln3->a[i] = 0; 511 tot *= 10; 512 } 513 } 514 515 ln3->dc = i; 516 while ((LMD > ln3->dc) && (0 < tot)) 517 { 518 if (tot >= i2) 519 { 520 ln3->a[ln3->dc] = tot / i2; 521 tot = (tot % i2) * 10; 522 } 523 else 524 { 525 ln3->a[ln3->dc] = 0; 526 tot *= 10; 527 } 528 ln3->dc++; 529 } 530 LNnormalize(ln3); 531 return 0; 532 } 533 534 int LNdcnvrt(double d, LNS *n) 535 { 536 char str[LMD]; 537 538 sprintf(str, "%ld:", d); 539 return LNstr2arr(str, n); 540 } 541 542 int LNcopy(LNS *ln1, LNS *ln2) 543 { 544 int i; 545 546 ln2->sign = ln1->sign; 547 ln2->exp = ln1->exp; 548 ln2->dc = ln1->dc; 549 for (i=0; i < ln1->dc; i++) 550 ln2->a[i] = ln1->a[i]; 551 return 0; 552 }
|
![[ Powered by Red Hat Linux ]](/icons/rh_pb.png){kind=icon}
![[ Powered by Apache ]](/icons/apache_pb.gif){kind=icon}
![[ Powered by PHP ]](/icons/php_pb.gif){kind=icon}
The statements and opinions included in these pages are those of only. Any statements and
opinions included in these pages are not those of Louisiana
State University or the LSU Board of Supervisors.
© 1999, 2000, 2001, 2002, 2003 Isaac Traxler