home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 228_01 / strmath.c < prev    next >
Text File  |  1987-07-31  |  23KB  |  1,068 lines
  1. /*
  2. HEADER:         CUGXXX; 
  3. TITLE:          String-math functions; 
  4. DATE:           4-1-84;
  5. DESCRIPTION:    String to math functions;
  6. KEYWORDS:       Mathematical functions;
  7. FILENAME:       STRMATH.C;
  8. WARNINGS:       For IBM PC without 8087 NDP, must be written using only 
  9.                 C functions (enhancement packages);
  10. AUTHORS:        Robert E. Sawyer; 
  11. COMPILER:       DeSmet C; 
  12. REFERENCES:     US-DISK 1308 (SMATH.C), Knuth, Art of Computer Programming
  13.                 V.2, and C. E. Burton, DDJ, #89, 'RSA: A Public Key 
  14.                 Cryptosystem, Part 1'. 
  15. ENDREF
  16. */
  17. /*
  18.  *    Program name:  strmath.c
  19.  *
  20.  *    Program author:  Robert E. Sawyer
  21.  *               Torrance, California
  22.  *
  23.  *    Released for personal, non-commercial use only, 1 August 1984.
  24.  *
  25.  *    Specifications to which the main functions were written:
  26.  *      They must do decimal arithmetic on numbers stored in strings.
  27.  *      The numbers must be in the form:
  28.  *
  29.  *      Snnnnnnn.nnnn
  30.  *
  31.  *      where "S" is an optional sign (+ or -), "n" is any
  32.  *      decimal digit (0 through 9) and "." is an optional
  33.  *      decimal point.  The four routines should be called
  34.  *      "decadd", "decsub", "decmul", and "decdiv", and they
  35.  *      each must be called as follows:
  36.  *
  37.  *          char n1[21],n2[21],result[21];
  38.  *          strcpy (n1,"123.45");
  39.  *          strcpy (n2,"-3.0)";
  40.  *
  41.  *          if (!decadd(result,n1,n2))
  42.  *              printf ("Error adding %s to %s\n", n1, n2);
  43.  *          else
  44.  *              printf ("Result is %s\n", result);
  45.  *
  46.  *      In this example, the program should print
  47.  *
  48.  *          Result is 120.45
  49.  *
  50.  *      "decsub", "decmul", and "decdiv" should work the same
  51.  *      way.
  52.  *
  53.  *      These routines should return a 1 (true) if the arguments
  54.  *      are valid and the result can be calculated, and a 0
  55.  *      (false) if anything is wrong.  In the case of an error,
  56.  *      the "result" argument should contain a null value.
  57.  *
  58.  *      The strings may have from 1 to 18 significant digits.
  59.  *      Since there can be a leading sign and a decimal point,
  60.  *      the strings must be able to hold at least 20 characters.
  61.  *      They are dimensioned with 21 above to handle the 20
  62.  *      character limit plus the trailing zero needed in C
  63.  *      strings.
  64.  *
  65.  *      If the result will be too long (i.e. more than 18
  66.  *      significant digits) treat that case as an error
  67.  *      (i.e., return a 0 and set "result" to be a null).
  68.  *      The same holds true for an attempted division by zero.
  69.  *
  70.  *      Math must be EXACT (!!) -- that means no rounding!
  71.  *      These routines must run on an IBM PC without an
  72.  *      8087 chip, and they must be written using only
  73.  *      C functions (i.e., no "C Tools", "C Food", or
  74.  *      other enhancement packages).
  75.  *
  76.  *    Sources:    The lowest level string-math functions are modelled
  77.  *      on corresponding algorithms in D.E.Knuth's, 'The Art of
  78.  *      Computer Programming', Vol.2, and on C.E.Burton's algorithms
  79.  *      in DDJ, #89, 'RSA: A Public Key Cryptosystem, Part 1'.
  80.  */
  81.  
  82. #define N    18     /*chosen maximum number of significant digits */
  83. #define MIN(x, y)  ((x) > (y) ? (y) : (x))
  84. #define MAX(x, y)  ((x) > (y) ? (x) : (y))
  85.  
  86. /*-----------------driver to test the functions-------------------*/
  87. main()
  88.     {
  89.     char n1[N+3], n2[N+3], nn1[N+3], nn2[N+3], res1[N+3], res2[N+3];
  90.     int l1, l2, lr1, lr2, ok;
  91.     char msg[N+3];
  92.  
  93.     printf("Arithmetic to %.0d significant digits\n\n", N);
  94.     while (1)
  95.     {
  96.     printf("Enter 1st number:  ");
  97.     scanf("%s", nn1);
  98.  
  99.      printf("Enter 2nd number:  ");
  100.     scanf("%s", nn2);
  101.  
  102.     l1 = strlen(nn1);
  103.     l2 = strlen(nn2);
  104.  
  105.     strcpy(n1, nn1);
  106.     strcpy(n2, nn2);
  107.  
  108.     ok = decadd(res1, n1, n2);
  109.     if (!ok)
  110.         strcpy(msg, "*ERROR*");
  111.     else
  112.         msg[0] = '\0';
  113.     printf("\n ADD -> %s  %s\n", res1, msg);
  114.  
  115.     ok = decsub(res1, n1, n2);
  116.     if (!ok)
  117.         strcpy(msg, "*ERROR*");
  118.     else
  119.         msg[0] = '\0';
  120.     printf("\n SUB -> %s  %s\n", res1, msg);
  121.  
  122.     ok = decmul(res1, n1, n2);
  123.     if (!ok)
  124.         strcpy(msg, "*ERROR*");
  125.     else
  126.         msg[0] = '\0';
  127.     printf("\n MUL -> %s  %s\n", res1, msg);
  128.  
  129.     ok = decdiv(res1, n1, n2);
  130.     if (!ok)
  131.         strcpy(msg, "*ERROR*");
  132.     else
  133.         msg[0] = '\0';
  134.     printf("\n DIV -> %s  %s\n", res1, msg);
  135.  
  136.     printf("-------------\n");
  137.     }
  138.     }
  139.  
  140. /*---------------------main functions--------------------------*/
  141.  
  142. decadd(sum, n1, n2)
  143.     char sum[], n1[], n2[];
  144.     {
  145.     char num[N+3], num1[N+3], num2[N+3];
  146.     int sign1, digl1, digr1, sign2, digl2, digr2;
  147.     int sign, digr;
  148.     int len, len1, len2;
  149.     int del;
  150.  
  151.     if (parse(n1, num1, &sign1, &digl1, &digr1) &&
  152.     parse(n2, num2, &sign2, &digl2, &digr2))
  153.     {
  154.     len1 = strlen(num1);
  155.     len2 = strlen(num2);
  156.     len  = MAX(digl1, digl2) + MAX(digr1, digr2);
  157.     if (len > N)    /* allow for sign, decimal point, and '\0' */
  158.         {
  159.         sum[0] = '\0';
  160.         return (0);
  161.         }
  162.     if (digr1 < digr2)
  163.         {
  164.         del = digr2 - digr1;
  165.         pad(num1, del);
  166.         len1 += del;
  167.         digr = digr2;
  168.         }
  169.     else
  170.         {
  171.         del = digr1 - digr2;
  172.         pad(num2, del);
  173.         len2 += del;
  174.         digr = digr1;
  175.         }
  176.     if (!add(num1, len1, sign1, num2, len2, sign2, num, &sign))
  177.         {
  178.         sum[0] = '\0';
  179.         return (0);
  180.         }
  181.     if ((len = strlen(num)) > N)
  182.         {
  183.         sum[0] = '\0';
  184.         return (0);
  185.         }
  186.     fix(num, len, sign, digr);
  187.     strcpy(sum, num);
  188.     return (1);
  189.     }
  190.     else
  191.     {
  192.     sum[0] = '\0';
  193.     return (0);
  194.     }
  195.     }
  196.  
  197. decsub(dif, n1, n2)
  198.     char dif[], n1[], n2[];
  199.     {
  200.     char num[N+3], num1[N+3], num2[N+3];
  201.     int sign1, digl1, digr1, sign2, digl2, digr2;
  202.     int sign, digr;
  203.     int len, len1, len2;
  204.     int del;
  205.  
  206.     if (parse(n1, num1, &sign1, &digl1, &digr1) &&
  207.     parse(n2, num2, &sign2, &digl2, &digr2))
  208.     {
  209.     len1 = strlen(num1);
  210.     len2 = strlen(num2);
  211.     len  = MAX(digl1, digl2) + MAX(digr1, digr2);
  212.     if (len > N)    /* allow for sign, decimal point, and '\0' */
  213.         {
  214.         dif[0] = '\0';
  215.         return (0);
  216.         }
  217.     if (digr1 < digr2)
  218.         {
  219.         del = digr2 - digr1;
  220.         pad(num1, del);
  221.         len1 += del;
  222.         digr = digr2;
  223.         }
  224.     else
  225.         {
  226.         del = digr1 - digr2;
  227.         pad(num2, del);
  228.         len2 += del;
  229.         digr = digr1;
  230.         }
  231.     if (!sub(num1, len1, sign1, num2, len2, sign2, num, &sign))
  232.         {
  233.         dif[0] = '\0';
  234.         return (0);
  235.         }
  236.     if ((len = strlen(num)) > N)
  237.         {
  238.         dif[0] = '\0';
  239.         return (0);
  240.         }
  241.     fix(num, len, sign, digr);
  242.     strcpy(dif, num);
  243.     return (1);
  244.     }
  245.     else
  246.     {
  247.     dif[0] = '\0';
  248.     return (0);
  249.     }
  250.     }
  251.  
  252. decmul(prod, n1, n2)
  253.     char prod[], n1[], n2[];
  254.     {
  255.     char num[N+3], num1[N+3], num2[N+3];
  256.     int sign1, digl1, digr1, sign2, digl2, digr2;
  257.     int sign, digr;
  258.     int len, len1, len2;
  259.  
  260.     if (parse(n1, num1, &sign1, &digl1, &digr1) &&
  261.     parse(n2, num2, &sign2, &digl2, &digr2))
  262.     {
  263.     len1 = strlen(num1);
  264.     len2 = strlen(num2);
  265.     if (len1+len2-1 > N)    /* allow for sign, decimal point, and '\0' */
  266.         {
  267.         prod[0] = '\0';
  268.         return (0);
  269.         }
  270.     digr = digr1 + digr2;
  271.     if (!mul(num1, len1, sign1, num2, len2, sign2, num, &sign))
  272.         {
  273.         prod[0] = '\0';
  274.         return (0);
  275.         }
  276.     if ((len = strlen(num)) > N)
  277.         {
  278.         prod[0] = '\0';
  279.         return (0);
  280.         }
  281.     fix(num, len, sign, digr);
  282.     strcpy(prod, num);
  283.     return (1);
  284.     }
  285.     else
  286.     {
  287.     prod[0] = '\0';
  288.     return (0);
  289.     }
  290.     }
  291.  
  292. decdiv(quot, n1, n2)
  293.     char quot[], n1[], n2[];
  294.     {
  295.     char num[N+N+1], num1[N+N+1], num2[N+3];
  296.     int sign1, digl1, digr1, sign2, digl2, digr2;
  297.     int sign, digr, digl, inum;
  298.     int len, len1, len2;
  299.  
  300.     if (parse(n1, num1, &sign1, &digl1, &digr1) &&
  301.     parse(n2, num2, &sign2, &digl2, &digr2))
  302.     {
  303.     len1 = strlen(num1);
  304.     len2 = strlen(num2);
  305.     pad(num1, N+N-len1);
  306.     if (!div(num1, N+N, sign1, num2, len2, sign2, num, &sign))
  307.         {
  308.         quot[0] = '\0';
  309.         return (0);
  310.         }
  311.     if ((len=strlen(num))==N+N-len2)
  312.         digl = len1 - len2;
  313.     else
  314.         digl = len1 - len2 + 1;
  315.     for (inum=len-1; (num[inum]=='0') && (inum>0); --inum)
  316.         ;
  317.     num[++inum] = '\0';
  318.     len = inum;
  319.     digr = len - digl + digr1 - digr2;
  320.     if ((len > N) || (digr > N) || (digl > N))
  321.         {
  322.         quot[0] = '\0';
  323.         return (0);
  324.         }
  325.     fix(num, len, sign, digr);
  326.     strcpy(quot, num);
  327.     return (1);
  328.     }
  329.     else
  330.     {
  331.     quot[0] = '\0';
  332.     return (0);
  333.     }
  334.     }
  335.  
  336. /*-----------intermediate level string-math functions----------*/
  337.  
  338. /*    add()
  339.  *    performs the appropriate string math
  340.  */
  341. add(num1, len1, sign1, num2, len2, sign2, num, sign)
  342.     char num1[], num2[], num[];
  343.     int sign1, sign2, *sign;
  344.     int len1, len2;
  345.     {
  346.     if ((sign1>0) && (sign2>0))
  347.     {
  348.     *sign = 1;
  349.     if (!sadd(num1, len1, num2, len2, num))
  350.         return (0);
  351.     }
  352.     else if ((sign1<0) && (sign2<0))
  353.     {
  354.     *sign = -1;
  355.     if (!sadd(num1, len1, num2, len2, num))
  356.         return (0);
  357.     }
  358.     else if ((sign1<0) && (sign2>0))
  359.     {
  360.     if ((len2>len1) || ((len2==len1) && (strcmp(num2,num1) > 0)))
  361.         {
  362.         *sign = 1;
  363.         if (!ssub(num2, len2, num1, len1, num))
  364.         return (0);
  365.         }
  366.     else
  367.         {
  368.         *sign = -1;
  369.         if (!ssub(num1, len1, num2, len2, num))
  370.         return (0);
  371.         }
  372.     }
  373.     else
  374.     {
  375.     if ((len2>len1) || ((len2==len1) && (strcmp(num2,num1) > 0)))
  376.         {
  377.         *sign = -1;
  378.         if (!ssub(num2, len2, num1, len1, num))
  379.         return (0);
  380.         }
  381.     else
  382.         {
  383.         *sign = 1;
  384.         if (!ssub(num1, len1, num2, len2, num))
  385.         return (0);
  386.         }
  387.     }
  388.     return (1);
  389.     }
  390.  
  391. /*    sub()
  392.  *    performs the appropriate string math
  393.  */
  394. sub(num1, len1, sign1, num2, len2, sign2, num, sign)
  395.     char num1[], num2[], num[];
  396.     int sign1, sign2, *sign;
  397.     int len1, len2;
  398.     {
  399.     if ((sign1>0) && (sign2>0))
  400.     {
  401.     if ((len2>len1) || ((len2==len1) && (strcmp(num2,num1) > 0)))
  402.         {
  403.         *sign = -1;
  404.         if (!ssub(num2, len2, num1, len1, num))
  405.         return (0);
  406.         }
  407.     else
  408.         {
  409.         *sign = 1;
  410.         if (!ssub(num1, len1, num2, len2, num))
  411.         return (0);
  412.         }
  413.     }
  414.     else if ((sign1<0) && (sign2<0))
  415.     {
  416.     if ((len2>len1) || ((len2==len1) && (strcmp(num2,num1) > 0)))
  417.         {
  418.         *sign = 1;
  419.          if (!ssub(num2, len2, num1, len1, num))
  420.         return (0);
  421.         }
  422.     else
  423.         {
  424.         *sign = -1;
  425.         if (!ssub(num1, len1, num2, len2, num))
  426.         return (0);
  427.         }
  428.     }
  429.     else if ((sign1<0) && (sign2>0))
  430.     {
  431.     *sign = -1;
  432.     if (!sadd(num2, len2, num1, len1, num))
  433.         return (0);
  434.     }
  435.     else
  436.     {
  437.     *sign = 1;
  438.     if (!sadd(num1, len1, num2, len2, num))
  439.         return (0);
  440.     }
  441.     return (1);
  442.     }
  443.  
  444. /*    mul()
  445.  *    performs the appropriate string math
  446.  */
  447. mul(num1, len1, sign1, num2, len2, sign2, num, sign)
  448.     char num1[], num2[], num[];
  449.     int sign1, sign2, *sign;
  450.     int len1, len2;
  451.     {
  452.     if (sign1*sign2 > 0)
  453.     {
  454.     *sign = 1;
  455.     if (!smul(num1, len1, num2, len2, num))
  456.         return (0);
  457.     }
  458.     else
  459.     {
  460.     *sign = -1;
  461.     if (!smul(num1, len1, num2, len2, num))
  462.         return (0);
  463.     }
  464.     return (1);
  465.     }
  466.  
  467. /*    div()
  468.  *    performs the appropriate string math
  469.  */
  470. div(num1, len1, sign1, num2, len2, sign2, num, sign)
  471.     char num1[], num2[], num[];
  472.     int sign1, sign2, *sign;
  473.     int len1, len2;
  474.     {
  475.     char rem[N+3];
  476.  
  477.     if (sign1*sign2 > 0)
  478.     {
  479.     *sign = 1;
  480.     if (!sdiv(num1, len1, num2, len2, num, rem))
  481.         return (0);
  482.     if (rem[0] > '0')
  483.         return (0);
  484.     }
  485.     else
  486.     {
  487.     *sign = -1;
  488.     if (!sdiv(num1, len1, num2, len2, num, rem))
  489.         return (0);
  490.     if (rem[0] > '0')
  491.         return (0);
  492.     }
  493.     return (1);
  494.     }
  495.  
  496. /*-----------lowest level string-math functions------------*/
  497.  
  498. /*  sadd(), ssub(), smul(), sdiv() perform the lowest level
  499.  *  manipulations on strings interpreted as nonnegative integers.
  500.  *    leading '0's are removed from num1, num2, and from the result
  501.  *  substrings, to which a terminal null is appended;
  502.  *    each function returns 0 on error.
  503.  */
  504.  
  505. /* sadd() yields sum[],
  506.  * lens <= max(len1, len2) + 1
  507.  */
  508. sadd(num1, len1, num2, len2, sum)
  509.     char num1[], num2[], sum[];
  510.     int len1, len2;
  511.     {
  512.     int lens, add, carry, index1, index2, indexs, temp1, temp2;
  513.  
  514.     lens = MAX(len1, len2) + 1;
  515.     indexs = lens - 1;
  516.     index1 = len1 - 1;
  517.     index2 = len2 - 1;
  518.     carry = 0;
  519.     while ( MIN(index1, index2) >= 0)
  520.     {
  521.     temp1 = num1[index1] - '0';
  522.     temp2 = num2[index2] - '0';
  523.     add = carry + temp1 + temp2;
  524.     sum[indexs] = add % 10 + '0';
  525.     carry = add / 10;
  526.     --index1;
  527.     --index2;
  528.     --indexs;
  529.     }
  530.     if (index2 < 0)
  531.     {
  532.     while (index1 >= 0)
  533.         {
  534.         temp1 = num1[index1] - '0';
  535.         add = carry + temp1;
  536.         sum[indexs] = add % 10 + '0';
  537.         carry = add / 10;
  538.         --index1;
  539.         --indexs;
  540.         }
  541.     }
  542.     else
  543.     {
  544.     while (index2 >= 0)
  545.         {
  546.         temp1 = num2[index2] - '0';
  547.         add = carry + temp1;
  548.         sum[indexs] = add % 10 + '0';
  549.         carry = add / 10;
  550.         --index2;
  551.         --indexs;
  552.         }
  553.     }
  554.     sum[indexs] = carry + '0';
  555.     --indexs;
  556.     while (indexs >= 0)
  557.     {
  558.     sum[indexs] = '0';
  559.     --indexs;
  560.     }
  561.     while ((sum[0]=='0') && (lens>1))
  562.     {
  563.     for (indexs=1; indexs<lens; ++indexs)
  564.         sum[indexs-1] = sum[indexs];
  565.     --lens;
  566.     }
  567.     sum[lens] = '\0';
  568.     return lens;
  569.     }
  570.  
  571. /* ssub() yields dif[],
  572.  * lend <= len1
  573.  */
  574. ssub(num1, len1, num2, len2, dif)
  575.     char num1[], num2[], dif[];
  576.     int len1, len2;
  577.     {
  578.     int lend, sub, borrow, index1, index2, indexd, temp1, temp2;
  579.  
  580.     lend = len1;
  581.     if (len1>=len2)
  582.     {
  583.     indexd = lend - 1;
  584.     index1 = len1 - 1;
  585.     index2 = len2 - 1;
  586.     borrow = 0;
  587.  
  588.     while (index2 >= 0)
  589.         {
  590.         temp1 = num1[index1] - '0';
  591.         temp2 = num2[index2] - '0';
  592.         sub = borrow + temp1 - temp2;
  593.         if (sub < 0)
  594.         {
  595.         sub += 10;
  596.         borrow = -1;
  597.         }
  598.         else
  599.         borrow = 0;
  600.         dif[indexd] = sub + '0';
  601.         --index1;
  602.         --index2;
  603.         --indexd;
  604.         }
  605.     while (index1 >= 0)
  606.         {
  607.         temp1 = num1[index1] - '0';
  608.         sub = borrow + temp1;
  609.         if (sub < 0)
  610.         {
  611.         sub += 10;
  612.         borrow = -1;
  613.         }
  614.         else
  615.         borrow = 0;
  616.         dif[indexd] = sub + '0';
  617.         --index1;
  618.         --indexd;
  619.         }
  620.     if (borrow==0)
  621.         while (indexd >= 0)
  622.         {
  623.         dif[indexd] = '0';
  624.         --indexd;
  625.         }
  626.     else
  627.         {
  628.         dif[0] = '\0';
  629.         return 0;
  630.         }
  631.     while ((dif[0]=='0') && (lend>1))
  632.         {
  633.         for (indexd=1; indexd<lend; ++indexd)
  634.         dif[indexd-1] = dif[indexd];
  635.         --lend;
  636.         }
  637.     dif[lend] = '\0';
  638.     }
  639.     else
  640.     {
  641.     dif[0] = '\0';
  642.     return 0;
  643.     }
  644.     return lend;
  645.     }
  646.  
  647. /* smul() yields prod[],
  648.  * lenp <= len1 + len2
  649.  */
  650. smul(num1, len1, num2, len2, prod)
  651.     char num1[], num2[], prod[];
  652.     int len1, len2;
  653.     {
  654.     int lenp, mult, carry, index1, index2, indexp, temp1, temp2, tempp;
  655.  
  656.     lenp = len1 + len2;
  657.     index2 = len2 - 1;
  658.     for (indexp=0; indexp<lenp; ++indexp)
  659.     prod[indexp] = '0';
  660.     while (index2 >= 0)
  661.     {
  662.     indexp = lenp + index2 - len2;
  663.     if (num2[index2] == '0')
  664.         {
  665.         carry = 0;
  666.         indexp -= len1;
  667.         }
  668.     else
  669.         {
  670.         index1 = len1 - 1;
  671.         carry = 0;
  672.         while (index1 >= 0)
  673.         {
  674.         temp1 = num1[index1] - '0';
  675.         temp2 = num2[index2] - '0';
  676.         tempp = prod[indexp] - '0';
  677.         mult = carry + temp1*temp2 + tempp;
  678.         prod[indexp] = mult % 10 + '0';
  679.         carry = mult / 10;
  680.         --index1;
  681.         --indexp;
  682.         }
  683.         }
  684.     prod[indexp] = carry + '0';
  685.     --index2;
  686.     }
  687.     while ((prod[0]=='0') && (lenp>1))
  688.     {
  689.     for (indexp=1; indexp<lenp; ++indexp)
  690.         prod[indexp-1] = prod[indexp];
  691.     --lenp;
  692.     }
  693.     prod[lenp] = '\0';
  694.     return lenp;
  695.     }
  696.  
  697. /* sdiv() yields quot[] and rem[],
  698.  * lenq <= max(len1-len2, 1)
  699.  * lenr <= len2
  700.  */
  701. sdiv(num1, len1, num2, len2, quot, rem)
  702.     char num1[], num2[], quot[], rem[];
  703.     int len1, len2;
  704.     {
  705.     int lenq, lenr, div, flag, scale,
  706.     index, index1, index2, indexq, indexr,
  707.     temp1, temp2, temp3, temp4, temp5, qtest;
  708.  
  709.     if (num1[0] != '0')
  710.     {
  711.     for (index1=len1; index1>0; --index1)
  712.         num1[index1] = num1[index1-1];
  713.     num1[0] = '0';
  714.     ++len1;
  715.     }
  716.     while ((num2[0]=='0') && (len2>1))
  717.     {
  718.     for (index2=1; index2<len2; ++index2)
  719.         num2[index2-1] = num2[index2];
  720.     --len2;
  721.     }
  722.     lenq = MAX(len1-len2, 1);
  723.     lenr = len2;
  724.     if ((len1<len2) || ((len1==len2) && (num1[0]<num2[0])))
  725.     {
  726.     quot[0] = '0';
  727.     lenq = 1;
  728.     strcpy(rem, num1);
  729.     lenr = len1;
  730.     }
  731.     if(num2[0] != '0')
  732.     {
  733.     for (indexq=0; indexq<lenq; ++indexq)
  734.         quot[indexq] = '0';
  735.     for (indexr=0; indexr<lenr; ++indexr)
  736.         rem[indexr] = '0';
  737.     flag = 0;
  738.     for (index1=1; index1<len1; ++index1)
  739.         if (num1[index1] != '0')
  740.         {
  741.         flag = 1;
  742.         break;
  743.         }
  744.     if (flag != 0)
  745.         {
  746.         temp1 = num2[0] - '0';
  747.         scale = 10 / (temp1 + 1);
  748.         if (scale > 1)
  749.         {
  750.         flag = 0;
  751.         index1 = len1 -1;
  752.         while (index1 >= 0)
  753.             {
  754.             temp1 = num1[index1] - '0';
  755.             div = flag + scale*temp1;
  756.             num1[index1] = div % 10 + '0';
  757.             flag = div /10;
  758.             --index1;
  759.             }
  760.         flag = 0;
  761.         index2 = len2 -1;
  762.         while (index2 >= 0)
  763.             {
  764.             temp1 = num2[index2] - '0';
  765.             div = flag + scale*temp1;
  766.             num2[index2] = div % 10 + '0';
  767.             flag = div / 10;
  768.             --index2;
  769.             }
  770.         }
  771.         index1 = 0;
  772.         while (index1 < (len1-len2))
  773.         {
  774.         if (num2[0] == num1[index1])
  775.             qtest = 9;
  776.         else
  777.             {
  778.             temp1 = num1[index1] - '0';
  779.             temp3 = num2[0] - '0';
  780.             if ((index1+1) < len1)
  781.             temp2 = num1[index1+1] - '0';
  782.             else
  783.             temp2 = 0;
  784.             qtest = (10*temp1 + temp2) / temp3;
  785.             }
  786.         temp2 = num1[index1] - '0';
  787.         temp4 = num2[0] - '0';
  788.         if (len2 >= 2)
  789.             temp1 = num2[1] - '0';
  790.         else
  791.             temp1 = 0;
  792.         if ((index1+1) < len1)
  793.             {
  794.             temp3 = num1[index1+1] - '0';
  795.             if ((index1+2) < len1)
  796.             temp5 = num1[index1+2] - '0';
  797.             else
  798.             temp5 = 0;
  799.             }
  800.         else
  801.             {
  802.             temp3 = 0;
  803.             temp5 = 0;
  804.             }
  805.         while (qtest*temp1 > (10*(10*temp2 + temp3
  806.                     - qtest*temp4) + temp5))
  807.             --qtest;
  808.         index2 = len2 - 1;
  809.         index = index1 + len2;
  810.         flag = 0;
  811.         while (index >= index1)
  812.             {
  813.             if (index2 >= 0)
  814.             {
  815.             temp1 = num2[index2] - '0';
  816.             flag -= qtest*temp1;
  817.             }
  818.             temp1 = num1[index] - '0';
  819.             div = flag + temp1;
  820.             if (div < 0)
  821.             {
  822.             flag = div / 10;
  823.             div %= 10;
  824.             if (div < 0)
  825.                 {
  826.                 div += 10;
  827.                 --flag;
  828.                 }
  829.             }
  830.             else
  831.             flag = 0;
  832.             num1[index] = div + '0';
  833.             --index2;
  834.             --index;
  835.             }
  836.         indexq = lenq - (len1 - len2) + index1;
  837.         if (flag != 0)
  838.             {
  839.             quot[indexq] = qtest - 1 + '0';
  840.             index2 = len2 - 1;
  841.             index = index1 + len2;
  842.             flag = 0;
  843.             while (index >= index1)
  844.             {
  845.             if (index2 >= 0)
  846.                 {
  847.                 temp1 = num2[index2] - '0';
  848.                 flag += temp1;
  849.                 }
  850.             temp1 = num1[index] - '0';
  851.             div = flag + temp1;
  852.             if (div > 9)
  853.                 {
  854.                 div -= 10;
  855.                 flag = 1;
  856.                 }
  857.             else
  858.                 flag = 0;
  859.             num1[index] = div + '0';
  860.             --index2;
  861.             --index;
  862.             }
  863.             }
  864.         else
  865.             quot[indexq] = qtest + '0';
  866.         ++index1;
  867.         }
  868.         index1 = len1 - len2;
  869.         indexr = lenr - len2;
  870.         flag = 0;
  871.         while (index1 < len1)
  872.         {
  873.         temp1 = num1[index1] - '0';
  874.         div = temp1 + 10*flag;
  875.         rem[indexr] = div / scale + '0';
  876.         flag = div % scale;
  877.         ++index1;
  878.         ++indexr;
  879.         }
  880.         index2 = 0;
  881.         flag = 0;
  882.         while (index2 < len2)
  883.         {
  884.         temp1 = num2[index2] - '0';
  885.         div = temp1 + 10*flag;
  886.         num2[index2] = div / scale + '0';
  887.         flag = div % scale;
  888.         ++index2;
  889.         }
  890.         }
  891.     while ((quot[0]=='0') && (lenq>1))
  892.         {
  893.         for (indexq=1; indexq<lenq; ++indexq)
  894.         quot[indexq-1] = quot[indexq];
  895.         --lenq;
  896.         }
  897.     while ((rem[0]=='0') && (lenr>1))
  898.         {
  899.         for (indexr=1; indexr<lenr; ++indexr)
  900.         rem[indexr-1] = rem[indexr];
  901.         --lenr;
  902.         }
  903.     quot[lenq] = '\0';
  904.     rem[lenr] = '\0';
  905.     }
  906.     else
  907.     {
  908.     quot[0] = '\0';
  909.     rem[0] = '\0';
  910.     return 0;
  911.     }
  912.     return (lenq+lenr) * (lenq>0) * (lenr>0);
  913.     }
  914.  
  915. /*    parse() returns 0 on error.
  916.  *    input:    str[] a string of digits with optional decimal point
  917.  *          and leading sign.
  918.  *    output:     num[] is a string containing the significant digits
  919.  *          of str[], and digl/digr is the number of digits to the
  920.  *        left/right of the decimal point.
  921.  */
  922. parse(str, num, sign, digl, digr)
  923.     char str[], num[];
  924.     int *sign, *digl, *digr;
  925.     {
  926.     char c;
  927.     int dflag, istr, inum, len;
  928.  
  929.     dflag = 0;
  930.     inum = 0;
  931.     *digl = 0;
  932.     *digr = 0;
  933.     c = str[0];
  934.     if (c=='+')
  935.     *sign = 1;
  936.     else if (c=='-')
  937.     *sign = -1;
  938.     else if (c=='.')
  939.     {
  940.     *sign = 1;
  941.     dflag = 1;
  942.     }
  943.     else if ((c>='0') && (c<='9'))
  944.     {
  945.     *sign = 1;
  946.     if (c != '0')
  947.         {
  948.         *digl = 1;
  949.         num[0] = c;
  950.         ++inum;
  951.         }
  952.     }
  953.     else
  954.     return (0);
  955.     istr = 1;
  956.     while ((c=str[istr++]) != '\0')
  957.     {
  958.     if ((c=='.') && (dflag==0))
  959.         dflag = 1;
  960.     else if ((c>='0') && (c<='9'))
  961.         {
  962.         if ((c!='0') || (*digl>0) || (dflag==1))
  963.         {
  964.         if (dflag==0)
  965.             ++(*digl);
  966.         else
  967.             ++(*digr);
  968.         num[inum] = c;
  969.         ++inum;
  970.         }
  971.         }
  972.     else
  973.         return (0);
  974.     }
  975.     --inum;
  976.       while ((num[inum]=='0') && (inum>= *digl))
  977.     {
  978.     --(*digr);
  979.     --inum;
  980.     }
  981.     num[++inum] = '\0';
  982.     len = inum;
  983.     while ((num[0]=='0') && (len>1))
  984.     {
  985.     for (inum=1; inum<len; ++inum)
  986.         num[inum-1] = num[inum];
  987.     --len;
  988.     if (*digl>0)
  989.         --(*digl);
  990.     }
  991.     num[len] = '\0';
  992.     return (1);
  993.     }
  994.  
  995. /*    fix()
  996.  *    inserts sign and decimal point in digit string num[]
  997.  */
  998. fix(num, len, sign, digr)
  999.     char num[];
  1000.     int len, sign, digr;
  1001.     {
  1002.     int inum;
  1003.     char nnum[N+3];
  1004.  
  1005.     if (digr >= 0)
  1006.     {
  1007.     if (len >= digr)
  1008.         {
  1009.         for (inum=len; inum>len-digr; --inum)
  1010.         num[inum] = num[inum-1];
  1011.         num[inum] = '.';
  1012.         ++len;
  1013.         num[len] = '\0';
  1014.         }
  1015.     else
  1016.         {
  1017.         nnum[0] = '.';
  1018.         for (inum=1; inum<=digr; ++inum)
  1019.         {
  1020.         if (inum<=digr-len)
  1021.             nnum[inum] = '0';
  1022.         else
  1023.             nnum[inum] = num[inum-digr+len-1];
  1024.         }
  1025.         nnum[inum] = '\0';
  1026.         strcpy(num, nnum);
  1027.         len = digr+1;
  1028.         }
  1029.     }
  1030.     else
  1031.     {
  1032.     len -= digr - 1;
  1033.     pad(num, -digr);
  1034.     num[len-1] = '.';
  1035.     num[len] = '\0';
  1036.  
  1037.     }
  1038.     if (sign==-1)
  1039.     {
  1040.     for (inum=len; inum>0; --inum)
  1041.         num[inum] = num[inum-1];
  1042.     num[0] = '-';
  1043.     ++len;
  1044.     num[len] = '\0';
  1045.     }
  1046.  
  1047.     }
  1048.  
  1049. /*     pad()
  1050.  *  input:    num[] a string .
  1051.  *          dig a number of '0's to be appended to num[].
  1052.  *    output: num[] with dig '0's appended.
  1053.  */
  1054.  pad(num, dig)
  1055.      char num[];
  1056.      int dig;
  1057.      {
  1058.      int inum, len;
  1059.  
  1060.     len = strlen(num);
  1061.     for (inum=len; inum < len+dig; ++inum)
  1062.     num[inum] = '0';
  1063.     num[inum] = '\0';
  1064.     }
  1065.  
  1066. /*------------------end of file----------------------*/
  1067.  
  1068.