Interim Reports: Week 2

Mar 5, 2012 at 7:57 PM

Thought I'd add a new discussion instead of tagging on the earlier discussion.

I decided to tackle code kata #4 (Dyson Numbers) this week.  I found one error and I'd like to make a suggestion.

I started with a few very basic test cases: the first five examples in Wikipedia's Smallest N-Parasitic numbers table.  When I executed SmallestNParasiticNumber(1, 1), it threw an exception as expected, and SNPN(2, 2) yielded the correct result.  I was unable to test for SNPN(3,3), however, which leads me to my suggestion.  Due to the nature of this problem, I do not think any of the primitive data types (int, long, ulong) are sufficient to solve it.  Just looking at the table in Wikipedia, the majority of examples have far too many digits for these types.  I suggest using the Big Integer structure for this problem, but having a limit on the digit length to say 100, throwing a custom exception like DysonDigitLimitException.

The next two test cases led me to discover the one error.  SNPN(4,4) should have given the relatively short answer 102564, but instead gave an OverflowException.  After a quick debugging session, I found the function LeftDigit has a faulty implementation.  The carryDigit should not only be set to 0 and 1; it should be nTimesRightDigitPlusCarryDigit / 10.  This is a start, but I have a feeling more testing will reveal this may not be the optimal solution, specifically where nTimesRightDigitPlusCarryDigit == 10.

Coordinator
Mar 5, 2012 at 10:39 PM

The Dyson Numbers kata is a fun one. I originally wrote that code rather hastily one evening to show my son, David, how a computer program could be used to determine the smallest 2-parasitic number. (I also showed him how a circle of digits written on a piece of paper could be used to determine an ever increasing number of 2-parasitic numbers with an ever increasing number of digits.) Thanks for discovering some of the issues with the program. If you would like to share it, I look forward to seeing the improvements you make to the code.

Coordinator
Mar 6, 2012 at 12:52 AM

Seibel: When did you learn to program?

Knuth: I was a freshman at Case Institute of Technology. This was the fall of 1956 and during that quarter or semester they got a computer.

Seibel: This was the IBM 650?

Knuth: It was the 650, yeah. . . . One afternoon a guy from the lab went to the blackboard and was explaining to the three of us freshmen what this machine did. I found a manual for the machine and they had example ten-line programs. It seemed to me they were kind of stupid--it looked like there were ways to improve even those programs. . . . Anyway, I got to see if one of my little changes to the program would also work, and it did. So I said, "My goodness, this is pretty amazing. I'm only a freshman and I can do better than what was in this book--this might be something I have talent for." . . . Then I decided to write a little program to calculate the prime factors of a number. It was about 100 lines long. I would come in at night when nobody else was using the machine, and debug it. And I found more than 100 bugs in my 100-line program. But 2 weeks later I had a program that would find prime factors of any 10-digit number that you dialed into the console switches.

From Coders at Work: Reflections on the Craft of Programming by Peter Seibel, pp. 566-567