Perl Weekly Challenge 106: Decimal String

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.

Example

Solutions

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

Perl

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

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.

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.

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.

Perl Weekly Challenge 106: Decimal String

Challenge

Examples

Discussion

Example

Solutions

Perl

AWK

Bash

C

Lua

Node.js

Python

Ruby