#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 | a2b31ca5ec86eaed275a854e41cb5fd7a3ce5c95
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by leif):
Replying to [comment:7 vdelecroix]:
> I confirm that there is no difference between "ii = i*i" and "ii -= 2*i
+ 1".
There of course is; just look at what the (C) compiler produces from it.
(I don't know what Cython itself does; it may optimize it, but may also
further obfuscate the code.)
On older machines, presumably any 32-bit processor [we support],
multiplication (or squaring) is more expensive than addition, increment,
and/or a shift. (And its cost depends on the number of 1-bits in the
multiplicands.)
> Anyway, I am pretty sure that this is the kind of optimization that gcc
takes care of with the option "-O3".
Nope, you have to be more explicit. It of course does some strength
reduction, e.g. replacing multiplication/division by powers of two by
shifts, additions or nice addressing modes etc., but you cannot expect it
to run a theorem prover... ;-)
--
Ticket URL: <http://trac.sagemath.org/ticket/16374#comment:17>
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.
