Computer Programming Contest Library

[Isaac's Home Page ]  [Fun Page ]  [Class Page ]  [Printable ]  
 Home
 Problem Archive
 Grades
 Tools
 Music
 

Large Number Library

The goal of this library is to produce all the utility routines necessary to work with arbitrarily large numbers.

Large Number Library Source Code

LargeNumber.c

    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

example.c

    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

l.c

    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

l1.c

    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 ] [ Powered by Apache ] [ Powered by PHP ]

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