# Perl Weekly Challenge 106: Decimal String

by Abigail

## Challenge

You are given numerator and denominator i.e. $N and $D.

Write a script to convert the fraction into decimal string. If the fractional part is recurring then put it in parenthesis.

### Examples

Input: $N = 1,$D = 3
Output: "0.(3)"

Input: $N = 1,$D = 2
Output: "0.5"

Input: $N = 5,$D = 66
Output: "0.0(75)"


## Discussion

It is very tempting to just divide the given numbers, use sprintf to get lots of digits, and then search a pattern which repeats.

But in most languages, this is not going to work, due to floating point arithmetic not being precise enough. It goes wrong with surprisingly low numbers.

For instance, $$\frac{1}{23} = 0.\overline{0434782608695652173913}$$, but (in Perl), printf "%.40f" => 1/23 gives 0.0434782608695652173907151075149535301989. This disagrees with the real result shortly after the 20th digit, and we don't even get the repeating part correctly in its first occurance.

Instead, we have to perform long division by hand. First, we calculate $$I = \lfloor \frac{N}{D} \rfloor$$ and set $$N = N \bmod D$$. $$I$$ is going to be the integer part (the part before the decimal separator) of our solution.

Now, in a loop, we calculate the digits after the decimal separator. As an invariant, we have $$N < D$$. We'll have string $$s$$ which we use to create the decimal string — we initialize $$r$$ as $$I$$ followed by a dot (our decimal separator). We also keep track of a position $$p$$, and we initialize $$p$$ as the length of the string $$r$$. We'll also have a hash $$S$$; initially empty.

In each iteration of the loop, we first check whether $$N$$ is zero. If so, the decimal expansion of the fraction is finite, and $$r$$ is the final result of the process. Otherwise, we add $$N$$ to the hash $$S$$, with value $$p$$. We can now find a new digit to be added to $$r$$. We do this by calculating $$d = \lfloor \frac{10 \cdot N}{D} \rfloor$$. Since $$N < D$$, $$0 \leq d < 10$$. $$d$$ is the new digit to be added to $$r$$. We then update $$N$$ by setting $$N = 10 \cdot N \bmod D$$. The long division equivalent of this is process of dropping a zero, and then calculating how often $$D$$ divides the new number, and then subtracting that many times $$D$$ from the number. Finally, we increment $$p$$ by one — after all, we added a digit to $$r$$.

The guard of our loop is $$N \notin S$$; if we have an $$N$$ which is already in $$S$$, the decimal expansion of the fraction repeats, and the value of $$N$$ in $$S$$ is the position where it starts repeating (and it repeats till the end of $$r$$). We can use this value to place the required parenthesis.

### Example

      22/7     \0.318
0                      int (7 / 22) == 0, so 0 before decimal point
--
7                      N =       N  % D
66                     3 * D
--
4                     N = (10 * N) % D   <--+
22                    1 * D                 |
--                                          |  Same, so '18'
18                    N = (10 * N) % D      |  is the repeating
176                   8 * D                 |  part
---                                         |
4                   N = (10 * N) % D   <--+


## Solutions

Given the algorithm described above, the implementations in the various languages follows easily.

### Perl

sub long_division ($numerator,$denominator) {
my $BASE = 10; my$fraction = sprintf "%d." => $numerator /$denominator;
my $position = length$fraction;
my %seen;

$numerator %=$denominator;

while (!$seen {$numerator}) {
return $fraction unless$numerator;  # No repeating part.
$seen {$numerator} = $position;$fraction .= int ($BASE *$numerator / $denominator);$numerator =      $BASE *$numerator % $denominator;$position ++;
}

#
# Place parens around the repetend part.
#
$fraction .= ")"; substr$fraction, $seen {$numerator}, 0, "(";

return $fraction; }  Find the full program on GitHub. ### AWK Almost the same function in AWK. function long_division (numerator, denominator) { base = 10 fraction = sprintf ("%d.", numerator / denominator) position = length (fraction) delete seen numerator %= denominator while (!seen [numerator]) { if (!numerator) { return fraction } seen [numerator] = position fraction = fraction int (base * numerator / denominator) numerator = base * numerator % denominator position ++ } return substr (fraction, 1, seen [numerator]) "(" \ substr (fraction, 1 + seen [numerator]) ")" }  Find the full program on GitHub. ### Bash function long_division () { declare numerator=$1
declare denominator=$2 declare BASE=10 fraction=$((numerator / denominator)).
declare position=${#fraction} declare -a seen ((numerator %= denominator)) while ((!seen[numerator])) do if ((numerator == 0)) then return fi seen[$numerator]=$position fraction=$fraction$((BASE * numerator / denominator)) ((numerator = BASE * numerator % denominator)) ((position ++)) done fraction=${fraction::${seen[$numerator]}}$${fraction:{seen[numerator]}}$$
}


The Bash solution is very similar to the Perl solution, but it does have some syntax oddities. There are no named parameters in Bash, function arguments are available in $1, $2, etc. We cannot return strings from functions, so we write to a global variable, fraction.

The ((EXPR)) construct evaluates EXPR as arithmetic; $((EXPR)) also evaluates EXPR as arithmetic, but then it replaces the result in the expression it is. String concatenation is done by just placing the parts you want to concatenate next to each other, so fraction=$((numerator / denominator)). divides numerator by denominator (division in Bash is integer division), and concatenates that result with a dot (.), placing the result in fraction.

${#EXPR} evaluates EXPR, and then it takes the length of the result. To get a substring in Bash, you use the ${EXPR1:EXPR2:EXPR3} construct; this gets the substring of EXPR1, starting from position EXPR2, and with length EXPR3. If EXPR2 is empty (or zero), the substring is taken from the beginning of the EXPR1. If EXPR3 is empty (and the second colon is missing), the substring is taken till the end of EXPR1.

Therefore, the last statement places the parenthesis on the right places.

Find the full program on GitHub.

### C

A bit more work in C, but at the heart, still the same algorithm. Allocating memory takes work, and inserting parenthesis requires shifting characters one by one.

char * long_division (int numerator, int denominator) {
/*
* Calculate the maximum size of the result
*/
size_t fraction_len =
(numerator < denominator ? 1 :
floor (log10 (numerator / denominator))) +  // Digits before decimal dot
1 +  // Decimal dot
denominator    +  // Digits after decimal dot
2 +  // Parens
1;   // Trailing NUL byte
/*
* Allocate a string to hold the caption.
*/
char * fraction;
if ((fraction = (char *) malloc (fraction_len * (sizeof (char)))) == NULL) {
perror ("Mallocing string failed");
exit (1);
}

/*
* Add the first part of the result (upto, and including the dot)
*/
int position;
snprintf (fraction, fraction_len, "%d.%n",
numerator / denominator, &position);

/*
* Allocate memory to remember which numerators we have seen;
* initialize the entries to 0.
*/
number * seen;
if ((seen = (number *) malloc (denominator * (sizeof (number)))) == NULL) {
perror ("Mallocing seen structure failed");
exit (1);
}
for (number i = 0; i < denominator; i ++) {
seen [i] = 0;
}

/*
* We already have the part before the decimal dot; for the part
* behind it, we need numerator < denominator
*/
numerator %= denominator;
while (!seen [numerator]) {
if (!numerator) {
fraction [position] = '\0';
return (fraction);
}
seen [numerator] = position;
fraction [position] = BASE * numerator / denominator + '0';
numerator           = BASE * numerator % denominator;
position ++;
}

/*
* We now have to place the parens -- which means shifting
* part of the string created so far.
*/
fraction [position + 2] = '\0';
fraction [position + 1] = ')';
for (int i = position; i > seen [numerator]; i --) {
fraction [i] = fraction [i - 1];
}
fraction [seen [numerator]] = '(';
return (fraction);
}


Find the full program on GitHub.

### Lua

Pretty straight forward in Lua. Lua uses two dots as the concatenator operator.

function long_division (numerator, denominator)
local BASE     = 10
local fraction = math . floor (numerator / denominator) .. "."
local position = fraction : len ()
local seen     = {}

numerator = numerator % denominator

while (not seen [numerator]) do
if   numerator == 0
then return (fraction)
end
seen [numerator] = position;
fraction  = fraction .. math . floor (BASE * numerator / denominator)
numerator =                           BASE * numerator % denominator
position  = position + 1
end

return (fraction : sub (1,  seen [numerator]) .. '(' ..
fraction : sub (1 + seen [numerator]) .. ')')

end


Find the full program on GitHub.

### Node.js

Nothing special about the Node.js solution.

function long_division (numerator, denominator) {
let BASE = 10
let fraction = Math . floor (numerator / denominator) + "."
let position = fraction . length
let seen     = []

numerator %= denominator

while (!(numerator in seen)) {
if (!numerator) {
return (fraction)
}
seen [numerator] = position
fraction += Math . floor (BASE * numerator / denominator)
numerator =               BASE * numerator % denominator
position ++
}

return (fraction . substr (0, seen [numerator]) + "(" +
fraction . substr (   seen [numerator]) + ")")
}


Find the full program on GitHub.

### Python

Python has two division operators: / which does regular division, and // which does integer division. I wish more languages had different operators for the different types of division.

Taking a substring in Python is done by using a slice operation.

Blocks in Python are done by indentation. Hated by many, but I can appreciate the charm of it. It makes for more condense code.

def long_division (numerator, denominator):
BASE      = 10
fraction  = str (numerator // denominator) + "."
position  = len (fraction)
seen      = {}

numerator = numerator % denominator

while not (numerator in seen):
if numerator == 0:
return (fraction)
seen [numerator] = position
fraction  = fraction + str (BASE * numerator // denominator)
numerator =                 BASE * numerator  % denominator
position  = position + 1

return (fraction [:seen [numerator]]  + "(" +
fraction [ seen [numerator]:] + ")")


Find the full program on GitHub.

### Ruby

Just like in Python, in Ruby slices take the role of substrings.

def long_division (numerator, denominator)
base       = 10
fraction   = (numerator / denominator) . to_s + "."
position   = fraction . length
seen       = {}

numerator %= denominator

while !seen [numerator] do
if   numerator == 0
then return (fraction)
end
seen [numerator] = position
fraction += (base * numerator / denominator) . to_s
numerator =  base * numerator % denominator
position += 1
end

return (fraction [0 .. seen [numerator]   - 1] + "(" +
fraction [     seen [numerator] .. -1] + ")")

end


Find the full program on GitHub.