MI = Multiple Inheritance?
2008/6/3 Robert Bradshaw <[EMAIL PROTECTED]>:
>
> 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
-~----------~----~----~----~------~----~------~--~---
