1
$\begingroup$

Write code for a modified version of the Grade School addition algorithm that adds the integer one to an m-digit integer. Thus, this modified algorithm does not even need a second number being added. Design the algorithm to be fast, so that it avoids doing excessive work on carries of zero.

I encountered this question looking over last year's final for my algorithms course. I'm not really sure how to answer it, although it seems like it isn't a very challenging question.

$\endgroup$

closed as unclear what you're asking by D.W., David Richerby, R B, Nicholas Mancuso, Hoopje Dec 29 '14 at 13:09

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Do you have some ideas? I'm sure you are able to implement the algorithm somehow; where did you get stuck while trying to make it faster? $\endgroup$ – Raphael Dec 18 '14 at 21:05
0
$\begingroup$

To slightly expand on @greybeard's answer, here are a few hints:

  1. Start adding from the right, as usual.
  2. When can you stop? Obviously, when you don't have a carry. When will that happen?
  3. When do you have to look at the next digit? Obviously, when you have a carry. When will that happen?

Challenge: show that the average number of steps this algorithm will take on an $m$-digit number represented in base $b$ is less than $b/(b-1)$.

$\endgroup$
  • $\begingroup$ How would you write such in a programming language though. You speak as if you can access the bits of the number like it's an array. If you could isn't it faster to start from the LSB. iterate through every bit until you find the first 0 bit. invert that bit. $\endgroup$ – Tobi Alafin Dec 29 '16 at 8:21
0
$\begingroup$

In a positional number system, there is one highest digit; every other has a successor in the set of digits. At the (low-significant) end of the sequence of digits (the integer's representation), there is either one of those other digits, or a sequence of that highest one.

$\endgroup$

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