as of today, there is a new version of my ratpoints program available.
ratpoints-2.1 uses SSE instructions on x86 processors to work with 128 bits at the same time (instead of 64 or even only 32). This results in a noticeable speed-up (some 25% reduced running time for "make test", up to 40% for curves with few points when searching up to a large height bound).
Best wishes, Michael Stoll -- Michael Stoll * http://www.mathe2.uni-bayreuth.de/stoll/ Mathematisches Institut * Universität Bayreuth * 95440 Bayreuth, Germany Michael.St...@uni-bayreuth.de
> as of today, there is a new version of myratpointsprogram available.
> ratpoints-2.1 uses SSE instructions on x86 processors to work with 128 bits at
> the same time (instead of 64 or even only 32). This results in a noticeable
> speed-up (some 25% reduced running time for "make test", up to 40% for curves
> with few points when searching up to a large height bound).
> What version of ratpoints is included in mwrank? How difficult would
> it be to upgrade to 2.1?
I'm sure I have answered this question endlessly in various places already.
I do not remember which version of Stoll's code I used. It was done in 1999.
It would be quite a lot of work to update it and I do not have the
time to do so: I changed a lot, and also Stoll's program is
completely rewritten so it would mean starting from scratch.
It would be worthwhile to have, independently of mwrank/eclib, access
to the point-searching functionality in ratpoints in Sage.
> On Mar 9, 2:50 am, Michael Stoll <Michael.St...@uni-bayreuth.de>
> wrote:
>> Hi everybody,
>> as of today, there is a new version of myratpointsprogram available.
>> ratpoints-2.1 uses SSE instructions on x86 processors to work with 128 bits at
>> the same time (instead of 64 or even only 32). This results in a noticeable
>> speed-up (some 25% reduced running time for "make test", up to 40% for curves
>> with few points when searching up to a large height bound).
> In trying to compile this on my MacBook, I run into the following
> compiler error, whether SSE2 is enabled or not:
> gcc sift.c -c -o sift.o -I/Users/rlmill/sage-3.4.rc0/local/include -
> Wall -O2 -DRATPOINTS_MAX_BITS_IN_PRIME=7
> sift.c: In function ‘_ratpoints_sift0’:
> sift.c:321: error: unrecognizable insn:
> (insn 290 289 291 25 (set (reg:DI 81 [ D.8230 ])
> (vec_select:DI (reg/v:V2DI 60 [ nums ])
> (parallel [
> (const_int 1 [0x1])
> ]))) -1 (nil)
> (nil))
> sift.c:321: internal compiler error: in extract_insn, at recog.c:2037
> Please submit a full bug report,
> with preprocessed source if appropriate.
> See <URL:http://developer.apple.com/bugreporter> for instructions.
> make: *** [sift.o] Error 1
Well, for the record (and I told this to Robert in person): This is a
bug in the gcc shipped with XCode 3.0 - I did not try any later
release of XCode to see if the code compiles. It build fine on
sage.math and rlm build an spkg out of it in case anyone is
interested. Since the code is currently GPL V3 there it does not
qualify to be merged at the moment anyway.
> Well, for the record (and I told this to Robert in person): This is a > bug in the gcc shipped with XCode 3.0 - I did not try any later > release of XCode to see if the code compiles. It build fine on > sage.math and rlm build an spkg out of it in case anyone is > interested.
at one point, I ran into a similar compiler bug when compiling an earlier version of the program with SSE2 enabled. It went away after I replaced a complicated statement by several simpler ones.
> Since the code is currently GPL V3 there it does not > qualify to be merged at the moment anyway.
What should I change to make it possible to merge it into SAGE?
Since you and I and Robert Miller will all be in Dagstuhl in May we
can perhaps sort this out there. By then (if not before) I will try
to see exactly what I would need in order to be able to use ratpoints
in mwrank (rather than adapting it, as I did before).
John
2009/4/6 Michael Stoll <Michael.St...@uni-bayreuth.de>:
>> Well, for the record (and I told this to Robert in person): This is a
>> bug in the gcc shipped with XCode 3.0 - I did not try any later
>> release of XCode to see if the code compiles. It build fine on
>> sage.math and rlm build an spkg out of it in case anyone is
>> interested.
> at one point, I ran into a similar compiler bug when compiling an earlier
> version of the program with SSE2 enabled. It went away after I replaced a
> complicated statement by several simpler ones.
>> Since the code is currently GPL V3 there it does not
>> qualify to be merged at the moment anyway.
> What should I change to make it possible to merge it into SAGE?
> Well, for the record (and I told this to Robert in person): This is a
> bug in the gcc shipped with XCode 3.0 - I did not try any later
> release of XCode to see if the code compiles...
This also happens with the latest development prerelease of XCode.
>> Well, for the record (and I told this to Robert in person): This is a >> bug in the gcc shipped with XCode 3.0 - I did not try any later >> release of XCode to see if the code compiles. It build fine on >> sage.math and rlm build an spkg out of it in case anyone is >> interested.
> at one point, I ran into a similar compiler bug when compiling an earlier > version of the program with SSE2 enabled. It went away after I replaced a > complicated statement by several simpler ones.
>> Since the code is currently GPL V3 there it does not >> qualify to be merged at the moment anyway.
> What should I change to make it possible to merge it into SAGE?
> Thanks, > Michael
Could you relicense it GPLv2+, i.e., "GPLV2 or at the users option any later version of the GPL."
Am Dienstag, 7. April 2009 11:15:52 schrieb Michael Stoll:
> Am Monday 06 April 2009 19:09:38 schrieb William Stein: > > Could you relicense it GPLv2+, i.e., "GPLV2 or at the users option any > > later version of the GPL."
> OK, I'll do that next week, when I'm back in Bayreuth.
> Best, > Michael
It's now done. The current version also has a few bug fixes and is at the usual place.
Am Montag, 6. April 2009 13:06:26 schrieb John Cremona:
> Michael,
> Since you and I and Robert Miller will all be in Dagstuhl in May we > can perhaps sort this out there. By then (if not before) I will try > to see exactly what I would need in order to be able to use ratpoints > in mwrank (rather than adapting it, as I did before).
> John
OK.
When writing ratpoints-2.0, I tried to make it easy to use it as a black box by other programs (the old version was a stand-alone program, therefore had to be adapted). So I don't expect problems, unless you use it for more than searching for points. (I haven't looked at your code yet.)
> Am Montag, 6. April 2009 13:06:26 schrieb John Cremona:
>> Michael,
>> Since you and I and Robert Miller will all be in Dagstuhl in May we
>> can perhaps sort this out there. By then (if not before) I will try
>> to see exactly what I would need in order to be able to use ratpoints
>> in mwrank (rather than adapting it, as I did before).
>> John
> OK.
> When writing ratpoints-2.0, I tried to make it easy to use it as a black box
> by other programs (the old version was a stand-alone program, therefore had
> to be adapted). So I don't expect problems, unless you use it for more than
> searching for points. (I haven't looked at your code yet.)
In fact it will not be hard. My own class based on your old code
contains in addition to your data a pointer to a class called
point_processor, the pointer is called "curve". The class
point_processor is an abstract base class which only contains a
(virtual) function process(x,y,z), and the sieve/search class calls
this function on any (x:y:z) it finds. To use this, any class which
wants to search for points and have them processed as they are found
just has to be derived from point_processor and provide its own
process() function.
The process function returns an int which is interpreted by the
sieve/search as a flag saying "stop now". So the using class can
easily determine under which conditions to stop before the sieving is
finished. That did require recoding some of your sieving code, as in
all the loops (etc) you have to keep checking whether a flag (called
"halt_flag" in the code) is set.
Example 1 (used in searching for points on elliptic curves): if you
already know the rank, you can stop searching when the rank of the
points found is equal to that.
Example 2 (used in searching on quartics, i.e. homogeneous spaces in
the 2-descent): stop after the first point found.
I don't think there are more examples.
So what I would do to your code is add this functionality. Or you
could build it in, with some simpler point_processor options (which I
already have) called point_printer (which just prints thepoints as
they are found), point_counter (which keeps count of the points found,
and can be asked at any point what the count is). etc.
If you do want to look at my code, the relevant files in the mwrank
(or eclib) distribution are in the qcurves directory (in eclib),
sieve_search.h/cc, and they are used in mwprocs.h/cc (that is example
1).
2009/4/14 Michael Stoll <Michael.St...@uni-bayreuth.de>:
> Am Dienstag, 7. April 2009 11:15:52 schrieb Michael Stoll: >> Am Monday 06 April 2009 19:09:38 schrieb William Stein: >> > Could you relicense it GPLv2+, i.e., "GPLV2 or at the users option any >> > later version of the GPL."
>> OK, I'll do that next week, when I'm back in Bayreuth.
>> Best, >> Michael
> It's now done. The current version also has a few bug fixes and is at the > usual place.
Thanks!!
Some complaints.
1. The link at the beginning of this thread is broken:
Again, many thanks for GPL-v2+ your awesome program. We just tested building it on OS X, PPC OS X, Opteron Linux, Solaris x86 and Solaris Sparc. To get it to build on Opteron, OS X and Solaris x86 we had to #undef __SSE2__, but then it built and seems to work fine.
> 2009/4/14 Michael Stoll <Michael.St...@uni-bayreuth.de>: > > Am Dienstag, 7. April 2009 11:15:52 schrieb Michael Stoll: > >> Am Monday 06 April 2009 19:09:38 schrieb William Stein: > >> > Could you relicense it GPLv2+, i.e., "GPLV2 or at the users option any > >> > later version of the GPL."
> >> OK, I'll do that next week, when I'm back in Bayreuth.
> >> Best, > >> Michael
> > It's now done. The current version also has a few bug fixes and is at the > > usual place.
> Thanks!!
> Some complaints.
> 1. The link at the beginning of this thread is broken:
I have no longer access to the Jacobs server. I guess I should tell them to redirect everything to my new web address.
Robert could have asked me, though.
> 3. Can you put everything in a directory? I just did
> wstein@bsd:~/Desktop$ tar zxvf ratpoints-2.1.1.tar.gz > Makefile [...] > gpl-2.0.txt
> and it clobbered my Desktop.
Done.
> Again, many thanks for GPL-v2+ your awesome program. We just tested > building it on OS X, PPC OS X, Opteron Linux, Solaris x86 and Solaris > Sparc. To get it to build on Opteron, OS X and Solaris x86 we had to > #undef __SSE2__, but then it built and seems to work fine.
They probably use different notation for the SSE instructions. It shouldn't be too hard to find out and adapt the definitions in rp-private.h (after #ifdef USE_SSE) accordingly to make it work.
> > When writing ratpoints-2.0, I tried to make it easy to use it as a black > > box by other programs (the old version was a stand-alone program, > > therefore had to be adapted). So I don't expect problems, unless you use > > it for more than searching for points. (I haven't looked at your code > > yet.)
> In fact it will not be hard. My own class based on your old code > contains in addition to your data a pointer to a class called > point_processor, the pointer is called "curve". The class > point_processor is an abstract base class which only contains a > (virtual) function process(x,y,z), and the sieve/search class calls > this function on any (x:y:z) it finds. To use this, any class which > wants to search for points and have them processed as they are found > just has to be derived from point_processor and provide its own > process() function.
> The process function returns an int which is interpreted by the > sieve/search as a flag saying "stop now". So the using class can > easily determine under which conditions to stop before the sieving is > finished. That did require recoding some of your sieving code, as in > all the loops (etc) you have to keep checking whether a flag (called > "halt_flag" in the code) is set.
This is pretty close to the structure ratpoints is using now. The call to the library function has the form
total = find_points(&args, process, (void *)info);
Here args is a structure containing the arguments that need to be passed (coefficients of the polynomial, height bound, values for the various parameters like number of primes to be used in the two sieving stages) and process is a function like
typedef struct {...} data;
int process(long x, long z, const mpz_t y, void *info0, int *quit) { data *info = (data *)info0;
(...)
return(1);
}
When find_points finds a point, it calles "process" with the numerator and denominator of the x-coordinate (as longs), the y-coordinate (as an gmp integer), the pointer "info" that was passed to find_points, and a pointer to an int. The return value is used to increment the eventual return value of find_points ("total" in the example above). If "process" sets *quit to something nonzero, find_points aborts the search (at least it hopefully does so now, after fixing a bug found by Robert Miller). The "info" pointer can be used to store information that should persist between calls to "process", for example a basis of the free part of the subgroup generated by the points found so far (Example 1 below). For Example 2 below, you just do "*quit = 1", then the search stops after the first point is found and processed.
> Example 1 (used in searching for points on elliptic curves): if you > already know the rank, you can stop searching when the rank of the > points found is equal to that.
> Example 2 (used in searching on quartics, i.e. homogeneous spaces in > the 2-descent): stop after the first point found.
> I don't think there are more examples.
> So what I would do to your code is add this functionality. Or you > could build it in, with some simpler point_processor options (which I > already have) called point_printer (which just prints thepoints as > they are found), point_counter (which keeps count of the points found, > and can be asked at any point what the count is). etc.
I would think it is only necessary to set up a C++ wrapper that interfaces to find_points. That should be pretty easy to do.
> If you do want to look at my code, the relevant files in the mwrank > (or eclib) distribution are in the qcurves directory (in eclib), > sieve_search.h/cc, and they are used in mwprocs.h/cc (that is example > 1).
Michael, Thanks a lot for the explanation. As it happens, while you
were typing your message I had just successfully built ratpoints-2.1.1
and read the very detailed instructions, so I had just seen that you
already had the facilities which I wanted. thanks!
As you say, it should not be hard to write a C++ wrapper (which will
have to convert between gmp integers and NTL ZZ's, since that is what
my code uses) and get this into mwrank & eclib.
Also, since Robert Miller is rapidly rewriting all of mwrank in Sage
(as far as I can tell) he'll be calling ratpoints directly from within
Sage. I would not mind at all if mwrank's own days were numbered...
and hope that we can get everything we have done on higher descents,
including all Tom Fisher's GenusOneModel code, into Sage too.
John
2009/4/15 Michael Stoll <Michael.St...@uni-bayreuth.de>:
> Am Dienstag, 14. April 2009 19:16:31 schrieb John Cremona:
>> > When writing ratpoints-2.0, I tried to make it easy to use it as a black
>> > box by other programs (the old version was a stand-alone program,
>> > therefore had to be adapted). So I don't expect problems, unless you use
>> > it for more than searching for points. (I haven't looked at your code
>> > yet.)
>> In fact it will not be hard. My own class based on your old code
>> contains in addition to your data a pointer to a class called
>> point_processor, the pointer is called "curve". The class
>> point_processor is an abstract base class which only contains a
>> (virtual) function process(x,y,z), and the sieve/search class calls
>> this function on any (x:y:z) it finds. To use this, any class which
>> wants to search for points and have them processed as they are found
>> just has to be derived from point_processor and provide its own
>> process() function.
>> The process function returns an int which is interpreted by the
>> sieve/search as a flag saying "stop now". So the using class can
>> easily determine under which conditions to stop before the sieving is
>> finished. That did require recoding some of your sieving code, as in
>> all the loops (etc) you have to keep checking whether a flag (called
>> "halt_flag" in the code) is set.
> This is pretty close to the structure ratpoints is using now. The call to the
> library function has the form
> total = find_points(&args, process, (void *)info);
> Here args is a structure containing the arguments that need to be passed
> (coefficients of the polynomial, height bound, values for the various
> parameters like number of primes to be used in the two sieving stages) and
> process is a function like
> typedef struct {...} data;
> int process(long x, long z, const mpz_t y, void *info0, int *quit)
> { data *info = (data *)info0;
> (...)
> return(1);
> }
> When find_points finds a point, it calles "process" with the numerator and
> denominator of the x-coordinate (as longs), the y-coordinate (as an gmp
> integer), the pointer "info" that was passed to find_points, and a pointer to
> an int. The return value is used to increment the eventual return value of
> find_points ("total" in the example above). If "process" sets *quit to
> something nonzero, find_points aborts the search (at least it hopefully does
> so now, after fixing a bug found by Robert Miller). The "info" pointer can be
> used to store information that should persist between calls to "process", for
> example a basis of the free part of the subgroup generated by the points
> found so far (Example 1 below). For Example 2 below, you just do "*quit = 1",
> then the search stops after the first point is found and processed.
>> Example 1 (used in searching for points on elliptic curves): if you
>> already know the rank, you can stop searching when the rank of the
>> points found is equal to that.
>> Example 2 (used in searching on quartics, i.e. homogeneous spaces in
>> the 2-descent): stop after the first point found.
>> I don't think there are more examples.
>> So what I would do to your code is add this functionality. Or you
>> could build it in, with some simpler point_processor options (which I
>> already have) called point_printer (which just prints thepoints as
>> they are found), point_counter (which keeps count of the points found,
>> and can be asked at any point what the count is). etc.
> I would think it is only necessary to set up a C++ wrapper that interfaces to
> find_points. That should be pretty easy to do.
>> If you do want to look at my code, the relevant files in the mwrank
>> (or eclib) distribution are in the qcurves directory (in eclib),
>> sieve_search.h/cc, and they are used in mwprocs.h/cc (that is example
>> 1).
>> John
> Michael
> --
> Michael Stoll * http://www.mathe2.uni-bayreuth.de/stoll/ > Mathematisches Institut * Universität Bayreuth * 95440 Bayreuth, Germany
> Michael.St...@uni-bayreuth.de
