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

数学计算

开发平台:

Unix_Linux

  1. /* mpz_lucnum_ui -- calculate Lucas number.
  2. Copyright 2001, 2003, 2005 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. #include <stdio.h>
  15. #include "gmp.h"
  16. #include "gmp-impl.h"
  17. /* change this to "#define TRACE(x) x" for diagnostics */
  18. #define TRACE(x)
  19. /* Notes:
  20.    For the +4 in L[2k+1] when k is even, all L[4m+3] == 4, 5 or 7 mod 8, so
  21.    there can't be an overflow applying +4 to just the low limb (since that
  22.    would leave 0, 1, 2 or 3 mod 8).
  23.    For the -4 in L[2k+1] when k is even, it seems (no proof) that
  24.    L[3*2^(b-2)-3] == -4 mod 2^b, so for instance with a 32-bit limb
  25.    L[0xBFFFFFFD] == 0xFFFFFFFC mod 2^32, and this implies a borrow from the
  26.    low limb.  Obviously L[0xBFFFFFFD] is a huge number, but it's at least
  27.    conceivable to calculate it, so it probably should be handled.
  28.    For the -2 in L[2k] with k even, it seems (no proof) L[2^(b-1)] == -1 mod
  29.    2^b, so for instance in 32-bits L[0x80000000] has a low limb of
  30.    0xFFFFFFFF so there would have been a borrow.  Again L[0x80000000] is
  31.    obviously huge, but probably should be made to work.  */
  32. void
  33. mpz_lucnum_ui (mpz_ptr ln, unsigned long n)
  34. {
  35.   mp_size_t  lalloc, xalloc, lsize, xsize;
  36.   mp_ptr     lp, xp;
  37.   mp_limb_t  c;
  38.   int        zeros;
  39.   TMP_DECL;
  40.   TRACE (printf ("mpn_lucnum_ui n=%lun", n));
  41.   if (n <= FIB_TABLE_LUCNUM_LIMIT)
  42.     {
  43.       /* L[n] = F[n] + 2F[n-1] */
  44.       PTR(ln)[0] = FIB_TABLE(n) + 2 * FIB_TABLE ((int) n - 1);
  45.       SIZ(ln) = 1;
  46.       return;
  47.     }
  48.   /* +1 since L[n]=F[n]+2F[n-1] might be 1 limb bigger than F[n], further +1
  49.      since square or mul used below might need an extra limb over the true
  50.      size */
  51.   lalloc = MPN_FIB2_SIZE (n) + 2;
  52.   MPZ_REALLOC (ln, lalloc);
  53.   lp = PTR (ln);
  54.   TMP_MARK;
  55.   xalloc = lalloc;
  56.   xp = TMP_ALLOC_LIMBS (xalloc);
  57.   /* Strip trailing zeros from n, until either an odd number is reached
  58.      where the L[2k+1] formula can be used, or until n fits within the
  59.      FIB_TABLE data.  The table is preferred of course.  */
  60.   zeros = 0;
  61.   for (;;)
  62.     {
  63.       if (n & 1)
  64.         {
  65.           /* L[2k+1] = 5*F[k-1]*(2*F[k]+F[k-1]) - 4*(-1)^k */
  66.           mp_size_t  yalloc, ysize;
  67.           mp_ptr     yp;
  68.           TRACE (printf ("  initial odd n=%lun", n));
  69.           yalloc = MPN_FIB2_SIZE (n/2);
  70.           yp = TMP_ALLOC_LIMBS (yalloc);
  71.           ASSERT (xalloc >= yalloc);
  72.           xsize = mpn_fib2_ui (xp, yp, n/2);
  73.           /* possible high zero on F[k-1] */
  74.           ysize = xsize;
  75.           ysize -= (yp[ysize-1] == 0);
  76.           ASSERT (yp[ysize-1] != 0);
  77.           /* xp = 2*F[k] + F[k-1] */
  78. #if HAVE_NATIVE_mpn_addlsh1_n
  79.           c = mpn_addlsh1_n (xp, yp, xp, xsize);
  80. #else
  81.           c = mpn_lshift (xp, xp, xsize, 1);
  82.           c += mpn_add_n (xp, xp, yp, xsize);
  83. #endif
  84.           ASSERT (xalloc >= xsize+1);
  85.           xp[xsize] = c;
  86.           xsize += (c != 0);
  87.           ASSERT (xp[xsize-1] != 0);
  88.           ASSERT (lalloc >= xsize + ysize);
  89.           c = mpn_mul (lp, xp, xsize, yp, ysize);
  90.           lsize = xsize + ysize;
  91.           lsize -= (c == 0);
  92.           /* lp = 5*lp */
  93. #if HAVE_NATIVE_mpn_addlshift
  94.           c = mpn_addlshift (lp, lp, lsize, 2);
  95. #else
  96.           c = mpn_lshift (xp, lp, lsize, 2);
  97.           c += mpn_add_n (lp, lp, xp, lsize);
  98. #endif
  99.           ASSERT (lalloc >= lsize+1);
  100.           lp[lsize] = c;
  101.           lsize += (c != 0);
  102.           /* lp = lp - 4*(-1)^k */
  103.           if (n & 2)
  104.             {
  105.               /* no overflow, see comments above */
  106.               ASSERT (lp[0] <= MP_LIMB_T_MAX-4);
  107.               lp[0] += 4;
  108.             }
  109.           else
  110.             {
  111.               /* won't go negative */
  112.               MPN_DECR_U (lp, lsize, CNST_LIMB(4));
  113.             }
  114.           TRACE (mpn_trace ("  l",lp, lsize));
  115.           break;
  116.         }
  117.       MP_PTR_SWAP (xp, lp); /* balance the swaps wanted in the L[2k] below */
  118.       zeros++;
  119.       n /= 2;
  120.       if (n <= FIB_TABLE_LUCNUM_LIMIT)
  121.         {
  122.           /* L[n] = F[n] + 2F[n-1] */
  123.           lp[0] = FIB_TABLE (n) + 2 * FIB_TABLE ((int) n - 1);
  124.           lsize = 1;
  125.           TRACE (printf ("  initial small n=%lun", n);
  126.                  mpn_trace ("  l",lp, lsize));
  127.           break;
  128.         }
  129.     }
  130.   for ( ; zeros != 0; zeros--)
  131.     {
  132.       /* L[2k] = L[k]^2 + 2*(-1)^k */
  133.       TRACE (printf ("  zeros=%dn", zeros));
  134.       ASSERT (xalloc >= 2*lsize);
  135.       mpn_sqr (xp, lp, lsize);
  136.       lsize *= 2;
  137.       lsize -= (xp[lsize-1] == 0);
  138.       /* First time around the loop k==n determines (-1)^k, after that k is
  139.          always even and we set n=0 to indicate that.  */
  140.       if (n & 1)
  141.         {
  142.           /* L[n]^2 == 0 or 1 mod 4, like all squares, so +2 gives no carry */
  143.           ASSERT (xp[0] <= MP_LIMB_T_MAX-2);
  144.           xp[0] += 2;
  145.           n = 0;
  146.         }
  147.       else
  148.         {
  149.           /* won't go negative */
  150.           MPN_DECR_U (xp, lsize, CNST_LIMB(2));
  151.         }
  152.       MP_PTR_SWAP (xp, lp);
  153.       ASSERT (lp[lsize-1] != 0);
  154.     }
  155.   /* should end up in the right spot after all the xp/lp swaps */
  156.   ASSERT (lp == PTR(ln));
  157.   SIZ(ln) = lsize;
  158.   TMP_FREE;
  159. }