 Find Repeating Part of a Fraction
This function takes two parameters, the numerator and denominator of a fraction, and determines the repeating part of the fraction (if one exists).
The logic is simple: After removing any part of the result that is a whole number, it begins dividing the denominator into the numerator and tracking the remainder after each digit. If the remainder becomes 0, then the function is done. Otherwise, when a remainder repeats, it has found the repeating part.
Because Perl treats all numbers as floating-point numbers, the easiest way to truncate a number to its integer part is to sprintf() it into a string using the "%d" conversion.
Source Code
1. # use sprintf to truncate to an integer
2.
3. sub idiv {
4. sprintf("%d",($_[0] / $_[1]));
5. }
6.
7. # usage is "repeat.pl num denom"
8.
9. $num = shift @ARGV;
10. $denom = shift @ARGV;
11.
12. # first display and chop off integer part
13.
14. $div = idiv($num,$denom);
15. $currdecimal = "$div";
16. $num = $num - ($div * $denom);
17. $currdecimal .= "." unless ($num == 0);
18. $digits = 0;
19.
20. until ($num == 0) {
21.
22. # store where we saw this remainder
23. $array[$num] = $digits;
24.
25. # calculate next digit
26. $num *= 10;
27. $div = idiv($num,$denom);
28. $currdecimal .= $div;
29. ++$digits;
30.
31. # find new remainder
32.
33. $num = $num - ($div * $denom);
34.
35. # did we see this before?
36. if ($array[$num]) {
37. $repeatlen = $digits - $array[$num];
38. $plural = "s" unless ($repeatlen == 1);
39. print ("$currdecimal: last $repeatlen"
40. . " digit$plural repeated\n");
41. last;
42. }
43. }
44.
45. if ($num == 0) {
46. print ("$currdecimal\n");
47. }
Suggestions
The program displays its results in two places, lines 39-40 and line 46. How does it guarantee that one-and only one-of those will be executed? What is the meaning of an entry in the @array array? What can you say about the relative values of $num and $denom at the start of the until loop on line 20? What guarantee is there that line 28 will add only one more digit to $currdecimal? What does it mean if the if on line 36 is true?
Hints
Walk through the code with the following inputs:
A result with no fractional part: $num == 8 $denom == 2 A result that has a non-repeating fractional part: $num == 3 $denom == 4 A result with a single repeating digit, and a few leading zeros: $num == 1 $denom == 300 A result with a two-digit repeating part: $num == 1 $denom == 11
Explanation of the Bug
The bug is in the if on line 36:
if ($array[$num]) {
The code uses the automatic support for sparse arrays in Perl. It indexes into $array using the current remainder, and knows it has found a repeat when the entry already exists. The problem is that what is being stored in the array for a given remainder is the digit number (with the first digit after the decimal place considered number 0) where the remainder previously occurred. Thus, for the first remainder, the value in the array will be 0 (just consider the effect of line 18 and then line 23 during the first iteration of the loop). This means the program will not notice a repeat if that remainder previously happened in the first fractional digit. Hint #4, 1 divided by 11, shows this; the program will report that the result is 0.090 with the last two digits repeating, instead of 0.09 with the last two digits repeating.
This bug would either be A.logic or B.expression, depending on whether the programmer made this mistake "intentionally" (realizing that the code was checking the value, but not realizing that it could ever be 0) or not. The fix is to change line 36 to read as follows:
if (defined($array[$num])) {
| 
