[GAP Forum] Different TwoSquares algorithm for large input?
Richard Graham
rickhg12hs at gmail.com
Mon Jul 26 20:16:48 BST 2010
Thanks for your response.
I suppose relying on integer factorization is the limiting factor (pun
intended). Sage does not appear to include Gap's factint, but still,
factorization of large numbers can be difficult.
Sage's four_squares function also relies on Gap's TwoSquares function, so it
too is limited.
I noticed that the four square problem is solved without factorization at:
http://www.alpertron.com.ar/FSQUARES.HTM
... and it can take very large inputs (I tried numbers greater than 2^1000).
I am wondering if the TwoSquares problem can be solved without integer
factorization.
Cheers!
Richard
On Mon, Jul 26, 2010 at 4:27 AM, Stephen Linton <sal at mcs.st-andrews.ac.uk>wrote:
> How large are your inputs? For me the existing algorithms seems to work
> quite well for really quite large numbers, limited mainly by integer
> factorisation.
> One obvious question is therefore: do you have the factint GAP package
> installed? It's part of the standard GAP distribution, but I don't know
> about SAGE.
>
> You can check with the GAP command
>
> InstalledPackageVersion("factint");
>
> which will give a version number or "fail.
>
> Steve Linton
>
> On 26 Jul 2010, at 00:51, Richard Graham wrote:
>
> > I use Sage for some recreational mathematics, which in turn uses Gap. I
> > would like to use the TwoSquares function with inputs that are large. Is
> > there perhaps another algorithm that could be used to handle large input?
> > Thanks.
> > _______________________________________________
> > Forum mailing list
> > Forum at mail.gap-system.org
> > http://mail.gap-system.org/mailman/listinfo/forum
>
>
More information about the Forum
mailing list