On Thu, Mar 12, 2009 at 3:03 AM, Robert Bradshaw
<[email protected]> wrote:
> On Mar 12, 2009, at 2:15 AM, William Stein wrote:
>
>> On Thu, Mar 12, 2009 at 1:46 AM, Dag Sverre Seljebotn
>> <[email protected]> wrote:
>>>>
>>>> This could be very useful for debugging things, but it implies
>>>> there's a single, correct way that the % and // operators behave.
>>>>
>>>> The problem is that sometimes I want to run code with Python
>>>> semantics (e.g. I'm quickly cythonizing a file) and sometimes I want
>>>> to run code with C semantics (e.g. I'm doing linear algebra mod p,
>>>> and don't want the overhead of fixing the sign). And perhaps I'm to
>>>> demanding, but I want to be able to use % in both places rather than
>>>> know some obscure function call.
>>>>
>>> Perhaps you could ask the Sage list to get some more input of what
>>> the
>>> typical expectations to Cython are?
>>>
>>> (Also if you work in Z_p, could you not use unsigned ints? Then you
>>> don't get the overhead? Though I'm avoiding unsigned types like the
>>> plague myself after I figured out that range(-n, n) is empty if n is
>>> unsigned :-))
>>
>> If you compute the sum of x and y mod p by doing "(x+y)%p", then the
>> time is dominated by the % operation, which can easily be nearly 10
>> times longer than +. Now imagine doing linear algebra, where you take
>> dot products, etc., and do lots of mod p arithmetic. If you dot two
>> vectors with n entries in the naive way you end up doing n %p's, which
>> is very expensive. Now imagine that you represent the entries of your
>> vectors as C ints between -p/2 and p/2. Then you can very often do
>> much of the dot product and only have to do very few mods, since
>> frequently when you add up a bunch of numbers between -(p/2)^2 and
>> (p/2)^2, they are likely to not overflow. The sum will be close to 0
>> because of cancellation.
>
> I was about to answer the very same thing then this email came in.
That's probably because you explained it to me once :-)
> One of the things that drives a lot of my optimizations in Cython has
> been the maxim that the obvious way should be the fast way, and I
> especially want to avoid having to resort to tricks to "fool" the
> compiler to get maximum speed. (Of course in this case we're talking
> about only a 5% or so difference, assuming no branching). I like the
Are you sure it's a difference of 5%?
I just tried these two programs:
main() {
int n = -1, m = 16, k, a=0;
for(k=1;k<100000000;k++) {
a = n%k + (a<0)?k:0;
}
}
and
main() {
int n = -1, m = 16, k, a=0;
for(k=1;k<100000000;k++) {
a = n%k;
}
}
and the first takes 22% longer than the second.
-- William
_______________________________________________
Cython-dev mailing list
[email protected]
http://codespeak.net/mailman/listinfo/cython-dev
