Dear William,
On Mar 31, 5:05 pm, "William Stein" <[EMAIL PROTECTED]> wrote:
> I'm not a computer scientist either, but I was as an undergrad, and
> I learned in Computer Science 101
So you are definitely more computer scientist than i.
I never attended a computer science class. It is (or used to be)
possible in Germany to study maths without being in touch with
computer science.
> if the size of the input to an
> algorithm is n, then it is impossible to have better complexity
> than linear in n, since it takes n steps to *read in the input*.
This makes sense even to me.
In fact, my question, though not clearly formulated, concerned the
number of additions. I remembered that "divide and conquer" has some
advantages, but it seems i was mistaken that this was due to reducing
the number of additions.
I understood your example on computation of factorial that Mike's
balanced-summation-patch would only help me under the condition that
1. the elements of the list have about the same size
2. a sum is bigger than the summands
3. addition is most expensive if one summand is much bigger than the
other.
Since this condition doesn't hold in my application, i guess it is
best to just add one thing after the other.
Yours
Simon
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
