Fraction to exact decimal

Question

Write a program or function that given two integers a, b outputs a string containing a decimal number representing the fraction a/b exactly.

If a/b is integer, simply output the value, without a decimal dot or leading zeroes:

123562375921304812375087183597 / 2777 -> 44494913907563850333124661
81 / 3 -> 27
-6 / 2 -> -3

If a/b is not integer but has a finite representation in base 10, output the value without leading or trailing zeroes (except a single zero before the dot):

1 / 2 -> 0.5
3289323463 / -250000000 -> -13.157293852

Finally, if and only if (so no 0.999...) a/b is not integer and does not have a finite representation, output the finite part followed by the repeating part in parenthesis. The repeating part must be as small as possible, and start as early as possible.

-1 / 3 -> -0.(3)
235 / 14 -> 16.7(857142)
123 / 321 -> 0.(38317757009345794392523364485981308411214953271028037)
355 / 113 -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)

Your program must work for all above examples in under 10 seconds on a modern desktop PC. Smallest program in bytes wins.

@DestructibleWatermelon This is possible in pretty much all languages, including Turing tarpits. (Those might struggle with the time limit though.) — Dennis, Commented Aug 9, 2016 at 5:46
@DestructibleWatermelon I was under the impression that most languages are turing complete. — orlp, Commented Aug 9, 2016 at 5:46
Can we safely assume the fraction won't be something like: 0.33333333333336333...? — brianush1, Commented Aug 9, 2016 at 5:50
This seems like a long-winded way of asking for solutions to PE26 ;) — Conor O'Brien, Commented Aug 9, 2016 at 6:24

Sp3000 · Accepted Answer · 2016-08-09 07:22:52Z

Python 2, 174 bytes

x,y=input()
a=abs(x)
b=abs(y)
r=a%b*10
L=[]
M=''
while~-(r in L):L+=r,;M+=str(r/b);r=r%b*10
i=L.index(r)
t=M[:i]+"(%s)"%M[i:]*(M[i:]>'0')
print"-%d."[x*y>=0:(t>'')+3]%(a/b)+t

I'm not quite convinced about the validity of this answer, but it's worked for the test cases above and other test cases I've thrown at it. It looks like a right mess though, so I'm sure there's plenty of room for golfing.

The initial setup takes absolute values of both arguments to ensure that we're dealing with nonnegative numbers (saving the sign calculation for later), and delegates the quotient part of the result to Python's arbitrary precision arithmetic. The fractional part is done with the grade-school division algorithm until we get a repeat in the remainder. We then look up when we last saw this repeat in order to get the period, and construct the string accordingly.

Note that the algorithm's actually quite slow due to the O(n) in operation, but it's fast enough for the examples.

Neil · Accepted Answer · 2016-10-11 17:25:16Z

Batch, 349 344 bytes

@echo off
set/ad=%2,i=%1/d,r=%1%%d
if not %r%==0 set i=%i%.&if %r% leq 0 set/ar=-r&if %i%==0 set i=-0.
set d=%d:-=%
set/ae=d
:g
if %r%==0 echo %i%&exit/b
set/ag=-~!(e%%2)*(!(e%%5)*4+1)
if not %g%==1 set/ae/=g&call:d&goto g
set/as=r
set i=%i%(
:r
call:d
if %r%==%s% echo %i%)&exit/b
goto r
:d
set/ar*=10,n=r/d,r%%=d
set i=%i%%n%

Edit: Saved 5 bytes by removing unnecessary characters. "Ungolfed":

@echo off
set /a d = %2
set /a i = %1 / d
set /a r = %1 % d
if not %r%==0 (
    set i=%i%.                  Decimal point is required
    if %r% leq 0 (
        set /a r = -r           Get absolute value of remainder
        if %i%==0 set i=-0.     Fix edge case (-1/3 = 0 remainder -1)
    )
)
set d = %d:-=%                  Get absolute value of divisor
set /a e = d
:g
if %r%==0 echo %i% & exit /b    Finished if there's no remainder
set /a g = gcd(e, 10)           Loop through nonrecurring decimals
if not %g%==1 (
    set /a e /= g
    call :d
    goto g
)
set /a s = r                    Save remainder to know when loop ends
set i=%i%(
:r
call :d
if %r%==%s% echo %i%)&exit/b
goto r
:d                              Add the next decimal place
set /a r *= 10
set /a n = r / d
set /a r %= d
set i=%i%%n%

I have no idea how any of this works, but I commend you for doing it in batch lmao — Alexander, Commented Aug 9, 2016 at 17:10

Brad Gilbert b2gills · Accepted Answer · 2017-07-14 00:47:57Z

4

Perl 6, 63 58 50 bytes

{->$a,$b {$a~"($b)"x?$b}(|($^a.FatRat/$^b).base-repeating(10))}

{->\a,$b {a~"($b)"x?$b}(|($^a.FatRat/$^b).base-repeating)}

{$/=($^a.FatRat/$^b).base-repeating;$0~"($1)"x?$1}

Test it

If you don't care that it will only work with denominators that fit into a 64 bit integer it can be shortened to just 43 bytes:

{$/=($^a/$^b).base-repeating;$0~"($1)"x?$1}

Expanded:

{
  # store in match variable so that we can
  # use ｢$0｣ and ｢$1｣
  $/ = (

    # turn the first value into a FatRat so that
    # it will continue to work for all Int inputs
    $^a.FatRat / $^b

  ).base-repeating;

  # ｢$0｣ is short for ｢$/[0]｣ which is the non-repeating part
  $0

  # string concatenated with
  ~

  # string repeat once if $1 is truthy (the repeating part)
  # otherwise it will be an empty Str
  "($1)" x ?$1
}

edited Jul 14, 2017 at 0:47

answered Aug 9, 2016 at 16:02

Brad Gilbert b2gills

13.3k1 gold badge18 silver badges36 bronze badges

\$\begingroup\$ The way you formatted your answer is confusing. You should remove your old programs, because right now it looks like a multi-line program. \$\endgroup\$
– mbomb007
Commented Jul 13, 2017 at 21:26
\$\begingroup\$ @mbomb007 The main reason I have for posting golfs is for marketing, and education of Perl 6. So I leave old versions in to show more of the language. That's also why I rarely post one until I have some sort of explanation in there. I have altered it so that the different examples are in different code blocks. \$\endgroup\$
– Brad Gilbert b2gills
Commented Jul 14, 2017 at 0:39
\$\begingroup\$ Old versions are always visible in the post's edit history. \$\endgroup\$
– mbomb007
Commented Jul 14, 2017 at 13:32
\$\begingroup\$ @mbomb007 Not if I wait to post until after trying several different ways to write it. \$\endgroup\$
– Brad Gilbert b2gills
Commented Jul 15, 2017 at 2:41
\$\begingroup\$ Then just edit one in every 5 minutes. \$\endgroup\$
– mbomb007
Commented Jul 15, 2017 at 3:46

Add a comment |

score 2 · Accepted Answer · 2016-08-09 21:22:43Z

Java, 625 605

Golfed code:

import static java.math.BigInteger.*;
String f(BigInteger a, BigInteger b){BigInteger[]r=a.divideAndRemainder(b);String s=r[0].toString();if(r[1].signum()<0)s="-"+s;if(!ZERO.equals(r[1])){s+='.';List<BigInteger>x=new ArrayList();List<BigInteger>y=new ArrayList();for(BigInteger d=TEN.multiply(r[1].abs());;){BigInteger[]z=d.divideAndRemainder(b.abs());int i=y.indexOf(z[1]);if(i>-1&&i==x.indexOf(z[0])){for(int j=0;j<i;++j)s+=x.get(j);s+='(';for(int j=i;j<x.size();++j)s+=x.get(j);s+=')';break;}x.add(z[0]);y.add(z[1]);if(ZERO.equals(z[1])){for(BigInteger j:x)s+=j;break;}d=TEN.multiply(z[1]);}}return s;}

Note: I count the static import as part of the function for golfing purposes.

This function starts out by getting the division result. It adds the integral portion and sign, if necessary. Then if there is a remainder, it performs base 10 long division. At each step, perform the division. Store the calculated digit and the remainder in two lists. If we encounter the same digit and remainder again, there is a repeated portion and we know what index it starts at. The code either adds the digits (no repeat) or the pre-repeat digits, then the repeated digits enclosed in parentheses.

This is a bit big mostly because of BigInteger. If the inputs did not overflow even a long then it could be a bit shorter. Still, I expect there are ways to improve this entry.

Ungolfed code with main method for testing:

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import static java.math.BigInteger.*;

public class FractionToExactDecimal {

  public static void main(String[] args) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "123562375921304812375087183597", "2777", "44494913907563850333124661" },
      { "81", "3", "27" },
      { "-6", "2", "-3" },
      { "1", "2", "0.5" },
      { "3289323463", "-250000000", "-13.157293852" },
      { "-1", "3", "-0.(3)" },
      { "235", "14", "16.7(857142)" },
      { "123", "321", "0.(38317757009345794392523364485981308411214953271028037)" },
      { "355", "113", "3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println(data[0] + " / " + data[1]);
      System.out.println("  Expected -> " + data[2]);
      System.out.print("    Actual -> ");
      System.out.println(new FractionToExactDecimal().f(new BigInteger(data[0]), new BigInteger(data[1])));
      System.out.println();
    }
  }

  // Begin golf
  String f(BigInteger a, BigInteger b) {
    BigInteger[] r = a.divideAndRemainder(b);
    String s = r[0].toString();
    if (r[1].signum() < 0) s = "-" + s;
    if (!ZERO.equals(r[1])) {
      s += '.';
      List<BigInteger> x = new ArrayList();
      List<BigInteger> y = new ArrayList();
      for (BigInteger d = TEN.multiply(r[1].abs());;) {
        BigInteger[] z = d.divideAndRemainder(b.abs());
        int i = y.indexOf(z[1]);
        if (i > -1 && i == x.indexOf(z[0])) {
          for (int j = 0; j < i; ++j)
            s += x.get(j);
          s += '(';
          for (int j = i; j < x.size(); ++j)
            s += x.get(j);
          s += ')';
          break;
        }
        x.add(z[0]);
        y.add(z[1]);
        if (ZERO.equals(z[1])) {
          for (BigInteger j : x)
            s += j;
          break;
        }
        d = TEN.multiply(z[1]);
      }
    }
    return s;
  }
  // End golf
}

Program output:

123562375921304812375087183597 / 2777
  Expected -> 44494913907563850333124661
    Actual -> 44494913907563850333124661

81 / 3
  Expected -> 27
    Actual -> 27

-6 / 2
  Expected -> -3
    Actual -> -3

1 / 2
  Expected -> 0.5
    Actual -> 0.5

3289323463 / -250000000
  Expected -> -13.157293852
    Actual -> -13.157293852

-1 / 3
  Expected -> -0.(3)
    Actual -> -0.(3)

235 / 14
  Expected -> 16.7(857142)
    Actual -> 16.7(857142)

123 / 321
  Expected -> 0.(38317757009345794392523364485981308411214953271028037)
    Actual -> 0.(38317757009345794392523364485981308411214953271028037)

355 / 113
  Expected -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)
    Actual -> 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168)

Nice! I think you can save a few bytes by making this a function that returns a string, and by removing that one space in a, BigInteger. I also think you could alias BigInteger.TEN and BigInteger.ZERO. — FryAmTheEggman, Commented Aug 9, 2016 at 21:07
@FryAmTheEggman thanks, I didn't realize the static import saved space over the more verbose references. It does. I also found a few other things I had missed, such as while (true) -> for (;;) which also allowed me to put stuff in the for initializer, saving another byte. — user18932, Commented Aug 9, 2016 at 21:23
First, how about extending BigInteger? Second, a repeated remainder is enough to show it repeats; if you limit the input to int you can use an int[] with the remainder as index and the index as value, if that makes sense. — JollyJoker, Commented Aug 10, 2016 at 7:15
@JollyJoker extending BigInteger would require writing a whole class to try to save space, and I seriously doubt the tradeoff would work. Plus, I cannot restrict input. Anyway, there are eight instances of the text BigInteger in my code, and I don't see how adding more code to shrink them to a single character class name will pay off. And certainly adding code to deal with int[] (which BigInteger already does internally) will only bloat my answer. — user18932, Commented Aug 10, 2016 at 21:23
@JollyJoker it is also worth mentioning that unless I override every BigInteger method I call to return an instance of the subclass, I will need to add several casts which further bloat the code. On top of the wasted bytes for a subclass's overhead, that would certainly increase the code size. — user18932, Commented Aug 10, 2016 at 21:26

Jörg Hülsermann · Accepted Answer · 2016-10-16 12:23:02Z

1

PHP, 277 Bytes

list(,$n,$d)=$argv;$a[]=$n;$n-=$d*$r[]=$n/$d^0;!$n?:$r[]=".";while($n&&!$t){$n*=10;$n-=$d*$r[]=$n/$d^0;$t=in_array($n%=$d,$a);$a[]=$n;}if($t){$l=count($a)-($p=array_search(end($a),$a));echo join(array_slice($r,0,2+$p))."(".join(array_slice($r,2+$p,$l)).")";}else echo join($r);

answered Oct 16, 2016 at 12:23

Jörg Hülsermann

13.3k3 gold badges15 silver badges36 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Mathematica 198 bytes

i=Integer;t=ToString;a_~h~b_:=f[a/b];f@q_i:= t@q;
f@q_:=""<>{t@IntegerPart[q],".",RealDigits[FractionalPart[q]][[1]]//.{{x___,{k__i}}:> {x,"("<>(t/@{k})<>")"},{x__i,j___String}:>""<> {""<>t/@{x},j}}}

UnGolfed

(* hand over quotient of a, b to function f *)
h[a_, b_] := f[a/b];

(* if the quotient is an integer, return it as a string *)
f[q_Integer] := ToString@q;

(* otherwise, return the integer part, followed by a decimal point ...*)
f[q_] := "" <> {ToString@IntegerPart[q], ".", 

   (* replacing the repeating part (if it exists) between parentheses *)
   RealDigits[FractionalPart[q]][[1]] //. {{x___, {i__Integer}} :> {x, "(" <>(ToString /@ {i}) <> ")"},

   (* and the non-repeating part (if it exists) without parentheses *)
   {x__Integer, i___String} :> "" <> {"" <> ToString /@ {x}, i}}}

Tests

h @@@ {{81, 3}, {-81, 3}, {1, 4}, {-13, 3}, {19, 7}, {3289323463, 25000}, {235, 14}, {1325, 14}}

{"27", "-27", "0.25", "-4.(3)", "2.(714285)", "131572.93852", "16.7(857142)", "94.6(428571)"}

Stack Exchange Network

Fraction to exact decimal

6 Answers 6

Python 2, 174 bytes

Batch, 349 344 bytes

Perl 6, 63 58 50 bytes

Expanded:

Java, 625 605

PHP, 277 Bytes

Mathematica 198 bytes

UnGolfed

Tests

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
number
rational-numbers
restricted-time
or ask your own question.

Linked

Hot Network Questions

Fraction to exact decimal

6 Answers 6

Python 2, 174 bytes

Batch, 349 344 bytes

Perl 6, 63 58 50 bytes

Expanded:

Java, 625 605

PHP, 277 Bytes

Mathematica 198 bytes

UnGolfed

Tests

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfnumberrational-numbersrestricted-time or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
number
rational-numbers
restricted-time
or ask your own question.