On Dec 24, 2:47 am, ja...@njkfrudils.plus.com wrote:
> On Wednesday 24 December 2008 02:23:22 Jason Martin wrote:
>
> > Thanks Jason & Bill,
>
> > I'll try digging into those errors in two day (Christmas/Family
> > obligations at the moment). I really really dislike
> > auto{conf|make|tool}, but I guess I need to embrace it... seems to be
> > the only game in town.
>
> The tag update has fixed the make speed , make tune errors
>
Sorry, no it hasn't , I forgot to to reapply the new gcd code after
refreshing the trunk
>
>
> > --jason
>
> > Jason Worth Martin
> > Asst. Professor of Mathematics
> >http://www.math.jmu.edu/~martin
>
> > On Tue, Dec 23, 2008 at 7:51 PM, <ja...@njkfrudils.plus.com> wrote:
> > > On Wednesday 24 December 2008 00:31:50 Bill Hart wrote:
> > >> On sage.math:
>
> > >> cd tune
> > >> make tune
>
> > >> ./.libs/libspeed.a(gcd_bin.o): In function `__gmpn_ngcd_matrix_init':
> > >> gcd_bin.c:(.text+0x0): multiple definition of `__gmpn_ngcd_matrix_init'
> > >> gcd.o:gcd.c:(.text+0x0): first defined here
> > >> ./.libs/libspeed.a(gcd_bin.o): In function `__gmpn_nhgcd_itch':
> > >> gcd_bin.c:(.text+0x80): multiple definition of `__gmpn_nhgcd_itch'
> > >> gcd.o:gcd.c:(.text+0x80): first defined here
> > >> ./.libs/libspeed.a(gcd_bin.o): In function `__gmpn_nhgcd':
> > >> gcd_bin.c:(.text+0xc4): multiple definition of `__gmpn_nhgcd'
> > >> gcd.o:gcd.c:(.text+0xc4): first defined here
> > >> ./.libs/libspeed.a(gcd_bin.o): In function `mpn_basic_gcd':
> > >> gcd_bin.c:(.text+0x2ed): multiple definition of `mpn_basic_gcd'
> > >> gcd.o:gcd.c:(.text+0x2ed): first defined here
>
> > > On my K8-linux same problem with make speed and tune
>
> > > ./configure && make && make check passes OK , and I got bored running
> > > ./try mpn_gcd :)
>
> > > get this warning from the build though
>
> > > ngcd.c: In function 'mpn_ngcd':
> > > ngcd.c:75: warning: implicit declaration of function 'mpn_basic_gcd'
>
> > > gcc -std=gnu99 -DHAVE_CONFIG_H -I. -I.. -D__GMP_WITHIN_GMP -I.. -O2 -m64
> > > -march=k8 -mtune=k8 -c gcd.c -fPIC -DPIC -o .libs/gcd.o
> > > gcd.c: In function 'mpz_rgcd':
> > > gcd.c:167: warning: implicit declaration of function 'mpn_rgcd'
> > > gcd.c: In function 'mpz_bgcd':
> > > gcd.c:171: warning: implicit declaration of function 'mpn_bgcd'
> > > gcd.c: In function 'mpz_sgcd':
> > > gcd.c:175: warning: implicit declaration of function 'mpn_sgcd'
> > > gcd.c: In function 'mpz_ngcd':
> > > gcd.c:179: warning: implicit declaration of function 'mpn_ngcd'
>
> > > ./configure --enable-alloca=debug --enable-assert && make && make check
> > > passes OK
>
> > > but
>
> > > ./configure --enable-alloca=debug --enable-assert --enable-nails=2 &&
> > > make && make check
>
> > > PASS: t-mul_i
> > > PASS: t-tdiv
> > > PASS: t-tdiv_ui
> > > PASS: t-fdiv
> > > PASS: t-fdiv_ui
> > > PASS: t-cdiv_ui
> > > nhgcd2.c:206: GNU MP assertion failed: h0 == h1
> > > /bin/sh: line 4: 31599 Aborted ${dir}$tst
> > > FAIL: t-gcd
> > > PASS: t-gcd_ui
> > > nhgcd2.c:206: GNU MP assertion failed: h0 == h1
> > > /bin/sh: line 4: 31647 Aborted ${dir}$tst
> > > FAIL: t-lcm
> > > PASS: dive
> > > PASS: dive_ui
> > > PASS: t-sqrtrem
> > > PASS: convert
> > > PASS: io
>
> > >> Bill.
>
> > >> 2008/12/23 Jason Martin <jason.worth.mar...@gmail.com>:
> > >> > Attached are some edited versions of
>
> > >> > mpn/generic/gcd.c
>
> > >> > and
>
> > >> > mpn/generic/ngcd.c
>
> > >> > Drop them in, test them for correctness and speed. Let me know what
> > >> > breaks. When everyone is happy, I'll check them in to svn
>
> > >> > --jason
>
> > >> > Jason Worth Martin
> > >> > Asst. Professor of Mathematics
> > >> >http://www.math.jmu.edu/~martin
>
> > >> > /* Schönhage's 1987 algorithm, reorganized into hgcd form */
>
> > >> > #include <stdio.h> /* for NULL */
>
> > >> > #include "gmp.h"
> > >> > #include "gmp-impl.h"
> > >> > #include "longlong.h"
>
> > >> > /* ******************************************************************
> > >> > * Here we are including the original GMP version of mpn_gcd
> > >> > * but we rename it as mpn_basic_gcd. It needs to be available
> > >> > * for the ngcd algorithm to call in the base case.
> > >> > *
> > >> > * Preconditions [U = (up, usize) and V = (vp, vsize)]:
> > >> > *
> > >> > * 1. V is odd.
> > >> > * 2. numbits(U) >= numbits(V).
> > >> > *
> > >> > * Both U and V are destroyed by the operation. The result is left
> > >> > at vp, * and its size is returned.
> > >> > *
> > >> > * Ken Weber (kwe...@mat.ufrgs.br, kwe...@mcs.kent.edu)
> > >> > *
> > >> > * Funding for this work has been partially provided by Conselho
> > >> > * Nacional de Desenvolvimento Cienti'fico e Tecnolo'gico (CNPq) do
> > >> > * Brazil, Grant 301314194-2, and was done while I was a visiting
> > >> > * reseacher in the Instituto de Matema'tica at Universidade Federal
> > >> > * do Rio Grande do Sul (UFRGS).
> > >> > *
> > >> > * Refer to K. Weber, The accelerated integer GCD algorithm, ACM
> > >> > * Transactions on Mathematical Software, v. 21 (March), 1995,
> > >> > * pp. 111-122.
> > >> > *
> > >> > * *****************************************************************/
>
> > >> > /* If MIN (usize, vsize) >= GCD_ACCEL_THRESHOLD, then the accelerated
> > >> > algorithm is used, otherwise the binary algorithm is used. This may
> > >> > be adjusted for different architectures. */
> > >> > #ifndef GCD_ACCEL_THRESHOLD
> > >> > #define GCD_ACCEL_THRESHOLD 5
> > >> > #endif
>
> > >> > /* When U and V differ in size by more than BMOD_THRESHOLD, the
> > >> > accelerated algorithm reduces using the bmod operation. Otherwise,
> > >> > the k-ary reduction is used. 0 <= BMOD_THRESHOLD < GMP_NUMB_BITS. */
> > >> > enum
> > >> > {
> > >> > BMOD_THRESHOLD = GMP_NUMB_BITS/2
> > >> > };
>
> > >> > /* Use binary algorithm to compute V <-- GCD (V, U) for usize, vsize
> > >> > == 2. Both U and V must be odd. */
> > >> > static inline mp_size_t
> > >> > gcd_2 (mp_ptr vp, mp_srcptr up)
> > >> > {
> > >> > mp_limb_t u0, u1, v0, v1;
> > >> > mp_size_t vsize;
>
> > >> > u0 = up[0];
> > >> > u1 = up[1];
> > >> > v0 = vp[0];
> > >> > v1 = vp[1];
>
> > >> > while (u1 != v1 && u0 != v0)
> > >> > {
> > >> > unsigned long int r;
> > >> > if (u1 > v1)
> > >> > {
> > >> > u1 -= v1 + (u0 < v0);
> > >> > u0 = (u0 - v0) & GMP_NUMB_MASK;
> > >> > count_trailing_zeros (r, u0);
> > >> > u0 = ((u1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (u0 >>
> > >> > r); u1 >>= r;
> > >> > }
> > >> > else /* u1 < v1. */
> > >> > {
> > >> > v1 -= u1 + (v0 < u0);
> > >> > v0 = (v0 - u0) & GMP_NUMB_MASK;
> > >> > count_trailing_zeros (r, v0);
> > >> > v0 = ((v1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (v0 >>
> > >> > r); v1 >>= r;
> > >> > }
> > >> > }
>
> > >> > vp[0] = v0, vp[1] = v1, vsize = 1 + (v1 != 0);
>
> > >> > /* If U == V == GCD, done. Otherwise, compute GCD (V, |U - V|). */
> > >> > if (u1 == v1 && u0 == v0)
> > >> > return vsize;
>
> > >> > v0 = (u0 == v0) ? (u1 > v1) ? u1-v1 : v1-u1 : (u0 > v0) ? u0-v0 :
> > >> > v0-u0; vp[0] = mpn_gcd_1 (vp, vsize, v0);
>
> > >> > return 1;
> > >> > }
>
> > >> > /* The function find_a finds 0 < N < 2^GMP_NUMB_BITS such that there
> > >> > exists 0 < |D| < 2^GMP_NUMB_BITS, and N == D * C mod
> > >> > 2^(2*GMP_NUMB_BITS). In the reference article, D was computed along
> > >> > with N, but it is better to compute D separately as D <-- N / C mod
> > >> > 2^(GMP_NUMB_BITS + 1), treating the result as a twos' complement
> > >> > signed integer.
>
> > >> > Initialize N1 to C mod 2^(2*GMP_NUMB_BITS). According to the
> > >> > reference article, N2 should be initialized to 2^(2*GMP_NUMB_BITS),
> > >> > but we use 2^(2*GMP_NUMB_BITS) - N1 to start the calculations within
> > >> > double precision. If N2 > N1 initially, the first iteration of the
> > >> > while loop will swap them. In all other situations, N1 >= N2 is
> > >> > maintained. */
>
> > >> > #if HAVE_NATIVE_mpn_gcd_finda
> > >> > #define find_a(cp) mpn_gcd_finda (cp)
>
> > >> > #else
> > >> > static
> > >> > #if ! defined (__i386__)
> > >> > inline /* don't inline this for the x86 */
> > >> > #endif
> > >> > mp_limb_t
> > >> > find_a (mp_srcptr cp)
> > >> > {
> > >> > unsigned long int leading_zero_bits = 0;
>
> > >> > mp_limb_t n1_l = cp[0]; /* N1 == n1_h * 2^GMP_NUMB_BITS + n1_l.
> > >> > */ mp_limb_t n1_h = cp[1];
>
> > >> > mp_limb_t n2_l = (-n1_l & GMP_NUMB_MASK); /* N2 == n2_h *
> > >> > 2^GMP_NUMB_BITS + n2_l. */ mp_limb_t n2_h = (~n1_h & GMP_NUMB_MASK);
>
> > >> > /* Main loop. */
> > >> > while (n2_h != 0) /* While N2 >= 2^GMP_NUMB_BITS. */
> > >> > {
> > >> > /* N1 <-- N1 % N2. */
> > >> > if (((GMP_NUMB_HIGHBIT >> leading_zero_bits) & n2_h) == 0)
> > >> > {
> > >> > unsigned long int i;
> > >> > count_leading_zeros (i, n2_h);
> > >> > i -= GMP_NAIL_BITS;
> > >> > i -= leading_zero_bits;
> > >> > leading_zero_bits += i;
> > >> > n2_h = ((n2_h << i) & GMP_NUMB_MASK) | (n2_l >>
> > >> > (GMP_NUMB_BITS - i)); n2_l = (n2_l << i) & GMP_NUMB_MASK;
> > >> > do
> > >> > {
> > >> > if (n1_h > n2_h || (n1_h == n2_h && n1_l >= n2_l))
> > >> > {
> > >> > n1_h -= n2_h + (n1_l < n2_l);
> > >> > n1_l = (n1_l - n2_l) & GMP_NUMB_MASK;
> > >> > }
> > >> > n2_l = (n2_l >> 1) | ((n2_h << (GMP_NUMB_BITS - 1)) &
> > >> > GMP_NUMB_MASK); n2_h >>= 1;
> > >> > i -= 1;
> > >> > }
> > >> > while (i != 0);
> > >> > }
> > >> > if (n1_h > n2_h || (n1_h == n2_h && n1_l >= n2_l))
> > >> > {
> > >> > n1_h -= n2_h + (n1_l < n2_l);
> > >> > n1_l = (n1_l - n2_l) & GMP_NUMB_MASK;
> > >> > }
>
> > >> > MP_LIMB_T_SWAP (n1_h, n2_h);
>
> ...
>
> read more »
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To post to this group, send email to mpir-devel@googlegroups.com
To unsubscribe from this group, send email to
mpir-devel+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/mpir-devel?hl=en
-~----------~----~----~----~------~----~------~--~---
