0
$\begingroup$

Suppose $n_1$, $n_2$, $\dots$ $n_k$ are given natural numbers. Can we write the addition $\sum$ of these $k$ numbers in terms two other functions $f$ and $g$?

i.e. $\sum(n_1, n_2,\dots,n_k)=f(n_1, n_2,\dots,n_k)+g(n_1, n_2,\dots,n_k)$?

Clearly, the addition function needs $k-1$ steps to add the $k$ given natural numbers. But if we are able to get the functions $f$ and $g$ in such a manner that $f$ and $g$ can be evaluated for the $k$ numbers in one shot then addition of k number can be computed in two three steps.

Any help is highly solicited.

$\endgroup$
1
$\begingroup$

Sure,

$$f(x_1,x_2,\dots,x_n) = x_1+x_2+\cdots x_n\\ g(x_1,x_2,\dots, x_n) = 0$$

means that the sum of $f$ and $g$ gives you the sum of the natural numbers input.


I don't really understand, however, how you would like to sum up $k$ natural numbers in two or three steps, especially as $k$ becomes large. It is reasonable to expect that for larger values of $k$, it will become more difficult (will take more steps) to calculate the sum of $k$ numbers.

$\endgroup$
10
  • $\begingroup$ You gave most trivial answer and the function f cannot be evaluated in one shot. $\endgroup$
    – Fukuzita
    Jun 24 '14 at 7:32
  • $\begingroup$ Essential aim is to derive two other functions in such a manner that the time complexity can be reduced for addition when k is large. $\endgroup$
    – Fukuzita
    Jun 24 '14 at 7:34
  • $\begingroup$ @SkSarifHassan 2 points. One, you asked for 2 functions that will result in the sum of the input values. I provided them. Two, yes, my answer is trivial and in the second part of my answer, I explained to you that finding a function that can be evaluated in "one shot" is impossible, as summing $k$ numbers is more difficult for larger values of $k$. $\endgroup$
    – 5xum
    Jun 24 '14 at 7:34
  • $\begingroup$ Professor, do you mean there does not exists any functions $f$ and $g$ such that the complexity is get reduced? $\endgroup$
    – Fukuzita
    Jun 24 '14 at 7:36
  • $\begingroup$ I am not a professor, and I am not saying that, I am just saying that the complexity will not be constant (you clearly want it to be constant) $\endgroup$
    – 5xum
    Jun 24 '14 at 7:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.