New version of ratpoints
Michael Stoll
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).
The program is available from the usual URL
http://www.mathe2.uni-bayreuth.de/stoll/progams/ .
Best wishes,
Michael Stoll
--
Michael Stoll * http://www.mathe2.uni-bayreuth.de/stoll/
Mathematisches Institut * Universität Bayreuth * 95440 Bayreuth, Germany
Michae...@uni-bayreuth.de
Robert Miller
it be to upgrade to 2.1?
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).
>
> The program is available from the usual URL
> http://www.mathe2.uni-bayreuth.de/stoll/progams/.
>
> Best wishes,
> Michael Stoll
> --
John Cremona
> What version of ratpoints is included in mwrank? How difficult would
> it be to upgrade to 2.1?
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.
John
Robert Miller
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
mabshoff
On Apr 1, 3:30 pm, Robert Miller <rlmills...@gmail.com> wrote:
Hi,
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.
Cheers,
Michael
Michael Stoll
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
John Cremona
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 <Michae...@uni-bayreuth.de>:
Robert Miller
> bug in the gcc shipped with XCode 3.0 - I did not try any later
This also happens with the latest development prerelease of XCode.
>
> Cheers,
>
> Michael
William Stein
Could you relicense it GPLv2+, i.e., "GPLV2 or at the users option any later
version of the GPL."
-- William
Michael Stoll
> 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,
Robert Miller
I've implemented a rudimentary spkg and Cython interface to ratpoints,
which are available here:
http://sage.math.washington.edu/home/rlmill/ratpoints-2.1.spkg
http://sage.math.washington.edu/home/rlmill/ratpoints.patch
The spkg builds on sage.math, and you can do the following:
sage: from sage.libs.ratpoints import ratp
sage: ratp([1..6], 200)
PROCESS: found point [ 1 : 0 : 0 ]
PROCESS: found point [ 0 : 1 : 1 ]
PROCESS: found point [ 0 : -1 : 1 ]
PROCESS: found point [ -2 : 3 : 3 ]
PROCESS: found point [ -2 : -3 : 3 ]
PROCESS: found point [ 7 : 1296 : 6 ]
PROCESS: found point [ 7 : -1296 : 6 ]
7 points found
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.
Michael Stoll
> 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.)
John Cremona
> 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.)
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).
John
William Stein
>
> 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:
http://www.mathe2.uni-bayreuth.de/stoll/progams/
2. Consequently, Robert Miller was deeply confused for days because of
this page:
http://www.faculty.jacobs-university.de/mstoll/programs/index.html
which has no link to your new page or warning.
3. Can you put everything in a directory? I just did
wstein@bsd:~/Desktop$ tar zxvf ratpoints-2.1.1.tar.gz
Makefile
ratpoints.h
rp-private.h
primes.h
gen_find_points_h.c
gen_init_sieve_h.c
sift.c
init.c
sturm.c
find_points.c
main.c
rptest.c
testdata.h
testbase
ratpoints-doc.pdf
gpl-2.0.txt
and it clobbered my Desktop.
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.
-- William
william
Michael Stoll
> 2009/4/14 Michael Stoll <Michae...@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:
>
> http://www.mathe2.uni-bayreuth.de/stoll/progams/
Sorry for the typo (should be prog_r_ams, obviously). The "Programs" link from
http://www.mathe2.uni-bayreuth.de/stoll/
does work, however.
> 2. Consequently, Robert Miller was deeply confused for days because of
> this page:
>
> http://www.faculty.jacobs-university.de/mstoll/programs/index.html
>
> which has no link to your new page or warning.
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.
Michael Stoll
> > 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.
See the section on "How to use the library" in ratpoints-doc.pdf at
http://www.mathe2.uni-bayreuth.de/stoll/programs/ratpoints-doc.pdf .
> 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.
John Cremona
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 <Michae...@uni-bayreuth.de>: