Opened 12 years ago

Closed 12 years ago

#424 closed enhancement (fixed)

GMP development code for fast GCD

Reported by: dmharvey Owned by: somebody
Priority: major Milestone: sage-2.8.4
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

The GMP development page

http://gmplib.org/devel/

has some code for fast GCD/XGCD of huge operands. It might not appear for a while in official releases, but they claim it's stable, and I'm interested in patching it into SAGE. I tried to do this and got stuck on configuration problems that a linux/GNU guru could help with.

Attachments (3)

gcd1.patch (137.3 KB) - added by dmharvey 12 years ago.
patch that at least puts some files in the right places
gcd2.patch (6.0 KB) - added by dmharvey 12 years ago.
fixed up various configuration/build files to work properly
fastgcd.hg (217.1 KB) - added by dmharvey 12 years ago.
patch for gmp spkg

Download all attachments as: .zip

Change History (8)

comment:1 Changed 12 years ago by was

I tried for a while to get the patch to work. I think it doesn't work against the latest GMP release (plain vanilla), which is newer than the last change of that patch:

`echo gcd | sed 's/_$//'`    -O2 -m64 -mtune=k8 -c -o gcd.lo gcd.c
 gcc -DHAVE_CONFIG_H -I. -I. -I.. -D__GMP_WITHIN_GMP -I.. -DOPERATION_gcd -O2 -m64 -mtune=k8 -c gcd.c  -fPIC -DPIC -o .libs/gcd.o
gcd.c: In function 'gcd_schoenhage':
gcd.c:702: error: storage size of 'hgcd' isn't known
gcd.c:703: error: storage size of 'quotients' isn't known
gcd.c:704: error: array type has incomplete element type
gcd.c:748: error: 'GCD_SCHOENHAGE_THRESHOLD' undeclared (first use in this function)
gcd.c:748: error: (Each undeclared identifier is reported only once
gcd.c:748: error: for each function it appears in.)
gcd.c:778: error: storage size of '__nhgcd_swap4_left_tmp' isn't known
gcd.c:796: error: invalid use of undefined type 'struct hgcd_row'
gcd.c:800: error: storage size of '__nhgcd_swap4_2_tmp' isn't known
gcd.c: In function '__gmpn_gcd':
gcd.c:831: error: 'GCD_SCHOENHAGE_THRESHOLD' undeclared (first use in this function)
make[2]: *** [gcd.lo] Error 1
make[2]: Leaving directory `/home/was/sage2.8/sage-2.8/spkg/build/gmp-4.2.1.p9/src/mpn'
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory `/home/was/sage2.8/sage-2.8/spkg/build/gmp-4.2.1.p9/src'
make: *** [all] Error 2

This isn't a problem with autoconf, etc., -- it s a problem with the patch simply not working.

William

comment:2 Changed 12 years ago by dmharvey

Well no, I *did* actually get the patch compiling in a standalone setting, after manually fiddling with autoconf (etc) output files. But I couldn't get it compiling in SAGE, now I can't quite remember why.

It might help to check out the doc/configuration file in GMP, which explains in some detail how to add new files to GMP.

Changed 12 years ago by dmharvey

patch that at least puts some files in the right places

comment:3 Changed 12 years ago by dmharvey

I've attached an initial patch which I believe puts all the right files and new lines of code in the right places. I haven't tried building yet. Apply this patch by patch -p1 < gcd1.patch in the gmp-4.2.1 directory.

Changed 12 years ago by dmharvey

fixed up various configuration/build files to work properly

Changed 12 years ago by dmharvey

patch for gmp spkg

comment:4 Changed 12 years ago by dmharvey

I just attached a patch (fastgcd.hg) which should be applied to the GMP spkg (gmp-4.2.1.p9.spkg. BTW the file spkg-install~ should be deleted from that spkg too.) This patch supersedes the files gcd1.patch and gcd2.patch. This new patch adds all relevant files, and also modifies the build scripts. (It also addresses #605, I hope). I've tested it on OSX ppc and intel, haven't tested it on sage.math yet.

comment:5 Changed 12 years ago by was

  • Milestone set to sage-2.8.4
  • Resolution set to fixed
  • Status changed from new to closed
Note: See TracTickets for help on using tickets.