Monday, October 12, 2009

Program to Find the Digital Root of an Integer


Problem: "The digital root of an integer n is defined as the result of summing the digits repeatedly until only a single digit remains. For example, the digital root of 1729 can be calculated using the following steps:

Step 1: 1+7+2+9 = 19
Step 2: 1+9 = 10
Step 3: 1+0 = 1

Because the total at the end of step 3 is the single digit 1, that value is the digital root.

Rewrite the DigitSum program shown in Figure 4-6 so that it calculates the digital root of the imput value." (Roberts ch 4, exercise 7).

Here's the code:

/*
* File: DigitalRoot.java
* Name: Chu
* Section Leader: Ambiguous. Probably Usman Akeju.
* -----------------------------

This program uses a while loop inside while loop to run integer n thru the DigitSum
program multiple times until you get to the digital root. The DigitSum program took advantage
of the fact that the remainder of n after getting divided by 10 equals the last digit
in the integer. This program uses that as the inner loop. Then after running through the inner
loop, the output of the inner loop is made to be equal to the integer temp, which is
evaluated as a condition of the outer while loop. This is what lets us feed the integer through
the DigitSum program over and over.
**/

import acm.program.*;

public class DigitalRoot extends ConsoleProgram {

public void run () {
println("This program finds the digital root of an integer.");
int n = readInt("Enter a positive integer: ");

//If the imput is one digit to begin with, print it; we're done.

if (n <=9) {
println("The digital root is " + n);
}

else {

int dsum = 0;
int temp = n;

//Outer loop; keeps running until we get a single-digit output.

while (temp > 9) {

n = temp;
dsum = 0;

/*Inner loop: Keeps finding the remainder after you divide n by 10 to
* find the sum of digits
*/

while (n > 0) {
dsum += n % 10;
n /= 10;
}

//Set temp to dsum so that dsum can get fed through the outer loop again.
temp = dsum;

}
println("The digital root is " + temp);

}
}
}

What the output looks like:

What made it tough:

1) A loop of loops:
As was mentioned in the question, this problem builds off an example program given in the text to sum the digits of any given integer, which is any one of the steps 1 through 3 in the explanation. The sample problem gave us what would be the inner while loop of this program. The trick was to create a loop of loops that would take the solution from step 1 and feed it back through the inner loop to find the output for step 2, and so on.

I had a go at it at first by writing it as three individual loops:


public class DigitalRoot extends ConsoleProgram {

public void run () {
println("This program finds the digital root of an integer.");
int n = readInt("Enter a positive integer: ");
int dsum = 0;
while (n > 0) {
dsum += n % 10;
n /= 10;
}

/*NEED: If dsum is > 10, send it back thru the while loop. (How?...)
If dsum < 10, print "The digital root is" + dsum.*/

int o = dsum;
dsum = 0;
while (o > 0) {
dsum += o % 10;
o /= 10;
}

int p = dsum;
dsum = 0;
while (p > 0) {
dsum += p % 10;
p /= 10;
}

println("The digital root is " + dsum);

}
}

The program worked only for inputs of 4 digits, since there are three loops. For a long time, I couldn't figure out how to get the output of one of the loops to cycle back up and go through the loop again.

2) Debugging:
Once I made up a loop of loops and used the temp variable (thanks to inspiration from the comments to Fib Seq), this problem gave me the damndest time when it came to debugging. For a long time after I sketched out the strategy and wrote my code, I'd run the program, enter the output, and got nothing; my program would just blink stupidly at me.

Usman showed me the clever tip to debug by printing lines of text at different stages of the program:

//DEBUG:
println("Entering OUTER loop: n= "+ n +" dsum= "+dsum +" temp= "+temp);
while (temp > 9) {
n = temp;
dsum = 0;

//DEBUG:
println("Entering INNER loop: n= "+ n +" dsum= "+dsum+" temp= "+temp);
while (n >= 0) {
dsum += n % 10;
n /= 10;
//DEBUG:
println(" End INNER loop: n= "+ n +" dsum= "+dsum+" temp= "+temp);
}

temp = dsum;
}

Inserting the debut text gave this output:

We had told the program to print text when a) it got to entering the outer loop, b) it entered the inner loop, and c) it exited the inner loop. Since the third line of text never got printed, that told me that the program was getting stuck somewhere in the inner loop. Specifically, it was getting stuck when it got to n = 0, since of the condition to keep the loop running was n>=0.


Here's what the debug code looks like when fixed:


Time to completion: I read the problem and worked on it for an hour every night last week.

Lingering questions: How come this took so damn long!

10 comments:

  1. Have you guys learned about functions yet? Functions not only make code easier to read, but also easier to write. Imagine you can call a function:

    int sumDigits(int n);

    so that you could call it:

    int dsum = sumDigits(n);

    instead of:

    while (n > 0) {
    dsum += n % 10;
    n /= 10;
    }

    That way, you can think of separate parts of the problem one at a time. It will probably just get easier as you do it more and have more tools available to you.

    ReplyDelete
  2. No functions yet, Jason, but I can see how that would have been useful. In a perverse way, it's fun how you have to twist your brain around to get a solution when you have limited tools to work with.

    ReplyDelete
  3. There's one way of shortening your code a bit (keeping with elegance). Your first "if" clause is redundant. Can you see why?

    ReplyDelete
  4. I did this one in Common Lisp also; if you have any questions about how it works, feel free to ask.

    http://gist.github.com/246954

    ReplyDelete
  5. The solution to this problem can be just 1 line:
    digital_root = 1 + ((number-1) % 9)

    9 is the magic number here. You should find a pattern after doing enough of those. Example:
    19 => 10 => 1 (9 stripped)
    29 => 11 => 2 (9 stripped)

    ReplyDelete
  6. fatty liver can cure fatty liver can cure fatty liver can cure

    Feel free to surf to my site - methodologies for investigating natural medicines for the treatment of nonalcoholic fatty liver disease (nafld)

    ReplyDelete
  7. I definitely wanted to post a word to be able to say thanks to you
    for the lovely steps you are posting here.
    My time intensive internet investigation has
    now been paid with pleasant facts and strategies to talk about with my close friends.
    I 'd declare that we visitors are unequivocally endowed to live in a superb site with so many outstanding people with valuable techniques. I feel extremely privileged to have encountered the webpage and look forward to plenty of more fabulous moments reading here. Thanks a lot again for all the details.

    My webpage sexverhaal gangbang **

    ReplyDelete
  8. hello there and thank you for your info – I've certainly picked up anything new from right here.
    I did however expertise a few technical issues using this site,
    as I experienced to reload the web site lots of times previous
    to I could get it to load correctly. I had
    been wondering if your web host is OK? Not that I am complaining,
    but slow loading instances times will very frequently affect
    your placement in google and can damage your high-quality score if ads and marketing with Adwords.
    Anyway I'm adding this RSS to my e-mail and can look out for a lot more of your respective
    fascinating content. Ensure that you update this again very soon.

    Review my site - Colon CLeanse COmplete REview

    ReplyDelete
  9. Hi, Neat post. There is an issue along with your website in web explorer, might test
    this? IE still is the marketplace leader and a good section of
    people will omit your excellent writing due to this problem.



    Take a look at my weblog - cheap laptops

    ReplyDelete
  10. Really good post. This is what I wrote: https://dgeekspot.wordpress.com/2015/11/17/digital-root-algorithm/

    ReplyDelete