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

数学计算

开发平台:

Unix_Linux

  1. /* mpf_get_str (digit_ptr, exp, base, n_digits, a) -- Convert the floating
  2.    point number A to a base BASE number and store N_DIGITS raw digits at
  3.    DIGIT_PTR, and the base BASE exponent in the word pointed to by EXP.  For
  4.    example, the number 3.1416 would be returned as "31416" in DIGIT_PTR and
  5.    1 in EXP.
  6. Copyright 1993, 1994, 1995, 1996, 1997, 2000, 2001, 2002, 2003, 2005, 2006 Free
  7. Software Foundation, Inc.
  8. This file is part of the GNU MP Library.
  9. The GNU MP Library is free software; you can redistribute it and/or modify
  10. it under the terms of the GNU Lesser General Public License as published by
  11. the Free Software Foundation; either version 3 of the License, or (at your
  12. option) any later version.
  13. The GNU MP Library is distributed in the hope that it will be useful, but
  14. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  15. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  16. License for more details.
  17. You should have received a copy of the GNU Lesser General Public License
  18. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  19. #include <stdlib.h> /* for NULL */
  20. #include "gmp.h"
  21. #include "gmp-impl.h"
  22. #include "longlong.h" /* for count_leading_zeros */
  23. /* Could use some more work.
  24.    1. Allocation is excessive.  Try to combine areas.  Perhaps use result
  25.       string area for temp limb space?
  26.    2. We generate up to two limbs of extra digits.  This is because we don't
  27.       check the exact number of bits in the input operand, and from that
  28.       compute an accurate exponent (variable e in the code).  It would be
  29.       cleaner and probably somewhat faster to change this.
  30. */
  31. /* Compute base^exp and return the most significant prec limbs in rp[].
  32.    Put the count of omitted low limbs in *ign.
  33.    Return the actual size (which might be less than prec).
  34.    Allocation of rp[] and the temporary tp[] should be 2*prec+2 limbs.  */
  35. static mp_size_t
  36. mpn_pow_1_highpart (mp_ptr rp, mp_size_t *ignp,
  37.     mp_limb_t base, unsigned long exp,
  38.     mp_size_t prec, mp_ptr tp)
  39. {
  40.   mp_size_t ign; /* counts number of ignored low limbs in r */
  41.   mp_size_t off; /* keeps track of offset where value starts */
  42.   mp_ptr passed_rp = rp;
  43.   mp_size_t rn;
  44.   int cnt;
  45.   int i;
  46.   if (exp == 0)
  47.     {
  48.       rp[0] = 1;
  49.       *ignp = 0;
  50.       return 1;
  51.     }
  52.   rp[0] = base;
  53.   rn = 1;
  54.   off = 0;
  55.   ign = 0;
  56.   count_leading_zeros (cnt, exp);
  57.   for (i = GMP_LIMB_BITS - cnt - 2; i >= 0; i--)
  58.     {
  59.       mpn_sqr (tp, rp + off, rn);
  60.       rn = 2 * rn;
  61.       rn -= tp[rn - 1] == 0;
  62.       ign <<= 1;
  63.       off = 0;
  64.       if (rn > prec)
  65. {
  66.   ign += rn - prec;
  67.   off = rn - prec;
  68.   rn = prec;
  69. }
  70.       MP_PTR_SWAP (rp, tp);
  71.       if (((exp >> i) & 1) != 0)
  72. {
  73.   mp_limb_t cy;
  74.   cy = mpn_mul_1 (rp, rp + off, rn, base);
  75.   rp[rn] = cy;
  76.   rn += cy != 0;
  77.   off = 0;
  78. }
  79.     }
  80.   if (rn > prec)
  81.     {
  82.       ASSERT (rn == prec + 1);
  83.       ign += rn - prec;
  84.       rp += rn - prec;
  85.       rn = prec;
  86.     }
  87.   /* With somewhat less than 50% probability, we can skip this copy.  */
  88.   if (passed_rp != rp + off)
  89.     MPN_COPY_INCR (passed_rp, rp + off, rn);
  90.   *ignp = ign;
  91.   return rn;
  92. }
  93. char *
  94. mpf_get_str (char *dbuf, mp_exp_t *exp, int base, size_t n_digits, mpf_srcptr u)
  95. {
  96.   mp_exp_t ue;
  97.   mp_size_t n_limbs_needed;
  98.   size_t max_digits;
  99.   mp_ptr up, pp, tp;
  100.   mp_size_t un, pn, tn;
  101.   unsigned char *tstr;
  102.   mp_exp_t exp_in_base;
  103.   size_t n_digits_computed;
  104.   mp_size_t i;
  105.   const char *num_to_text;
  106.   size_t alloc_size = 0;
  107.   char *dp;
  108.   TMP_DECL;
  109.   up = PTR(u);
  110.   un = ABSIZ(u);
  111.   ue = EXP(u);
  112.   if (base >= 0)
  113.     {
  114.       num_to_text = "0123456789abcdefghijklmnopqrstuvwxyz";
  115.       if (base == 0)
  116. base = 10;
  117.       else if (base > 36)
  118. {
  119.   num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  120.   if (base > 62)
  121.     return NULL;
  122. }
  123.     }
  124.   else
  125.     {
  126.       base = -base;
  127.       num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  128.     }
  129.   MPF_SIGNIFICANT_DIGITS (max_digits, base, PREC(u));
  130.   if (n_digits == 0 || n_digits > max_digits)
  131.     n_digits = max_digits;
  132.   if (dbuf == 0)
  133.     {
  134.       /* We didn't get a string from the user.  Allocate one (and return
  135.  a pointer to it) with space for `-' and terminating null.  */
  136.       alloc_size = n_digits + 2;
  137.       dbuf = (char *) (*__gmp_allocate_func) (n_digits + 2);
  138.     }
  139.   if (un == 0)
  140.     {
  141.       *exp = 0;
  142.       *dbuf = 0;
  143.       n_digits = 0;
  144.       goto done;
  145.     }
  146.   TMP_MARK;
  147.   /* Allocate temporary digit space.  We can't put digits directly in the user
  148.      area, since we generate more digits than requested.  (We allocate
  149.      2 * GMP_LIMB_BITS extra bytes because of the digit block nature of the
  150.      conversion.)  */
  151.   tstr = (unsigned char *) TMP_ALLOC (n_digits + 2 * GMP_LIMB_BITS + 3);
  152.   n_limbs_needed = 2 + (mp_size_t)
  153.     (n_digits / (GMP_NUMB_BITS * mp_bases[base].chars_per_bit_exactly));
  154.   if (ue <= n_limbs_needed)
  155.     {
  156.       /* We need to multiply number by base^n to get an n_digits integer part.  */
  157.       mp_size_t n_more_limbs_needed, ign, off;
  158.       unsigned long e;
  159.       n_more_limbs_needed = n_limbs_needed - ue;
  160.       e = (unsigned long) n_more_limbs_needed * (GMP_NUMB_BITS * mp_bases[base].chars_per_bit_exactly);
  161.       if (un > n_limbs_needed)
  162. {
  163.   up += un - n_limbs_needed;
  164.   un = n_limbs_needed;
  165. }
  166.       pp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2);
  167.       tp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2);
  168.       pn = mpn_pow_1_highpart (pp, &ign, (mp_limb_t) base, e, n_limbs_needed, tp);
  169.       if (un > pn)
  170. mpn_mul (tp, up, un, pp, pn); /* FIXME: mpn_mul_highpart */
  171.       else
  172. mpn_mul (tp, pp, pn, up, un); /* FIXME: mpn_mul_highpart */
  173.       tn = un + pn;
  174.       tn -= tp[tn - 1] == 0;
  175.       off = un - ue - ign;
  176.       if (off < 0)
  177. {
  178.   MPN_COPY_DECR (tp - off, tp, tn);
  179.   MPN_ZERO (tp, -off);
  180.   tn -= off;
  181.   off = 0;
  182. }
  183.       n_digits_computed = mpn_get_str (tstr, base, tp + off, tn - off);
  184.       exp_in_base = n_digits_computed - e;
  185.     }
  186.   else
  187.     {
  188.       /* We need to divide number by base^n to get an n_digits integer part.  */
  189.       mp_size_t n_less_limbs_needed, ign, off, xn;
  190.       unsigned long e;
  191.       mp_ptr dummyp, xp;
  192.       n_less_limbs_needed = ue - n_limbs_needed;
  193.       e = (unsigned long) n_less_limbs_needed * (GMP_NUMB_BITS * mp_bases[base].chars_per_bit_exactly);
  194.       if (un > n_limbs_needed)
  195. {
  196.   up += un - n_limbs_needed;
  197.   un = n_limbs_needed;
  198. }
  199.       pp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2);
  200.       tp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2);
  201.       pn = mpn_pow_1_highpart (pp, &ign, (mp_limb_t) base, e, n_limbs_needed, tp);
  202.       xn = n_limbs_needed + (n_less_limbs_needed-ign);
  203.       xp = TMP_ALLOC_LIMBS (xn);
  204.       off = xn - un;
  205.       MPN_ZERO (xp, off);
  206.       MPN_COPY (xp + off, up, un);
  207.       dummyp = TMP_ALLOC_LIMBS (pn);
  208.       mpn_tdiv_qr (tp, dummyp, (mp_size_t) 0, xp, xn, pp, pn);
  209.       tn = xn - pn + 1;
  210.       tn -= tp[tn - 1] == 0;
  211.       n_digits_computed = mpn_get_str (tstr, base, tp, tn);
  212.       exp_in_base = n_digits_computed + e;
  213.     }
  214.   /* We should normally have computed too many digits.  Round the result
  215.      at the point indicated by n_digits.  */
  216.   if (n_digits_computed > n_digits)
  217.     {
  218.       size_t i;
  219.       /* Round the result.  */
  220.       if (tstr[n_digits] * 2 >= base)
  221. {
  222.   n_digits_computed = n_digits;
  223.   for (i = n_digits - 1;; i--)
  224.     {
  225.       unsigned int x;
  226.       x = ++(tstr[i]);
  227.       if (x != base)
  228. break;
  229.       n_digits_computed--;
  230.       if (i == 0)
  231. {
  232.   /* We had something like `bbbbbbb...bd', where 2*d >= base
  233.      and `b' denotes digit with significance base - 1.
  234.      This rounds up to `1', increasing the exponent.  */
  235.   tstr[0] = 1;
  236.   n_digits_computed = 1;
  237.   exp_in_base++;
  238.   break;
  239. }
  240.     }
  241. }
  242.     }
  243.   /* We might have fewer digits than requested as a result of rounding above,
  244.      (i.e. 0.999999 => 1.0) or because we have a number that simply doesn't
  245.      need many digits in this base (e.g., 0.125 in base 10).  */
  246.   if (n_digits > n_digits_computed)
  247.     n_digits = n_digits_computed;
  248.   /* Remove trailing 0.  There can be many zeros.  */
  249.   while (n_digits != 0 && tstr[n_digits - 1] == 0)
  250.     n_digits--;
  251.   dp = dbuf + (SIZ(u) < 0);
  252.   /* Translate to ASCII and copy to result string.  */
  253.   for (i = 0; i < n_digits; i++)
  254.     dp[i] = num_to_text[tstr[i]];
  255.   dp[n_digits] = 0;
  256.   *exp = exp_in_base;
  257.   if (SIZ(u) < 0)
  258.     {
  259.       dbuf[0] = '-';
  260.       n_digits++;
  261.     }
  262.   TMP_FREE;
  263.  done:
  264.   /* If the string was alloced then resize it down to the actual space
  265.      required.  */
  266.   if (alloc_size != 0)
  267.     {
  268.       __GMP_REALLOCATE_FUNC_MAYBE_TYPE (dbuf, alloc_size, n_digits + 1, char);
  269.     }
  270.   return dbuf;
  271. }