Re: [sage-devel] Bug in Heilbronn Matrix

[John Cremona]

I cannot think of a reason for computing Heilbronn matrices of such
large index, so you have one? And how does it perform for smaller n,
say 1000, 10000, 20000, ...?

Lastly, Sage-5.7 has been released so you should upgrade (but I am not
saying if any relevant code has changed between 5.4.1 and 5.7, as I
have not checked).

John

On 27 February 2013 11:32, Peng <tianpen...@gmail.com> wrote:
> Dear all,
>
> I've tried to compute Heilbronn Matrices for n=50000 in sage 5.4.1, but the
> following Error comes out when I run
>
> sage: H=HeilbronnMerel(50000)
>
> --------------------------------------------------------------------
>
> RuntimeError Traceback (most recent call last)
>
> /home/guests/sage-5.4.1/<ipython console=""> in <module>()
>
> /home/guests/sage-5.4.1/local/lib/python2.7/site-packages/sage/modular/modsym/heilbronn.so
> in sage.modular.modsym.heilbronn.HeilbronnMerel.__init__
> (sage/modular/modsym/heilbronn.c:5185)()
>
> /home/guests/sage-5.4.1/local/lib/python2.7/site-packages/sage/modular/modsym/heilbronn.so
> in sage.modular.modsym.heilbronn.HeilbronnMerel._initialize_list
> (sage/modular/modsym/heilbronn.c:5343)()
>
> RuntimeError: Floating point exception
>
> --------------------------------------------------------------------
>
> It seems to be a bug in sage when computing Heilbronn Matrices for large n.
> However, I even couldn't find out why this happens. Anybody can please help
> me handle with that? Thank you.
>
>
> Best regards!
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Peng]

Dear John Cremona,

Thanks for your reply.

For n=45000 or smaller, it works well and gives an output. Then the next number I tried is 50000 and this gave an Error. 

In sage 5.7, this doesn't work neither.

I even don't know yet why this happens exactly.

PS:

I'm trying to compute the modular Galois represtations of Ramanujan tau function using the algorithm by Johan Bosman, which requests a huge precision for q-expansion of modular forms used inside the code. Actually, this error happens when I ran Bosman's code and sage indicates that HeilbronnMere went wrong in this case.

[John Cremona]

Try asking Bosman directly; I don't know if he reads this list.

John

[David Loeffler]

The bug also occurs on Sage 5.7, and a quick-and-dirty bisection
script shows that n = 46341 does work and n = 46342 does not. Since
46341 is almost exactly the square root of 2^{31}, and the relevant
bits of code seem to use C int variables rather than Sage integers
(presumably for speed reasons), it looks like an integer overflow.

David

[Peng]

I've asked him in fact, but he is currently not working on it. 

Bosman's code certainly performs well on the case which has been done by him. This error occurs only on my computation, which seems too cumbersome as far as it goes. 

Anyway, thanks for all your advice.

[Peng]

That sounds quite reasonable. I try to read the code again and search a solution. Thank you very much.

[David Loeffler]

On 5 March 2013 06:54, Peng Tian <tianpen...@gmail.com> wrote:
> Dear David,
> You are right. I tried to change the data type of the code in sage, which is
> "int" type in the source code of SAGE and now I'm using "long int" instead.
> The previous error is gone and everything is working well now.
>
> Thanks a lot!
>
> Best regards!
> Peng
>

Dear Peng,

Using long ints is a sound temporary fix, I guess. It would have the
side-effect of making the small N cases slightly slower and more
memory-hungry, so it might be best to have two separate functions in
the code, one using ints and the other longs, and choose between them
according to whether N^2 > 2^{31} or not; we already do similar things
for some other related functions, e.g lift_to_sl2z(). You could even
write a patch for this and upload it to Sage's trac server; then
that'll prevent anyone else having this problem in the future.

In an ideal world we'd also want a third implementation that uses MPIR
arbitrary-precision integers; this will be necessary when N is
*really* big, i.e. N^2 > 2^{63}. But I suspect that nobody's going to
be calculating Heilbronn matrices for such big N for a long while yet.

David

[Robert Bradshaw]

Looking at the original error "RuntimeError: Floating point exception"
does raise some concerns about blindly switching to long int; if
there's floating point involved all ints can be represented exactly as
doubles, but not all longs. I have not, however, looked at at the code
at all. When this gets fixed in Sage I'd like to see an explicit check
for the limit rather than crashing deep in the bowels of the code (or
worse, returning a wrong answer due to rounding or something).

- Robert

[William Stein]

There's no floating point. I wrote this code in 2004, and it was some
of the first
Cython (Pyrex at the time) code I wrote... and it was back when computers were
pretty much all 32-bit.

William

[Robert Bradshaw]

I'm curious whence the "RuntimeError: Floating point exception,"
perhaps I should just go look at the code...

[Peng Tian]

No floating points have been involved in the code. The error should be caused by divide-by-zero. 

If N>46341, a product of two integers might be overflow and result in a negative number. Consequently, the range of a denominator would start from a negative integer and end at a positive number, and then the denominator would take the value of 0.

To change the data type of int can solve it entirely, I guess.