dumbmp.c
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:16k
源码类别:

数学计算

开发平台:

Unix_Linux

  1. /* dumbmp mini GMP compatible library.
  2. Copyright 2001, 2002, 2004 Free Software Foundation, Inc.
  3. This file is part of the GNU MP Library.
  4. The GNU MP Library is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU Lesser General Public License as published by
  6. the Free Software Foundation; either version 3 of the License, or (at your
  7. option) any later version.
  8. The GNU MP Library is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  11. License for more details.
  12. You should have received a copy of the GNU Lesser General Public License
  13. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  14. /* The code here implements a subset (a very limited subset) of the main GMP
  15.    functions.  It's designed for use in a few build-time calculations and
  16.    will be slow, but highly portable.
  17.    None of the normal GMP configure things are used, nor any of the normal
  18.    gmp.h or gmp-impl.h.  To use this file in a program just #include
  19.    "dumbmp.c".
  20.    ANSI function definitions can be used here, since ansi2knr is run if
  21.    necessary.  But other ANSI-isms like "const" should be avoided.
  22.    mp_limb_t here is an unsigned long, since that's a sensible type
  23.    everywhere we know of, with 8*sizeof(unsigned long) giving the number of
  24.    bits in the type (that not being true for instance with int or short on
  25.    Cray vector systems.)
  26.    Only the low half of each mp_limb_t is used, so as to make carry handling
  27.    and limb multiplies easy.  GMP_LIMB_BITS is the number of bits used.  */
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #include <string.h>
  31. typedef unsigned long mp_limb_t;
  32. typedef struct {
  33.   int        _mp_alloc;
  34.   int        _mp_size;
  35.   mp_limb_t *_mp_d;
  36. } mpz_t[1];
  37. #define GMP_LIMB_BITS  (sizeof (mp_limb_t) * 8 / 2)
  38. #define ABS(x)   ((x) >= 0 ? (x) : -(x))
  39. #define MIN(l,o) ((l) < (o) ? (l) : (o))
  40. #define MAX(h,i) ((h) > (i) ? (h) : (i))
  41. #define ALLOC(x) ((x)->_mp_alloc)
  42. #define PTR(x)   ((x)->_mp_d)
  43. #define SIZ(x)   ((x)->_mp_size)
  44. #define ABSIZ(x) ABS (SIZ (x))
  45. #define LOMASK   ((1L << GMP_LIMB_BITS) - 1)
  46. #define LO(x)    ((x) & LOMASK)
  47. #define HI(x)    ((x) >> GMP_LIMB_BITS)
  48. #define ASSERT(cond)                                    
  49.   do {                                                  
  50.     if (! (cond))                                       
  51.       {                                                 
  52.         fprintf (stderr, "Assertion failuren");        
  53.         abort ();                                       
  54.       }                                                 
  55.   } while (0)
  56. char *
  57. xmalloc (int n)
  58. {
  59.   char  *p;
  60.   p = malloc (n);
  61.   if (p == NULL)
  62.     {
  63.       fprintf (stderr, "Out of memory (alloc %d bytes)n", n);
  64.       abort ();
  65.     }
  66.   return p;
  67. }
  68. mp_limb_t *
  69. xmalloc_limbs (int n)
  70. {
  71.   return (mp_limb_t *) xmalloc (n * sizeof (mp_limb_t));
  72. }
  73. void
  74. mem_copyi (char *dst, char *src, int size)
  75. {
  76.   int  i;
  77.   for (i = 0; i < size; i++)
  78.     dst[i] = src[i];
  79. }
  80. static int
  81. isprime (unsigned long int t)
  82. {
  83.   unsigned long int q, r, d;
  84.   if (t < 32)
  85.     return (0xa08a28acUL >> t) & 1;
  86.   if ((t & 1) == 0)
  87.     return 0;
  88.   if (t % 3 == 0)
  89.     return 0;
  90.   if (t % 5 == 0)
  91.     return 0;
  92.   if (t % 7 == 0)
  93.     return 0;
  94.   for (d = 11;;)
  95.     {
  96.       q = t / d;
  97.       r = t - q * d;
  98.       if (q < d)
  99. return 1;
  100.       if (r == 0)
  101. break;
  102.       d += 2;
  103.       q = t / d;
  104.       r = t - q * d;
  105.       if (q < d)
  106. return 1;
  107.       if (r == 0)
  108. break;
  109.       d += 4;
  110.     }
  111.   return 0;
  112. }
  113. int
  114. log2_ceil (int n)
  115. {
  116.   int  e;
  117.   ASSERT (n >= 1);
  118.   for (e = 0; ; e++)
  119.     if ((1 << e) >= n)
  120.       break;
  121.   return e;
  122. }
  123. void
  124. mpz_realloc (mpz_t r, int n)
  125. {
  126.   if (n <= ALLOC(r))
  127.     return;
  128.   ALLOC(r) = n;
  129.   PTR(r) = (mp_limb_t *) realloc (PTR(r), n * sizeof (mp_limb_t));
  130.   if (PTR(r) == NULL)
  131.     {
  132.       fprintf (stderr, "Out of memory (realloc to %d)n", n);
  133.       abort ();
  134.     }
  135. }
  136. void
  137. mpn_normalize (mp_limb_t *rp, int *rnp)
  138. {
  139.   int  rn = *rnp;
  140.   while (rn > 0 && rp[rn-1] == 0)
  141.     rn--;
  142.   *rnp = rn;
  143. }
  144. void
  145. mpn_copyi (mp_limb_t *dst, mp_limb_t *src, int n)
  146. {
  147.   int  i;
  148.   for (i = 0; i < n; i++)
  149.     dst[i] = src[i];
  150. }
  151. void
  152. mpn_zero (mp_limb_t *rp, int rn)
  153. {
  154.   int  i;
  155.   for (i = 0; i < rn; i++)
  156.     rp[i] = 0;
  157. }
  158. void
  159. mpz_init (mpz_t r)
  160. {
  161.   ALLOC(r) = 1;
  162.   PTR(r) = xmalloc_limbs (ALLOC(r));
  163.   PTR(r)[0] = 0;
  164.   SIZ(r) = 0;
  165. }
  166. void
  167. mpz_clear (mpz_t r)
  168. {
  169.   free (PTR (r));
  170.   ALLOC(r) = -1;
  171.   SIZ (r) = 0xbadcafeL;
  172.   PTR (r) = (mp_limb_t *) 0xdeadbeefL;
  173. }
  174. int
  175. mpz_sgn (mpz_t a)
  176. {
  177.   return (SIZ(a) > 0 ? 1 : SIZ(a) == 0 ? 0 : -1);
  178. }
  179. int
  180. mpz_odd_p (mpz_t a)
  181. {
  182.   if (SIZ(a) == 0)
  183.     return 0;
  184.   else
  185.     return (PTR(a)[0] & 1) != 0;
  186. }
  187. int
  188. mpz_even_p (mpz_t a)
  189. {
  190.   if (SIZ(a) == 0)
  191.     return 1;
  192.   else
  193.     return (PTR(a)[0] & 1) == 0;
  194. }
  195. size_t
  196. mpz_sizeinbase (mpz_t a, int base)
  197. {
  198.   int an = ABSIZ (a);
  199.   mp_limb_t *ap = PTR (a);
  200.   int cnt;
  201.   mp_limb_t hi;
  202.   if (base != 2)
  203.     abort ();
  204.   if (an == 0)
  205.     return 1;
  206.   cnt = 0;
  207.   for (hi = ap[an - 1]; hi != 0; hi >>= 1)
  208.     cnt += 1;
  209.   return (an - 1) * GMP_LIMB_BITS + cnt;
  210. }
  211. void
  212. mpz_set (mpz_t r, mpz_t a)
  213. {
  214.   mpz_realloc (r, ABSIZ (a));
  215.   SIZ(r) = SIZ(a);
  216.   mpn_copyi (PTR(r), PTR(a), ABSIZ (a));
  217. }
  218. void
  219. mpz_init_set (mpz_t r, mpz_t a)
  220. {
  221.   mpz_init (r);
  222.   mpz_set (r, a);
  223. }
  224. void
  225. mpz_set_ui (mpz_t r, unsigned long ui)
  226. {
  227.   int  rn;
  228.   mpz_realloc (r, 2);
  229.   PTR(r)[0] = LO(ui);
  230.   PTR(r)[1] = HI(ui);
  231.   rn = 2;
  232.   mpn_normalize (PTR(r), &rn);
  233.   SIZ(r) = rn;
  234. }
  235. void
  236. mpz_init_set_ui (mpz_t r, unsigned long ui)
  237. {
  238.   mpz_init (r);
  239.   mpz_set_ui (r, ui);
  240. }
  241. void
  242. mpz_setbit (mpz_t r, unsigned long bit)
  243. {
  244.   int        limb, rn, extend;
  245.   mp_limb_t  *rp;
  246.   rn = SIZ(r);
  247.   if (rn < 0)
  248.     abort ();  /* only r>=0 */
  249.   limb = bit / GMP_LIMB_BITS;
  250.   bit %= GMP_LIMB_BITS;
  251.   mpz_realloc (r, limb+1);
  252.   rp = PTR(r);
  253.   extend = (limb+1) - rn;
  254.   if (extend > 0)
  255.     mpn_zero (rp + rn, extend);
  256.   rp[limb] |= (mp_limb_t) 1 << bit;
  257.   SIZ(r) = MAX (rn, limb+1);
  258. }
  259. int
  260. mpz_tstbit (mpz_t r, unsigned long bit)
  261. {
  262.   int  limb;
  263.   if (SIZ(r) < 0)
  264.     abort ();  /* only r>=0 */
  265.   limb = bit / GMP_LIMB_BITS;
  266.   if (SIZ(r) <= limb)
  267.     return 0;
  268.   bit %= GMP_LIMB_BITS;
  269.   return (PTR(r)[limb] >> bit) & 1;
  270. }
  271. int
  272. popc_limb (mp_limb_t a)
  273. {
  274.   int  ret = 0;
  275.   while (a != 0)
  276.     {
  277.       ret += (a & 1);
  278.       a >>= 1;
  279.     }
  280.   return ret;
  281. }
  282. unsigned long
  283. mpz_popcount (mpz_t a)
  284. {
  285.   unsigned long  ret;
  286.   int            i;
  287.   if (SIZ(a) < 0)
  288.     abort ();
  289.   ret = 0;
  290.   for (i = 0; i < SIZ(a); i++)
  291.     ret += popc_limb (PTR(a)[i]);
  292.   return ret;
  293. }
  294. void
  295. mpz_add (mpz_t r, mpz_t a, mpz_t b)
  296. {
  297.   int an = ABSIZ (a), bn = ABSIZ (b), rn;
  298.   mp_limb_t *rp, *ap, *bp;
  299.   int i;
  300.   mp_limb_t t, cy;
  301.   if ((SIZ (a) ^ SIZ (b)) < 0)
  302.     abort (); /* really subtraction */
  303.   if (SIZ (a) < 0)
  304.     abort ();
  305.   mpz_realloc (r, MAX (an, bn) + 1);
  306.   ap = PTR (a);  bp = PTR (b);  rp = PTR (r);
  307.   if (an < bn)
  308.     {
  309.       mp_limb_t *tp;  int tn;
  310.       tn = an; an = bn; bn = tn;
  311.       tp = ap; ap = bp; bp = tp;
  312.     }
  313.   cy = 0;
  314.   for (i = 0; i < bn; i++)
  315.     {
  316.       t = ap[i] + bp[i] + cy;
  317.       rp[i] = LO (t);
  318.       cy = HI (t);
  319.     }
  320.   for (i = bn; i < an; i++)
  321.     {
  322.       t = ap[i] + cy;
  323.       rp[i] = LO (t);
  324.       cy = HI (t);
  325.     }
  326.   rp[an] = cy;
  327.   rn = an + 1;
  328.   mpn_normalize (rp, &rn);
  329.   SIZ (r) = rn;
  330. }
  331. void
  332. mpz_add_ui (mpz_t r, mpz_t a, unsigned long int ui)
  333. {
  334.   mpz_t b;
  335.   mpz_init (b);
  336.   mpz_set_ui (b, ui);
  337.   mpz_add (r, a, b);
  338.   mpz_clear (b);
  339. }
  340. void
  341. mpz_sub (mpz_t r, mpz_t a, mpz_t b)
  342. {
  343.   int an = ABSIZ (a), bn = ABSIZ (b), rn;
  344.   mp_limb_t *rp, *ap, *bp;
  345.   int i;
  346.   mp_limb_t t, cy;
  347.   if ((SIZ (a) ^ SIZ (b)) < 0)
  348.     abort (); /* really addition */
  349.   if (SIZ (a) < 0)
  350.     abort ();
  351.   mpz_realloc (r, MAX (an, bn) + 1);
  352.   ap = PTR (a);  bp = PTR (b);  rp = PTR (r);
  353.   if (an < bn)
  354.     {
  355.       mp_limb_t *tp;  int tn;
  356.       tn = an; an = bn; bn = tn;
  357.       tp = ap; ap = bp; bp = tp;
  358.     }
  359.   cy = 0;
  360.   for (i = 0; i < bn; i++)
  361.     {
  362.       t = ap[i] - bp[i] - cy;
  363.       rp[i] = LO (t);
  364.       cy = LO (-HI (t));
  365.     }
  366.   for (i = bn; i < an; i++)
  367.     {
  368.       t = ap[i] - cy;
  369.       rp[i] = LO (t);
  370.       cy = LO (-HI (t));
  371.     }
  372.   rp[an] = cy;
  373.   rn = an + 1;
  374.   if (cy != 0)
  375.     {
  376.       cy = 0;
  377.       for (i = 0; i < rn; i++)
  378. {
  379.   t = -rp[i] - cy;
  380.   rp[i] = LO (t);
  381.   cy = LO (-HI (t));
  382. }
  383.       SIZ (r) = -rn;
  384.       return;
  385.     }
  386.   mpn_normalize (rp, &rn);
  387.   SIZ (r) = rn;
  388. }
  389. void
  390. mpz_sub_ui (mpz_t r, mpz_t a, unsigned long int ui)
  391. {
  392.   mpz_t b;
  393.   mpz_init (b);
  394.   mpz_set_ui (b, ui);
  395.   mpz_sub (r, a, b);
  396.   mpz_clear (b);
  397. }
  398. void
  399. mpz_mul (mpz_t r, mpz_t a, mpz_t b)
  400. {
  401.   int an = ABSIZ (a), bn = ABSIZ (b), rn;
  402.   mp_limb_t *scratch, *tmp, *ap = PTR (a), *bp = PTR (b);
  403.   int ai, bi;
  404.   mp_limb_t t, cy;
  405.   scratch = xmalloc_limbs (an + bn);
  406.   tmp = scratch;
  407.   for (bi = 0; bi < bn; bi++)
  408.     tmp[bi] = 0;
  409.   for (ai = 0; ai < an; ai++)
  410.     {
  411.       tmp = scratch + ai;
  412.       cy = 0;
  413.       for (bi = 0; bi < bn; bi++)
  414. {
  415.   t = ap[ai] * bp[bi] + tmp[bi] + cy;
  416.   tmp[bi] = LO (t);
  417.   cy = HI (t);
  418. }
  419.       tmp[bn] = cy;
  420.     }
  421.   rn = an + bn;
  422.   mpn_normalize (scratch, &rn);
  423.   free (PTR (r));
  424.   PTR (r) = scratch;
  425.   SIZ (r) = (SIZ (a) ^ SIZ (b)) >= 0 ? rn : -rn;
  426.   ALLOC (r) = an + bn;
  427. }
  428. void
  429. mpz_mul_ui (mpz_t r, mpz_t a, unsigned long int ui)
  430. {
  431.   mpz_t b;
  432.   mpz_init (b);
  433.   mpz_set_ui (b, ui);
  434.   mpz_mul (r, a, b);
  435.   mpz_clear (b);
  436. }
  437. void
  438. mpz_mul_2exp (mpz_t r, mpz_t a, unsigned long int bcnt)
  439. {
  440.   mpz_set (r, a);
  441.   while (bcnt)
  442.     {
  443.       mpz_add (r, r, r);
  444.       bcnt -= 1;
  445.     }
  446. }
  447. void
  448. mpz_ui_pow_ui (mpz_t r, unsigned long b, unsigned long e)
  449. {
  450.   unsigned long  i;
  451.   mpz_t          bz;
  452.   mpz_init (bz);
  453.   mpz_set_ui (bz, b);
  454.   mpz_set_ui (r, 1L);
  455.   for (i = 0; i < e; i++)
  456.     mpz_mul (r, r, bz);
  457.   mpz_clear (bz);
  458. }
  459. void
  460. mpz_tdiv_q_2exp (mpz_t r, mpz_t a, unsigned long int bcnt)
  461. {
  462.   int as, rn;
  463.   int cnt, tnc;
  464.   int lcnt;
  465.   mp_limb_t high_limb, low_limb;
  466.   int i;
  467.   as = SIZ (a);
  468.   lcnt = bcnt / GMP_LIMB_BITS;
  469.   rn = ABS (as) - lcnt;
  470.   if (rn <= 0)
  471.     SIZ (r) = 0;
  472.   else
  473.     {
  474.       mp_limb_t *rp, *ap;
  475.       mpz_realloc (r, rn);
  476.       rp = PTR (r);
  477.       ap = PTR (a);
  478.       cnt = bcnt % GMP_LIMB_BITS;
  479.       if (cnt != 0)
  480.         {
  481.   ap += lcnt;
  482.   tnc = GMP_LIMB_BITS - cnt;
  483.   high_limb = *ap++;
  484.   low_limb = high_limb >> cnt;
  485.   for (i = rn - 1; i != 0; i--)
  486.     {
  487.       high_limb = *ap++;
  488.       *rp++ = low_limb | LO (high_limb << tnc);
  489.       low_limb = high_limb >> cnt;
  490.     }
  491.   *rp = low_limb;
  492.           rn -= low_limb == 0;
  493.         }
  494.       else
  495.         {
  496.   ap += lcnt;
  497.           mpn_copyi (rp, ap, rn);
  498.         }
  499.       SIZ (r) = as >= 0 ? rn : -rn;
  500.     }
  501. }
  502. void
  503. mpz_tdiv_r_2exp (mpz_t r, mpz_t a, unsigned long int bcnt)
  504. {
  505.   int    rn, bwhole;
  506.   mpz_set (r, a);
  507.   rn = ABSIZ(r);
  508.   bwhole = bcnt / GMP_LIMB_BITS;
  509.   bcnt %= GMP_LIMB_BITS;
  510.   if (rn > bwhole)
  511.     {
  512.       rn = bwhole+1;
  513.       PTR(r)[rn-1] &= ((mp_limb_t) 1 << bcnt) - 1;
  514.       mpn_normalize (PTR(r), &rn);
  515.       SIZ(r) = (SIZ(r) >= 0 ? rn : -rn);
  516.     }
  517. }
  518. int
  519. mpz_cmp (mpz_t a, mpz_t b)
  520. {
  521.   mp_limb_t *ap, *bp, al, bl;
  522.   int as = SIZ (a), bs = SIZ (b);
  523.   int i;
  524.   int sign;
  525.   if (as != bs)
  526.     return as > bs ? 1 : -1;
  527.   sign = as > 0 ? 1 : -1;
  528.   ap = PTR (a);
  529.   bp = PTR (b);
  530.   for (i = ABS (as) - 1; i >= 0; i--)
  531.     {
  532.       al = ap[i];
  533.       bl = bp[i];
  534.       if (al != bl)
  535. return al > bl ? sign : -sign;
  536.     }
  537.   return 0;
  538. }
  539. int
  540. mpz_cmp_ui (mpz_t a, unsigned long b)
  541. {
  542.   mpz_t  bz;
  543.   int    ret;
  544.   mpz_init_set_ui (bz, b);
  545.   ret = mpz_cmp (a, bz);
  546.   mpz_clear (bz);
  547.   return ret;
  548. }
  549. void
  550. mpz_tdiv_qr (mpz_t q, mpz_t r, mpz_t a, mpz_t b)
  551. {
  552.   mpz_t          tmpr, tmpb;
  553.   unsigned long  cnt;
  554.   ASSERT (mpz_sgn(a) >= 0);
  555.   ASSERT (mpz_sgn(b) > 0);
  556.   mpz_init_set (tmpr, a);
  557.   mpz_init_set (tmpb, b);
  558.   mpz_set_ui (q, 0L);
  559.   if (mpz_cmp (tmpr, tmpb) > 0)
  560.     {
  561.       cnt = mpz_sizeinbase (tmpr, 2) - mpz_sizeinbase (tmpb, 2) + 1;
  562.       mpz_mul_2exp (tmpb, tmpb, cnt);
  563.       for ( ; cnt > 0; cnt--)
  564.         {
  565.           mpz_mul_2exp (q, q, 1);
  566.           mpz_tdiv_q_2exp (tmpb, tmpb, 1L);
  567.           if (mpz_cmp (tmpr, tmpb) >= 0)
  568.             {
  569.               mpz_sub (tmpr, tmpr, tmpb);
  570.               mpz_add_ui (q, q, 1L);
  571.               ASSERT (mpz_cmp (tmpr, tmpb) < 0);
  572.             }
  573.         }
  574.     }
  575.   mpz_set (r, tmpr);
  576.   mpz_clear (tmpr);
  577.   mpz_clear (tmpb);
  578. }
  579. void
  580. mpz_tdiv_qr_ui (mpz_t q, mpz_t r, mpz_t a, unsigned long b)
  581. {
  582.   mpz_t  bz;
  583.   mpz_init_set_ui (bz, b);
  584.   mpz_tdiv_qr (q, r, a, bz);
  585.   mpz_clear (bz);
  586. }
  587. void
  588. mpz_tdiv_q (mpz_t q, mpz_t a, mpz_t b)
  589. {
  590.   mpz_t  r;
  591.   mpz_init (r);
  592.   mpz_tdiv_qr (q, r, a, b);
  593.   mpz_clear (r);
  594. }
  595. void
  596. mpz_tdiv_r (mpz_t r, mpz_t a, mpz_t b)
  597. {
  598.   mpz_t  q;
  599.   mpz_init (q);
  600.   mpz_tdiv_qr (q, r, a, b);
  601.   mpz_clear (q);
  602. }
  603. void
  604. mpz_tdiv_q_ui (mpz_t q, mpz_t n, unsigned long d)
  605. {
  606.   mpz_t  dz;
  607.   mpz_init_set_ui (dz, d);
  608.   mpz_tdiv_q (q, n, dz);
  609.   mpz_clear (dz);
  610. }
  611. /* Set inv to the inverse of d, in the style of invert_limb, ie. for
  612.    udiv_qrnnd_preinv.  */
  613. void
  614. mpz_preinv_invert (mpz_t inv, mpz_t d, int numb_bits)
  615. {
  616.   mpz_t  t;
  617.   int    norm;
  618.   ASSERT (SIZ(d) > 0);
  619.   norm = numb_bits - mpz_sizeinbase (d, 2);
  620.   ASSERT (norm >= 0);
  621.   mpz_init_set_ui (t, 1L);
  622.   mpz_mul_2exp (t, t, 2*numb_bits - norm);
  623.   mpz_tdiv_q (inv, t, d);
  624.   mpz_set_ui (t, 1L);
  625.   mpz_mul_2exp (t, t, numb_bits);
  626.   mpz_sub (inv, inv, t);
  627.   mpz_clear (t);
  628. }
  629. /* Remove leading '0' characters from the start of a string, by copying the
  630.    remainder down. */
  631. void
  632. strstrip_leading_zeros (char *s)
  633. {
  634.   char  c, *p;
  635.   p = s;
  636.   while (*s == '0')
  637.     s++;
  638.   do
  639.     {
  640.       c = *s++;
  641.       *p++ = c;
  642.     }
  643.   while (c != '');
  644. }
  645. char *
  646. mpz_get_str (char *buf, int base, mpz_t a)
  647. {
  648.   static char  tohex[] = "0123456789abcdef";
  649.   mp_limb_t  alimb, *ap;
  650.   int        an, bn, i, j;
  651.   char       *bp;
  652.   if (base != 16)
  653.     abort ();
  654.   if (SIZ (a) < 0)
  655.     abort ();
  656.   if (buf == 0)
  657.     buf = xmalloc (ABSIZ (a) * (GMP_LIMB_BITS / 4) + 3);
  658.   an = ABSIZ (a);
  659.   if (an == 0)
  660.     {
  661.       buf[0] = '0';
  662.       buf[1] = '';
  663.       return buf;
  664.     }
  665.   ap = PTR (a);
  666.   bn = an * (GMP_LIMB_BITS / 4);
  667.   bp = buf + bn;
  668.   for (i = 0; i < an; i++)
  669.     {
  670.       alimb = ap[i];
  671.       for (j = 0; j < GMP_LIMB_BITS / 4; j++)
  672.         {
  673.           bp--;
  674.           *bp = tohex [alimb & 0xF];
  675.           alimb >>= 4;
  676.         }
  677.       ASSERT (alimb == 0);
  678.     }
  679.   ASSERT (bp == buf);
  680.   buf[bn] = '';
  681.   strstrip_leading_zeros (buf);
  682.   return buf;
  683. }
  684. void
  685. mpz_out_str (FILE *file, int base, mpz_t a)
  686. {
  687.   char *str;
  688.   if (file == 0)
  689.     file = stdout;
  690.   str = mpz_get_str (0, 16, a);
  691.   fputs (str, file);
  692.   free (str);
  693. }
  694. /* Calculate r satisfying r*d == 1 mod 2^n. */
  695. void
  696. mpz_invert_2exp (mpz_t r, mpz_t a, unsigned long n)
  697. {
  698.   unsigned long  i;
  699.   mpz_t  inv, prod;
  700.   ASSERT (mpz_odd_p (a));
  701.   mpz_init_set_ui (inv, 1L);
  702.   mpz_init (prod);
  703.   for (i = 1; i < n; i++)
  704.     {
  705.       mpz_mul (prod, inv, a);
  706.       if (mpz_tstbit (prod, i) != 0)
  707.         mpz_setbit (inv, i);
  708.     }
  709.   mpz_mul (prod, inv, a);
  710.   mpz_tdiv_r_2exp (prod, prod, n);
  711.   ASSERT (mpz_cmp_ui (prod, 1L) == 0);
  712.   mpz_set (r, inv);
  713.   mpz_clear (inv);
  714.   mpz_clear (prod);
  715. }
  716. /* Calculate inv satisfying r*a == 1 mod 2^n. */
  717. void
  718. mpz_invert_ui_2exp (mpz_t r, unsigned long a, unsigned long n)
  719. {
  720.   mpz_t  az;
  721.   mpz_init_set_ui (az, a);
  722.   mpz_invert_2exp (r, az, n);
  723.   mpz_clear (az);
  724. }
  725. /* x=y^z */
  726. void
  727. mpz_pow_ui (mpz_t x, mpz_t y, unsigned long z)
  728. {
  729.   mpz_t t;
  730.   mpz_init_set_ui (t, 1);
  731.   for (; z != 0; z--)
  732.     mpz_mul (t, t, y);
  733.   mpz_set (x, t);
  734.   mpz_clear (t);
  735. }
  736. /* x=x+y*z */
  737. void
  738. mpz_addmul_ui (mpz_t x, mpz_t y, unsigned long z)
  739. {
  740.   mpz_t t;
  741.   mpz_init (t);
  742.   mpz_mul_ui (t, y, z);
  743.   mpz_add (x, x, t);
  744.   mpz_clear (t);
  745. }
  746. /* x=floor(y^(1/z)) */
  747. void
  748. mpz_root (mpz_t x, mpz_t y, unsigned long z)
  749. {
  750.   mpz_t t, u;
  751.   if (mpz_sgn (y) < 0)
  752.     {
  753.       fprintf (stderr, "mpz_root does not accept negative valuesn");
  754.       abort ();
  755.     }
  756.   if (mpz_cmp_ui (y, 1) <= 0)
  757.     {
  758.       mpz_set (x, y);
  759.       return;
  760.     }
  761.   mpz_init (t);
  762.   mpz_init_set (u, y);
  763.   do
  764.     {
  765.       mpz_pow_ui (t, u, z - 1);
  766.       mpz_tdiv_q (t, y, t);
  767.       mpz_addmul_ui (t, u, z - 1);
  768.       mpz_tdiv_q_ui (t, t, z);
  769.       if (mpz_cmp (t, u) >= 0)
  770. break;
  771.       mpz_set (u, t);
  772.     }
  773.   while (1);
  774.   mpz_set (x, u);
  775.   mpz_clear (t);
  776.   mpz_clear (u);
  777. }