0

If we consider an operation as the sum/division/substraction/multiplication between two single digit numbers, then the following was said in my class:

If we sum 2 numbers of n digits each, then we need n elementary operations. But I can't see how this is true, which means, I am misinterpreting something. Let's look at the following example:

576 + 917 = 1493

6+7 = 3 remains, 1 carried (1 operation)

7 + 1 + 1 = 9 remains (2 operations)

5+9=14 remains (1 operation)

Here we have 4 operation for the sume of 2 3-digit numbers. What exactly I am not doing wrong.

EDIT:

If we consider 999 + 888 you will get even more operations, in this case 5 in total.

imbAF
  • 295
  • Perhaps the instructor was thinking of binary numbers, though even there you have to be a little generous as regards what you call an "operation". Adding $0+0$ yields $0$ unless you had a carry from the prior stage in which case it yields $1$. For example. As another thought, in looking at the complexity of various things, it is common enough to ignore constants. Thus $10n$ and $n$ are effectively the same. – lulu Apr 26 '22 at 14:50
  • No binary.It was basis of 10 – imbAF Apr 26 '22 at 14:52
  • Of course, you can do the same "carry" argument with base $10$, it's just a little more tedious to write it out. $5+5$, say, is $0$ with a carry unless you were already carrying, in which case it is $1$ with a carry. And so on. – lulu Apr 26 '22 at 14:54
  • Yes but like, if you consider 999+ 888 , you are having 5 elementary operations, while the rule says I should have 3. – imbAF Apr 26 '22 at 14:56
  • Handling the carry is often not counted as a separate operation. The elementary operation is the adding together of two digits and a possible carry to give you one digit of output and a possible carry to the next operation. – Jaap Scherphuis Apr 26 '22 at 14:58
  • Please read what I said. I am counting the $5+5$ sum as a single operation, regardless of whether there was a carry or not. I'm just redefining "operation" to include a state by state treatment of the carry. That i, I am not counting the carry as an operation. Or perhaps your instructor meant $O(n)$ instead of $n$, so constants are not relevant. Why not ask your instructor what was meant? – lulu Apr 26 '22 at 14:58
  • @JaapScherphuis If that's the case then it would work. The logic that the sum of 2 n-digit numbers need n sums=n operations. I just thought that a computer, would spend time on adding the carrier to the next-high significant digits. But I guess it's not the case – imbAF Apr 26 '22 at 15:06
  • Sure, handling carries takes more time than ignoring them, but as lulu said, constant factors do not really matter. You can consider each digit to need two elementary operations to get 2n in total. Since computer usually work in binary, the elementary operations could be binary additions so there is a further factor $\log_2(10)$ on top of that. We don't need to worry about that. What we're interested in is the way it depends on $n$. If the number of digits grows, the time grows linearly, i.e. it is proportional to $n$. The actual proportionality constant matters little. – Jaap Scherphuis Apr 26 '22 at 15:50

0 Answers0