Task — Decimal string

You are given numerator and denominator $N and $D. Write a script to convert the fraction into decimal string. If the fractional part is recurring then put the recurring part in parenthesis.

Examples

Example 1
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)'

Analysis

This is not as easy as it sounds! There are a couple of approaches I considered:

• An analytical solution assisted by Ron Knott's excellent analysis, and
• A pragmatic approach, generating the decimal string to a lot of digits and looking for a repeating pattern.

I played with the first method and decided it was really quite complicated, and concluded that the second solution would probably be easier to code. I'm not sure whether that was the right decision.

However, my method starts by generating the required quotient to 1000 decimal places, using use Math::BigFloat. I then run 3 nested loops:

• over the starting digit of recurrence,
• over the length of the recurrence, and
• over the number of repeats.

The longest recurring sequence this will find is 500 digits, which will recur twice in my 1000 digit quotient. If no such recurrence is found, my code gives up with an appropriate message.

However, despite the 3 nested loops, which I would normally avoid, it completes in negligible time.

Note that I do restrict the numerator and denominator to (positive or negative) integers: the algorithm works for non-integers but quickly needs even more than 1000 digits of precision in the quotient.

The code caters for special cases $D == 0 and $D == $N == 0, and for either or both $N and $D being negative.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-03-29
use utf8;     # Week 106 - task 2 - Decimal string
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;
use Math::BigFloat;

decimal_string(1, 3);
decimal_string(1, 2);
decimal_string(5, 66);
decimal_string(315, 187);
decimal_string(99, -98);
decimal_string(1, 0);
decimal_string(0, 0);

sub decimal_string {
    
    my ($d, $denom, $frac, $frac_length, $good, $n, $num, $output, $pattern, $q_string, $quotient, $repeat_length, 
        $repeats, $s, $save_start, $sign, $start, $this, $whole);
    
    # initialise
    ($num, $denom) = @_;
    say qq[\nInput:  \$n = $num, \$d = $denom];
    if ($num != int($num) or $denom != int($denom)) {
        say qq[*** integers only, please];
        return;
    }
    $sign = ($num <= 0 xor $denom <= 0) ? '-' : '';
    ($num, $denom) = (abs($num), abs($denom));
    
    
    # special cases
    if ($denom == 0) {
        say qq[Output: ] . ($num != 0 ? qq[&#x221e;] : qq[indeterminate]);
        return;
    } elsif ($num == 0) {
        say qq[Output: 0.0];
        return;
    }
        
    # find quotient 1000 places
    Math::BigFloat->accuracy(1000);
    $num = Math::BigFloat->new($num);
    $denom = Math::BigFloat->new($denom);
    $quotient = Math::BigFloat->copy($num);
    $quotient->bdiv($denom);
    $q_string = $quotient->bstr;
    $q_string = substr($q_string, 0, -1);
    $good = 1;
    
    # a whole number
    if ($q_string =~ m|^(\d+)\.0+$|) {
        say qq[Output: $1.0];
        return;
    }
        
    # non-recurring
    if ($q_string =~ m|(.*?)(0*)$|  and length($2) >= $denom) {
        say qq[Output: $1];
        return;
    }
    
    # recurring
    $q_string =~ m|^([0-9]*?)\.([0-9]*)$|;
    ($whole, $frac) = ($1, $2);
    $good = 0;
    $frac_length = length($frac);
    
    # loop over start of repetition
    X: for $start (0 .. $frac_length - 1) {
        $save_start = $start;
        
        # loop over repeat length
        Y: for $repeat_length (1 .. int($denom)) {
            $pattern = substr($frac, $start, $repeat_length);
            
            # loop over number of repeats
            Z: for $repeats (1 .. 1000) {
                $s = $start + $repeats * $repeat_length;
                $this = substr($frac, $s, $repeat_length);
                last Z unless ($this eq $pattern or length($this) lt $repeat_length);
                
                # matches all the way
                $good = 1 unless $repeat_length * 2 > $frac_length;
                $output = qq[$sign$whole.] . substr($frac, 0, $save_start) . qq[($pattern)];
                last X;
            }
        }
    }
    
    if ($good) {
        say qq[Output: $output];
    } else {
        say qq[Output: ] . $sign . substr($q_string, 0, 50) 
            . qq[...\ndoes not repeat within 1000 digits];
    }
}

50 lines of code

I completed this challenge after the closing date
and it has not been submitted to GitHub

Output

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)

Input:  $n = 315, $d = 187
Output: 1.(6844919786096256)

Input:  $n = 99, $d = -98
Output: -1.0(102040816326530612244897959183673469387755)

Input:  $n = 1, $d = 0
Output: ∞

Input:  $n = 0, $d = 0
Output: indeterminate