On Jun 3, 2008, at 12:09 AM, Gary Furnish wrote:
>
> On Mon, Jun 2, 2008 at 11:41 PM, Robert Bradshaw
> <[EMAIL PROTECTED]> wrote:
>>
>> On Jun 2, 2008, at 12:55 PM, William Stein wrote:
>>
>>> On Mon, Jun 2, 2008 at 12:53 PM, Gary Furnish
>>> <[EMAIL PROTECTED]> wrote:
>>>>
>>>> -1. First, everything cwitty said is correct.
>>
>> More on this below.
>>
>>>> Second, if we start
>>>> using ZZ[sqrt(2)] and ZZ[sqrt(3)], then sqrt(2)+sqrt(3) requires
>>>> going
>>>> through the coercion system which was designed to be elegant
>>>> instead
>>>> of fast, so this becomes insanely slow for any serious use.
>>
>> The coercion system is designed to be elegant *and* fast. Writing
>> something like 1 + sqrt(2) is going to require the coercion system no
>> matter what we do, as is 1 + sqrt(2) + 1/2. Computing QQ(sqrt(2),
>> sqrt
>> (3)) may take a millisecond or two, but after that coercion into it
>> from ether ring will be fast.
>>
> As long as there are classes in pure python that use MI on the
> critical path that symbolics has to use, the argument that coercion
> was written to be fast makes no sense to me.
Not sure what you mean by "MI" here, could you explain. In any case,
just because coercion isn't as fast as it could be doesn't mean that
it's not written for speed and much faster than it used to be. Of
course there's room for improvement, but right now the focus is
trying to finish the new system (which isn't really that "new"
compared to the change made a year ago) in place.
>>>> Finally, this is going to require serious code duplication from
>>>> symbolics, so
>>>> I'm not sure what the big gain is over just using symbolics to do
>>>> this
>>>> in the first place.
>>
>> Number field element work completely differently than symbolics, I
>> see little if any code duplication.
>>
> Fair enough.
>>> Also, cwitty pointed out that
>>>
>>> sage: sum([sqrt(p) for p in prime_range(1000)])
>>>
>>> works fine in Sage now, but with your (and my) proposal,
>>> it would be impossible, since it would require constructing
>>> a ring of integers of a number field of degree 2^168..
>>
>> This is the biggest argument against such a proposal, and I'm not
>> quite sure how best to handle this. One would have to implement large
>> number fields over sparse polynomials, and only lazily compute the
>> ring of integers. Or, as John Cremona suggested, "train users." None
>> of the above are ideal.
>>
>> I would like to give my motivation for not having sqrt(2) be in SR:
>>
>> 1) Speed. I know you're working very hard to make symbolics much,
>> much faster than they currently are, but I still don't think it'll be
>> able to compete in this very specialized domain. Currently:
>>
>> sage: timeit("((1+sqrt(2))^100).expand()")
>> 5 loops, best of 3: 52.9 ms per loop
>>
>> sage: timeit("((1+sqrt(2)+sqrt(3))^50).expand()")
>> 5 loops, best of 3: 579 ms per loop
>> sage: sym_a = sqrt(2) + sqrt(3)
>> sage: timeit("((1+sym_a)^50).expand()")
>> 5 loops, best of 3: 576 ms per loop
>>
>> Compared to
>>
>>
>> sage: K.<a> = NumberField(x^2-2)
>> sage: timeit("((1+a)^100)")
>> 625 loops, best of 3: 48.4 µs per loop
>>
>> sage: K.<a> = NumberField(x^4 - 10*x^2 + 1)
>> sage: timeit("((1+a)^50)")
>> 625 loops, best of 3: 138 µs per loop
>>
>> That's over three orders of magnitude faster (and it's *not* due to
>> pexpect/interface overhead as the actual input and output are
>> relatively small). Making arithmetic involving a couple of radicals
>> fast should probably be the most important, especially as one starts
>> making structures over them.
>
> Symbolics isn't going to approach number field speed. I think we can
> do much better then maxima, but its not going to be that much better
> (maybe if we encapsulate number fields as a special case in SR)
I'd rather have them be a number field elements (with all the
methods, etc) over providing a wrapping in SR. Otherwise one ends up
with something like pari, where everything just sits in the same parent.
>> 2) I personally don't like having to sprinkle the "expand" and and/or
>> "simplify" all over the place. Now I don't think symbolics should be
>> expanded automatically, but stuff like (1+sqrt(2))^2 should be or
>> 1/(1
>> +i). It's like just getting the question back. (I guess I'm revealing
>> my bias that I don't think of it as living in SR, but rather a number
>> field...) On that note, I can't even figure out how to do simplify
>> "(sqrt(2)-3)/(sqrt(2)-1)" in the symbolics...as opposed to
>>
>> sage: K.<sqrt2> = NumberField(x^2-2)
>> sage: (sqrt2-3)/(sqrt2-1)
>> -2*sqrt2 - 1
>> sage: 1/(sqrt2-1)
>> sqrt2 + 1
>>
> Your going to have a hard time convincing me that the default behavior
> in Mathematica and Maple is wrong. This makes sense for number theory
> but not for people using calculus.
OK, this is a valid point, though the non-calculus portions (and
emphasis) of Sage are (relatively) more significant. Sage is not a
CAS, that is just one (important) piece of it.
Maple does
> 1/(1+I);
1/2 - 1/2 I
at least. Looking to the M's for ideas is good, but they should not
always dictate how we do things--none but Magma has the concept of
parents/elements, and Sage uses a very OO model which differs from
all of them. Why doesn't it make sense for Mathematica/Maple? I think
it's because they view simplification (or even deciding to simplify)
as expensive.
>> 3) The coercion system works best when things start as high up the
>> tree as they can, and the Symbolic Ring is like the big black hole at
>> the bottom that sucks everything in (and makes it slow). There is a
>> coercion from ZZ[sqrt(2)] (with embedding) to SR, but not the other
>> way around, and even trying to cast the other way is problematic. I'd
>> rather that matrix([1, 1/2, 0, sqrt(2)]) land in a matrix space over
>> the a number field (rather than over SR), and ZZ['x'].gen() + sqrt(2)
>> be an actual polynomial in x. Also, the SR, though very useful,
>> somehow seems less rigorous (I'm sure that this is improving).
>>
> When coercion is faster we can consider changing this.
Coercion speed is irrelevant to the issues I mentioned here... and as
coercion+number fields is *currently* faster than what you could hope
to get with SR (the examples above all involve coercion) it wouldn't
help your case either.
> My definition
> of fast is "<10 cycles if the parents are the same,
Python semantics tie our hands a bit here, but I think we're about as
close as we can get.
> no dictionary lookups if one parent is in the other for all common
> cases,
Would this mean hard-coding all common paths? Currently there is a
single dictionary lookup for common cases (and not a Python dict).
> otherwise reasonablely quick pure Cython code.
Yes, it should be fast, but only has to be done once and then it's
cached. Of course the code specific to the ring/elements is as fast
or slow as whoever wrote it.
> New and old coercion fail these
> tests of sufficiently quick, and I'm not waiting to finish symbolics
> until they do pass those tests.
Thanks for your concise definition--if you have any input of how to
make things faster without hard-coding tons of special cases I'd be
very glad to hear (though the current focus is getting things merged
back into the main sage branch before we focus on optimization again).
> My alternative option is lets throw in a flag, defaults to off
> (current behavior) that lets you turn on sqrt/powers as in number
> theory by default instead of SR. This makes the code perform as
> expected by end users, and advanced users can use number fields if
> they know they are appropriate. This is just largely a one if
> statement change in the dispatch of sqrt so this should be reasonably
> safe.
"Perform as expected" is what we disagree on, though I'd call us both
end- and advanced users. I generally dislike the idea of flags the
user sets that change behavior, but it's an option to consider.
- Robert
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
