# Talk:Digital Roots

### From Progteam

I learned this rule almost as stated back in the days when arithmetic was actually taught in public schools. We called it casting out nines. Does that ring a bell you young'uns? The answer is the remainder when N is divided by 9, except that zero is replaced by 9 for the problem as formulated. So the only processing is to break N into a string of digits. After that, you iteratively add mod 9, and finish with a zero test. And I suppose that good manners suggests that you should verify that N>0.

Is it worth knowing the digit-by-digit mod rules, and how to reproduce them? This is elementary number theory. (And takes just a 5 minute lecture) --Siegel 17:01, 24 February 2008 (EST)

Hmm.. I tried everything I could think of as far as weird input goes... The only thing that got a runtime error was too big to be an integer, so I don't think it's that.

-- Melanie

## Stack Overflow

I'm assuming the error is that your recursion goes too deep. Try the same idea with an iterative approach. Really, you're just using tail recursion, so converting to an iterative version should be easy.

Looking further, this approach is fundamentally flawed because of assumptions on the input. For instance, a 10000 digit integer is fair game for this problem, but of course, an int isn't going to take anything bigger than 2 billion. Dealing with very large data is what this problem is testing. You need to a) find some way of representing arbitrarily large numbers, and b) find a way to process them without overflowing the stack.

New rule: No marking a problem as solved until PKU says so! :) ~Hjfreyer 15:40, 15 February 2008 (EST)