5
$\begingroup$

I would be interested in some References (books or articles) concerning an answer to the following question :

what is more difficult to calculate from the viewpoint of a computer : the "sum" or the "maximum" of a finite set of numbers ?

My guess is that "sum" and "maximum" are of the same level of difficulty, but I would like very much to know References concerning this question.

Thank you in advance.

George

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Not a research-level theoretical computer science question. $\endgroup$
    – Dave Clarke
    Dec 3, 2010 at 11:40
  • 4
    $\begingroup$ @Dave: But I guess it could be turned into a research-level question. Can we come up with a model that separates sum and max? For example, could we show that in certain models, computing the sum of $n$ $b$-bit numbers requires strictly more extra space (in addition to the read-only input tape and write-only output tape) than max? Or is the answer always trivial? $\endgroup$
    – Jukka Suomela
    Dec 3, 2010 at 12:09
  • $\begingroup$ What is the measure of difficulty your are interested in? What is the model of computation? $\endgroup$
    – Kaveh
    Dec 3, 2010 at 14:03
  • 1
    $\begingroup$ I like the answers more than the question ! I wish we could change the question to the one Jukka proposes and use Kaveh's answer ;) $\endgroup$
    – Suresh Venkat
    Dec 3, 2010 at 17:14

3 Answers 3

Reset to default
12
$\begingroup$

The sum of finitely many binary numbers can be computed in $TC^0$ and is in fact complete for $TC^0$ under $AC^0$ reductions.

The maximum of finitely many binary numbers can be computed in $AC^0$.

So from the circuit-complexity perspective, sum is more difficult.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Really? Could you please tell us how to compute the maximum of $n$ $n$-bit numbers in AC$^0$? $\endgroup$
    – slimton
    Dec 3, 2010 at 16:04
  • 7
    $\begingroup$ @slimton: Note first that we can compare two numbers in $AC^0$. Then here is how to compute the maximum of $n$ numbers $x_1,\dots,x_n$, each of $n$ bits. First we compare all pairs of numbers. Next we compute for each $x_i$ the AND of all tests $x_i \geq x_j$. For each bit of $x_i$ we take the AND with this and the bit. Now, all numbers that are not equal to the maximum has been zeroed out. Now take the bitwise OR of all these numbers. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Dec 3, 2010 at 16:36
1
$\begingroup$

From pure algorithmic PoV in both cases there are N-1 addition operations.

For a computer though MAX might be harder to perform as there is one additional branch - determining the index of the currently max number. In sum operation this is not needed as interim result is just reused on the next number.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I do not have to add even once for finding the maximum. $\endgroup$
    – Raphael
    Dec 3, 2010 at 12:57
  • $\begingroup$ Any comparison operation in effect does a subtraction and checks for 0 result. Subtraction is addition with different sign. Modern processors might do it differently but it all boils down to checking bits one against another and then branching based on the result (which i what I meant). Perhaps tried to say it in too few words. $\endgroup$
    – Георги Кременлиев
    Dec 3, 2010 at 14:25
  • $\begingroup$ The fact stands that for comparison I only have to check from the MSB downward to the first difference while for addition I have to look at all bits. This makes a difference. Comparing by subtracting is not a good implementation (in terms of TM). $\endgroup$
    – Raphael
    Dec 5, 2010 at 13:25
1
$\begingroup$

What machine model do you want to use?

On RM, both are equally hard if you assume that $+$ and $<=$ are equally expensive (common assumption).

On 1-TM, sum is slightly more expensive since we have to add all bits compared to comparing only the the most signifikant bits (up to the first difference).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy