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.

```
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)"
```

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.

This algorithm is based on the one found on the Wikipedia page about repeating decimals.

```
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 <--+
```

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

```
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.

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.

```
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.

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.

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.

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 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.

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.