Annotation of OpenXM_contrib/gmp/mpz/lucnum_ui.c, Revision 1.1
1.1 ! ohara 1: /* mpz_lucnum_ui -- calculate Lucas number.
! 2:
! 3: Copyright 2001 Free Software Foundation, Inc.
! 4:
! 5: This file is part of the GNU MP Library.
! 6:
! 7: The GNU MP Library is free software; you can redistribute it and/or modify
! 8: it under the terms of the GNU Lesser General Public License as published by
! 9: the Free Software Foundation; either version 2.1 of the License, or (at your
! 10: option) any later version.
! 11:
! 12: The GNU MP Library is distributed in the hope that it will be useful, but
! 13: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
! 14: or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
! 15: License for more details.
! 16:
! 17: You should have received a copy of the GNU Lesser General Public License
! 18: along with the GNU MP Library; see the file COPYING.LIB. If not, write to
! 19: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
! 20: MA 02111-1307, USA. */
! 21:
! 22: #include <stdio.h>
! 23: #include "gmp.h"
! 24: #include "gmp-impl.h"
! 25:
! 26:
! 27: /* change this to "#define TRACE(x) x" for diagnostics */
! 28: #define TRACE(x)
! 29:
! 30:
! 31: /* Notes:
! 32:
! 33: For the +4 in L[2k+1] when k is even, all L[4m+3] == 4, 5 or 7 mod 8, so
! 34: there can't be an overflow applying +4 to just the low limb (since that
! 35: would leave 0, 1, 2 or 3 mod 8).
! 36:
! 37: For the -4 in L[2k+1] when k is even, it seems (no proof) that
! 38: L[3*2^(b-2)-3] == -4 mod 2^b, so for instance with a 32-bit limb
! 39: L[0xBFFFFFFD] == 0xFFFFFFFC mod 2^32, and this implies a borrow from the
! 40: low limb. Obviously L[0xBFFFFFFD] is a huge number, but it's at least
! 41: conceivable to calculate it, so it probably should be handled.
! 42:
! 43: For the -2 in L[2k] with k even, it seems (no proof) L[2^(b-1)] == -1 mod
! 44: 2^b, so for instance in 32-bits L[0x80000000] has a low limb of
! 45: 0xFFFFFFFF so there would have been a borrow. Again L[0x80000000] is
! 46: obviously huge, but probably should be made to work. */
! 47:
! 48: void
! 49: mpz_lucnum_ui (mpz_ptr ln, unsigned long n)
! 50: {
! 51: mp_size_t lalloc, xalloc, lsize, xsize;
! 52: mp_ptr lp, xp;
! 53: mp_limb_t c;
! 54: int zeros;
! 55: TMP_DECL (marker);
! 56:
! 57: TRACE (printf ("mpn_lucnum_ui n=%lu\n", n));
! 58:
! 59: if (n <= FIB_TABLE_LUCNUM_LIMIT)
! 60: {
! 61: /* L[n] = F[n] + 2F[n-1] */
! 62: PTR(ln)[0] = FIB_TABLE(n) + 2 * FIB_TABLE ((int) n - 1);
! 63: SIZ(ln) = 1;
! 64: return;
! 65: }
! 66:
! 67: /* +1 since L[n]=F[n]+2F[n-1] might be 1 limb bigger than F[n], further +1
! 68: since square or mul used below might need an extra limb over the true
! 69: size */
! 70: lalloc = MPN_FIB2_SIZE (n) + 2;
! 71: MPZ_REALLOC (ln, lalloc);
! 72: lp = PTR (ln);
! 73:
! 74: TMP_MARK (marker);
! 75: xalloc = lalloc;
! 76: xp = TMP_ALLOC_LIMBS (xalloc);
! 77:
! 78: /* Strip trailing zeros from n, until either an odd number is reached
! 79: where the L[2k+1] formula can be used, or until n fits within the
! 80: FIB_TABLE data. The table is preferred of course. */
! 81: zeros = 0;
! 82: for (;;)
! 83: {
! 84: if (n & 1)
! 85: {
! 86: /* L[2k+1] = 5*F[k-1]*(2*F[k]+F[k-1]) - 4*(-1)^k */
! 87:
! 88: mp_size_t yalloc, ysize;
! 89: mp_ptr yp;
! 90:
! 91: TRACE (printf (" initial odd n=%lu\n", n));
! 92:
! 93: yalloc = MPN_FIB2_SIZE (n/2);
! 94: yp = TMP_ALLOC_LIMBS (yalloc);
! 95: ASSERT (xalloc >= yalloc);
! 96:
! 97: xsize = mpn_fib2_ui (xp, yp, n/2);
! 98:
! 99: /* possible high zero on F[k-1] */
! 100: ysize = xsize;
! 101: ysize -= (yp[ysize-1] == 0);
! 102: ASSERT (yp[ysize-1] != 0);
! 103:
! 104: /* xp = 2*F[k] + F[k-1] */
! 105: c = mpn_lshift (xp, xp, xsize, 1);
! 106: c += mpn_add_n (xp, xp, yp, xsize);
! 107: ASSERT (xalloc >= xsize+1);
! 108: xp[xsize] = c;
! 109: xsize += (c != 0);
! 110: ASSERT (xp[xsize-1] != 0);
! 111:
! 112: ASSERT (lalloc >= xsize + ysize);
! 113: c = mpn_mul (lp, xp, xsize, yp, ysize);
! 114: lsize = xsize + ysize;
! 115: lsize -= (c == 0);
! 116:
! 117: /* lp = 5*lp */
! 118: #if HAVE_NATIVE_mpn_addlshift
! 119: c = mpn_addlshift (lp, lp, lsize, 2);
! 120: #else
! 121: c = mpn_lshift (xp, lp, lsize, 2);
! 122: c += mpn_add_n (lp, lp, xp, lsize);
! 123: #endif
! 124: ASSERT (lalloc >= lsize+1);
! 125: lp[lsize] = c;
! 126: lsize += (c != 0);
! 127:
! 128: /* lp = lp - 4*(-1)^k */
! 129: if (n & 2)
! 130: {
! 131: /* no overflow, see comments above */
! 132: ASSERT (lp[0] <= MP_LIMB_T_MAX-4);
! 133: lp[0] += 4;
! 134: }
! 135: else
! 136: {
! 137: /* won't go negative */
! 138: MPN_DECR_U (lp, lsize, CNST_LIMB(4));
! 139: }
! 140:
! 141: TRACE (mpn_trace (" l",lp, lsize));
! 142: break;
! 143: }
! 144:
! 145: MP_PTR_SWAP (xp, lp); /* balance the swaps wanted in the L[2k] below */
! 146: zeros++;
! 147: n /= 2;
! 148:
! 149: if (n <= FIB_TABLE_LUCNUM_LIMIT)
! 150: {
! 151: /* L[n] = F[n] + 2F[n-1] */
! 152: lp[0] = FIB_TABLE (n) + 2 * FIB_TABLE ((int) n - 1);
! 153: lsize = 1;
! 154:
! 155: TRACE (printf (" initial small n=%lu\n", n);
! 156: mpn_trace (" l",lp, lsize));
! 157: break;
! 158: }
! 159: }
! 160:
! 161: for ( ; zeros != 0; zeros--)
! 162: {
! 163: /* L[2k] = L[k]^2 + 2*(-1)^k */
! 164:
! 165: TRACE (printf (" zeros=%d\n", zeros));
! 166:
! 167: ASSERT (xalloc >= 2*lsize);
! 168: mpn_sqr_n (xp, lp, lsize);
! 169: lsize *= 2;
! 170: lsize -= (xp[lsize-1] == 0);
! 171:
! 172: /* First time around the loop k==n determines (-1)^k, after that k is
! 173: always even and we set n=0 to indicate that. */
! 174: if (n & 1)
! 175: {
! 176: /* L[n]^2 == 0 or 1 mod 4, like all squares, so +2 gives no carry */
! 177: ASSERT (xp[0] <= MP_LIMB_T_MAX-2);
! 178: xp[0] += 2;
! 179: n = 0;
! 180: }
! 181: else
! 182: {
! 183: /* won't go negative */
! 184: MPN_DECR_U (xp, lsize, CNST_LIMB(2));
! 185: }
! 186:
! 187: MP_PTR_SWAP (xp, lp);
! 188: ASSERT (lp[lsize-1] != 0);
! 189: }
! 190:
! 191: /* should end up in the right spot after all the xp/lp swaps */
! 192: ASSERT (lp == PTR(ln));
! 193: SIZ(ln) = lsize;
! 194:
! 195: TMP_FREE (marker);
! 196: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to lucnum_ui.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp / mpz