#16374: better two_squares, three_squares, four_squares for small input
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.3
Component: number theory | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/16374 | 17883e34f96f7f78f35f56bad527dcbaa728169d
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by leif):
Replying to [comment:29 jdemeyer]:
> I think the `long double` is overkill and would revert to using
`sqrt()`.
>
> 1. It decreases portability (`sqrtl()` is C99 so at least you need to
compile in C99 mode and not all systems have this function).
:-) Yes, C99 is only 15 years old. (Note that a lot of code in Sage
requires C99, and any recent GCC defaults to `-std=gnu99`.)
While there are (very few) platforms where the math library at least used
to lack some long double functions, I really wouldn't care here.
By the way, IMHO `i` and `j` should be `unsigned` rather than `unsigned
long`. (And as mentioned, I'd rather use `uint32_t` and `uint64_t`, or
even better, `uint_fast32_t` instead of the former.)
Note that in
{{{
#!python
j = <unsigned> sqrt[l](<[long] double> n)
j += 1 - j%2
}}}
`j` still cannot overflow, since `sqrt[l]()` returns `UINT_MAX` (which is
odd) for n close to `ULONG_MAX`.
However, I'd limit the input to values far below `ULONG_MAX` (more
precisely, `UINT64_MAX`) anyway.
[[BR]]
> 2. You will never want to call `two_squares` in this range (`2^53`)
anyway.
Yes, and I'd actually bail out above some cutoff.
[[BR]]
> 4. I have to check the details, but I think that `<unsigned long>
sqrt(<double> n)` is actually sufficiently precise that it computes the
exact integer square root.
? You mean `(unsigned long)sqrt((double)N) * (unsigned
long)sqrt((double)N) <= N` (for all N < 2^53^, say), or `(unsigned
long)sqrt((double)(N*N)) == N` (for all N < 2^26^, say)?
[[BR]]
I'm ok with using `sqrt()` if we limit the input accordingly (to at most
2^53^-1).
--
Ticket URL: <http://trac.sagemath.org/ticket/16374#comment:32>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
