0
$\begingroup$

I imagine finding the closed form of an algorithm should yield fewer steps than the original. But in the case of a summation from 1 to n, I'm not sure if it actually does.

Here's the original sum

Sum(N)
   total = 0
   for x = 1 to N
       total = total + x
   ret total

Here's the closed form

Sum(N)
    ret N*(N-1)/2

I think the argument is that '*' is only a single operation vs many '+' operations, but I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition.

Please correct me if my above claims are incorrect. My questions are: Does the closed form in this particular case yield fewer steps? Is closed form intended to reduce number of operations on the machine itself, and does it ever do that?

Improve this question
$\endgroup$
5
  • $\begingroup$ Please let me know if you would like clarification, as I wrote this question rather hastily. $\endgroup$
    – Samie Bee
    Nov 8, 2017 at 16:53
  • $\begingroup$ "repeated addition" does not mean anything regarding efficiency. How many additions is the key point. Computing N*(N-1) does not require more than O(log N) additions, so doing O(N) additions as in the first loop is quite inefficient. $\endgroup$
    – chi
    Nov 8, 2017 at 17:17
  • $\begingroup$ Which machine model? Is multiplication a single-step operation? $\endgroup$
    – Raphael
    Nov 8, 2017 at 18:59
  • $\begingroup$ @chi interesting, would you explain how $N(N-1)$ can be computed in $\mathcal{O}(log N)$? $\endgroup$
    – Samie Bee
    Nov 9, 2017 at 1:58
  • $\begingroup$ @SamyBencherif Actually, it's $O(log^2 N)$, using standard long multiplication, as we do with pen & paper. We simply multiply each digit of $N-1$ with all the digits of $N$, and then sum everything. $\endgroup$
    – chi
    Nov 9, 2017 at 8:34

2 Answers 2

Reset to default
7
$\begingroup$

I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition.

Try being more imaginative. I'm pretty sure that you were taught at school how to calculate, say, $38\times 144$ without adding $144$ thirty-seven times.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You must be talking about using the distributive property to break the product into a sum of easier products (that can be done via left shift), right? $\endgroup$
    – Samie Bee
    Nov 9, 2017 at 1:56
  • $\begingroup$ @SamyBencherif That's one way, yes. There are also other algorithms for multiplication. $\endgroup$
    – David Richerby
    Nov 9, 2017 at 8:42
1
$\begingroup$

The complexity of the loop is roughly $\mathcal{O}(N n)$ where $n$ is the number of bits in N. The complexity of multiplication using the school book method is $\mathcal{O}(n^2)$ and there are better algorithms with complexity $\mathcal{O}(n^q)$ where $q<2$. Since $n < N$ it's clear that the multiplication is faster assymptotically.

Improve this answer
$\endgroup$
4
  • $\begingroup$ But don't you need to prove $n^q < Nn$? $\endgroup$
    – Samie Bee
    Nov 9, 2017 at 1:51
  • $\begingroup$ @SamyBencherif , I meant that even the school book method is faster because $n \times n < N n$ because $n < N$. $\endgroup$
    – jman
    Nov 9, 2017 at 2:00
  • $\begingroup$ Oh right. One more thing, how is $n<N$ when $n$ is the number of bits in $N$? $\endgroup$
    – Samie Bee
    Nov 9, 2017 at 2:32
  • $\begingroup$ $ n = \text{floor} \left( log_2 (N) \right) +1 $. You can also think of $n$ as the number of digits and the complexity estimate as the number of single digit operations. If the number of digits is greater than 2, then the number of digits is always less than the number ( 2 < 10, 3 < 100 , etc.). $\endgroup$
    – jman
    Nov 9, 2017 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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