прикреплённый файл:longint.c к странице LecturesVMSH/C/2011-04-26

   1 #include <stdio.h>
   2 
   3 #define N 1000
   4 
   5 char x[N];
   6 char y[N];
   7 char z[N];
   8 
   9 int lx, ly, lz;
  10 
  11 int input(char *x) // returns length of number (significant digits)
  12 {
  13     int i = N-1;
  14     int l;
  15     int t;
  16     int c;
  17     int was_not_zero_digit = 0;
  18     c = getchar();
  19     
  20     while((c <= '9') && (c >= '0')){
  21         if( was_not_zero_digit || (c != '0')) {
  22           was_not_zero_digit = 1;   
  23           x[i] = c-'0'; /* digit 0..9 from a digit character */
  24           i--;
  25         }
  26         c = getchar();
  27     }
  28     l = N-1-i; /* length of a number, to return */
  29     
  30     while(i>0) { /* fill up insignificant zeroes */
  31       x[i] = 0;
  32       i--;
  33      } 
  34      
  35      for( i=0; i<=(l-1)/2; i++ )
  36      {
  37        t = x[N-l+i]; 
  38        x[N-l+i] = x[N-1-i];
  39        x[N-1-i] = t;
  40      }
  41   return l;
  42 }
  43 
  44 void output( char *x, int l)
  45 {
  46     int i;
  47     for( i = N-l; i<=N-1; i++ )
  48       printf( "%d", x[i] );
  49     printf("\n" );
  50 }
  51 
  52 int compare( char *x1, int l1, char *x2, int l2)
  53 {
  54     int i; 
  55     if( l1 < l2 )
  56       return -1;
  57     else if ( l1 > l2 )
  58       return 1; 
  59     else { /* l1 == l2 */
  60       i = N-l1; /* first significant digit of both values */
  61       while( (i <= N-1) && (x1[i] == x2[i]) )
  62         i++;
  63       if (i <= N-1) /* there were some different digits */
  64         if (x1[i] < x2[i])
  65           return -1;
  66         else /*x1[i] > x2[i] */
  67           return 1;
  68       else
  69         return 0;
  70     }
  71 }
  72 
  73 int add (char *x1, int lx1, char *x2, int lx2, char *z)
  74 {
  75     int maxl;
  76     int i; 
  77     int c, d;
  78     
  79     if (lx1 > lx2)
  80       maxl = lx1;
  81     else 
  82       maxl = lx2;
  83       
  84     i = N-1;
  85     c = 0;
  86     while( i > N-maxl-2 )
  87     {
  88         d = x1[i] + x2[i] + c;
  89         c = d / 10; /* carry */
  90         d = d % 10; /* result digit */
  91         z[i] = d;
  92         i--;
  93     }
  94     
  95     if (z[i+1] != 0) /* last carry, which could increase length */
  96       return maxl+1; 
  97     else
  98       return maxl;
  99       
 100 }
 101 
 102 int zero (char *x)
 103 {
 104     int i;
 105     for( i = 0; i<N; i++)
 106       x[i] = 0;
 107     return 0;
 108 }
 109 
 110 int one(char *x)
 111 {
 112     zero(x);
 113     x[N-1] = 1;
 114     return 1;
 115 }
 116 
 117 int dumb_multiply( char *x1, int lx1, char *x2, int lx2, char *z)
 118 {
 119     int tmp; char *tmpc;
 120     char i[N]; int li;
 121     char one1[N];
 122     
 123     int lz;
 124     
 125     /* ensure that x1 >= x2, optimize additons */
 126     if (compare(x1, lx1, x2, lx2) < 0)
 127     {
 128         tmp = lx1; lx1 = lx2; lx2 = tmp;
 129         tmpc = x1; x1 = x2; x2 = tmpc;
 130     }
 131    
 132     lz = zero(z);
 133     
 134     one(one1);
 135     
 136     /* take and add x1 x2 times */
 137     for( li = zero(i);                 /* i = 0 */
 138          compare(i, li, x2, lx2) < 0;  /* i < x2 */
 139          li = add( i, li, one1, 1, i))      /* i++ */
 140     {
 141          lz = add( z, lz, x1, lx1, z );
 142     }
 143     
 144     return lz;
 145 }
 146 
 147 int power( char *x1, int lx1, char *x2, int lx2, char *z ) /* z = x1 ^ x2 */
 148 { 
 149     char i[N]; int li;
 150     char one1[N];
 151     int lz;
 152     
 153     one(one1);
 154     lz = one(z);  /* z = 1 */
 155     
 156     for( li = zero(i);                 /* i = 0 */
 157          compare(i, li, x2, lx2) < 0;  /* i < x2 */
 158          li = add(i, li, one1, 1, i))  /* i++ */
 159      {
 160          lz = dumb_multiply(z, lz, x1, lx1, z); /* z = z * x1 */
 161      }
 162      
 163      return lz;
 164 }
 165 
 166 int main( int argc, char  **argv )
 167 {
 168     int res; 
 169     
 170     lx = input(x);
 171     ly = input(y);
 172     printf( "x        : %d digits: ", lx);
 173     output(x, lx);
 174     printf( "y        : %d digits: ", ly);
 175     output(y, ly);
 176     
 177     res = compare(x, lx, y, ly);
 178     
 179     if( res > 0 )
 180       printf( "x > y\n" );
 181     else if ( res < 0)
 182       printf( "x < y\n" );
 183     else
 184       printf( "x == y\n" );
 185      
 186     lz = add( x, lx, y, ly, z); /* z = x +y */
 187     printf( "z = x + y: %d digits: ", lz);
 188     output(z, lz);
 189 
 190     lz = dumb_multiply( x, lx, y, ly, z); /* z = x * y */
 191     printf( "z = x * y: %d digits: ", lz);
 192     output(z, lz);
 193 
 194     lz = power( x, lx, y, ly, z); /* z = x ^ y */
 195     printf( "z = x ^ y: %d digits: ", lz);
 196     output(z, lz);
 197 
 198 
 199     return 0;
 200 }