2.9BSD - /usr/src/lib/ape/pow.c

   1: #include "lint.h"
   2: #ifndef lint
   3: static char sccs_id[] = "@(#)pow.c	2.3	7/24/82";
   4: #endif lint
   5: 
   6: #include <ape.h>
   7: pow(a,b,c,d) /* d = a^b mod c; c needed to prevent overflow */
   8: MINT *a,*b,*c,*d;
   9: {   int j,n;
  10:     MINT junk, *z;
  11:     short port; /* Portable short length indicator */
  12: 
  13:     if (b->len < 0)
  14:         {
  15:         xfree(d);
  16:         return;
  17:         }
  18:     else if (b->len == 0)
  19:         {
  20:         xfree(d);
  21:         d->len = 1;
  22:         d->val = xalloc(1,"pow");
  23:         *d->val = 1;
  24:         return;
  25:         }
  26:     junk.len=0;
  27:     z = itom(1);
  28:     for(j=0;j<b->len;j++)   /* Go backwards through each bit
  29: 				 * of each word */
  30:     {
  31:         port = ~0;
  32:         n=b->val[b->len-j-1];
  33:         while ((port <<= 1))
  34:         {   mult(z,z,z); /* Square what we have so far */
  35:             mdiv(z,c,&junk,z);
  36:             if ((n <<= 1) & CARRYBIT) /* Put in another a */
  37:             {   mult(a,z,z);
  38:                 mdiv(z,c,&junk,z);
  39:             }
  40:         }
  41:     }
  42:     xfree(&junk);
  43:     xfree(d);
  44:     d->len = z->len;
  45:     d->val = z->val;
  46:     return;
  47: }
  48: 
  49: 
  50: rpow(a,n,b)
  51: MINT *a,*b; /* b = a^n */
  52: int n;
  53: {
  54:     MINT *z;
  55:     int port = ~0; /* portable wordlength indicator */
  56: 
  57:     if (n < 0)
  58:         {
  59:         xfree(b);
  60:         return;
  61:         }
  62:     else if (n == 0)
  63:         {
  64:         xfree(b);
  65:         b->len = 1;
  66:         b->val = xalloc(1,"rpow");
  67:         *b->val = 1;
  68:         return;
  69:         }
  70:     z = itom(1);
  71:     while ((port <<= 1))
  72:         {
  73:         mult(z,z,z); /* Square what we have so far */
  74:         if ((n <<= 1) < 0) /* Put in another a */
  75:             mult(a,z,z);
  76:         }
  77:     xfree(b);
  78:     b->len = z->len;
  79:     b->val = z->val;
  80:     return;
  81: }
  82: 
  83: lpow(m,n,b)
  84: MINT *b; /* b = m^n */
  85: int m;      /* Specialized hacky version */
  86: long int n;
  87: {
  88:     PMINT mintm;
  89:     long int port = ~0; /* portable longword length indicator */
  90: 
  91:     xfree(b);
  92:     if (n < 0L) return;
  93:     b->len = 1;
  94:     b->val = xalloc(1,"lpow");
  95:     *b->val = 1;
  96:     if (n == 0L) return;
  97:     mintm = itom(m);
  98:     while ((port <<= 1))
  99:         {
 100:         mult(b,b,b); /* Square what we have so far */
 101:         if ((n <<= 1) < 0) /* Put in another m */
 102:             mult(mintm,b,b);
 103:         }
 104:     afree(mintm); /* tidy up */
 105:     return;
 106: }

Defined functions

Defined variables