9
\$\begingroup\$

Given three integers N,D,R write a program to output Rth digit after the decimal point in the decimal expansion for a given proper fraction N/D.

\$\endgroup\$
3
  • \$\begingroup\$ Is it ok to write a function or do we have to provide a complete program? Also with Rth digit - do you want to have the Rth digit after the decimal point or the Rth digit in total? \$\endgroup\$
    – Howard
    Dec 29, 2013 at 9:37
  • 1
    \$\begingroup\$ Mat I suggest you include some test cases? \$\endgroup\$
    – DavidC
    Dec 29, 2013 at 16:14
  • 6
    \$\begingroup\$ This question seems underspecified. Since it is codegolf the shortest answer wins, however edge case behavior and precision requirements are not given. Need all answers report '0' for rational numbers (for example the 5th digit of 1/2)? What about fractions that would result in a number less than FLOAT_MIN in whatever language the answer is composed in? The assumption I make is that arbitrary precision and trailing zeros are required, but it would be nice if this were stated/refuted in the question. \$\endgroup\$
    – Kaya
    Dec 29, 2013 at 19:17

10 Answers 10

4
\$\begingroup\$

GolfScript 17

10\?@abs*\abs/10%

GolfScript can't handle real numbers well, but multiplying by powers of 10 is equivalent.

Here's an explanation and walkthrough with sample input, for any of you who are new to GolfScript, since I think this is a nice simple introduction:

59 -17 5
10\ #Place 10 on the stack and then switch the top 2 elements
-> 59 -17 10 5
? #Exponentiate
-> 59 -17 100000
@ #Rotate top 3 elements
-> -17 100000 59
abs #Take absolute value of top element
-> -17 100000 59
* #Multiply the top 2 elements
-> -17 5900000
\ #Switch top 2 elements
-> 5900000 -17
abs #Take absolute value of top element
-> 5900000 17
/ #Do integer division
-> 347058
10% #Place 10 on the stack and then take modulo
-> 8
\$\endgroup\$
4
  • \$\begingroup\$ Doesn't work with negative N or D, e.g. -1 3 1. \$\endgroup\$
    – Howard
    Dec 29, 2013 at 9:33
  • \$\begingroup\$ @Howard shoot good call. I've added 2 calls to abs. This edge case is now responsible for almost a third of the characters! Anybody got a shorter alternative? \$\endgroup\$
    – Ben Reich
    Dec 29, 2013 at 15:10
  • \$\begingroup\$ How does it handle 1 70000 3? 1 2 5? \$\endgroup\$
    – DavidC
    Dec 29, 2013 at 19:55
  • \$\begingroup\$ @DavidCarraher For 1 70000 3 it calculates 10^3/70000 using integer division, which is 0, as desired. Note that 1 70000 5 = 10^5/70000 = 1, as desired. Similarly, 1 2 5=10^5/2=0, since the decimal expansion of 1/2 has a 0 in the fifth decimal place. \$\endgroup\$
    – Ben Reich
    Dec 30, 2013 at 2:57
3
\$\begingroup\$

Java

static int digit(int N, int D, int R) {
    if (D < 0) D = -D;
    if (N < 0) N = -N;
    int Q=0;
    while (R-- > 0) {
        while (N >=D) N -=D;
        int P=N = ((N+N)<<1)+N;
        for (Q=P^P; N >D; N -=D) Q++;
        while (P >=D) P -=D;
        N = P<<1;
    }
    for (; N >= 0; N -=D) R++;
    return (Q<<1) + R;
}

This code

  • avoids multiplication and division
  • splits decimal digit in 5- and 2-digit (Q and final R) internally

Explanation

When dividing manually you get digits by multiplying remainders by 10 and comparing the results to multiples of the divisor

10 / 17 = Digit 0, Remainder 10 (x 10)
100 / 17 = Digit 5, Remainder 15 (x 10)
 150 / 17 = Digit 8, Remainder 14 (x 10)
  140 / 17 = Digit 8, Remainder 4 (x 10)
etc.

So the basic code (ignoring all digits except the R-th) would be

static int digitA(int N, int D, int R) {
    while (R-- > 0) {
        N = N % D;
        N = N * 10;
    }
    return N / D;
}

Replacing multiplications and divisions by adding/subtracting and shifting results in

while (R-- > 0) {
    while (N >= D) N = N - D;
    N = ((N << 2) + N) << 1;
}
int digit = 0;
while (N > D) { digit++; N = N - D; }
return digit;

As R is -1 after the first loop, it can be used to replace digit afterwards. With avoiding shifting by more than 1 and introducing intermediate P the code becomes

while (R-- > 0) {
    while (N >= D) N = N - D;
    int P = ((N + N) << 1) + N;
    N = P << 1;
}
for ( ; N >= D; N = N - D) R++;
return R;

The number of loop runs can be reduced by "splitting the decimal digit into two digits with base 5 and 2". The above manual division schema would become something like

10 / 17 = 2-Digit 0, Remainder 10 (x 5)
50 / 17 = 5-Digit 2, Remainder 16 (x 2)
32 / 17 = 2-Digit 1, Remainder 15 (x 5) --> 10-digit = 2*2 + 1
75 / 17 = 5-Digit 4, Remainder 7 (x 2)
14 / 17 = 2-Digit 0, Remainder 14 (x 5) --> 10-digit = 4*2 + 0
70 / 17 = 5-Digit 4, Remainder 2 (x 2)
4 / 17 = 2-Digit 0, Remainder 4 (x 5) --> 10-digit = 4*2 + 0
etc.

As only the R-th decimal digit is to be returned, only the R-th 5-digit before the R-th 2-digit is required to compose the R-th decimal digit.

int P=N = ((N+N)<<1)+N; // N = N * 5
for (Q=P^P; N >D; N -=D) Q++; // Q=digit(5)
//...
return (Q<<1) + R;

The rest is some "obfuscation"

  • P^P is zero - inspired by machine code where XORing may be the most efficient way to set a register to zero :-)
  • The line while (P >=D) P -=D; is the same as P=N; - but is more "smiling" :-)
\$\endgroup\$
2
  • \$\begingroup\$ Mind sharing an explanantion as well? \$\endgroup\$
    – CinCout
    Apr 16, 2017 at 6:36
  • 1
    \$\begingroup\$ @CinCout Added explanation, admitting it was hard to recall what I was thinking/intending so long ago ... :-) \$\endgroup\$
    – memnon
    Apr 16, 2017 at 11:13
2
\$\begingroup\$

Mathematica: 36 chars

f = RealDigits[#1/#2, 10, 1, -#3][[1, 1]] &

Test case:

f[1, 70000, 5]

1

\$\endgroup\$
1
\$\begingroup\$

Python: 96 bytes

The following code counts the number of digits after the decimal point, e.g. for N = 3 and D = 17, fracnum(N,D,7) = 5 since N/D = 0.176470588235.

def fracnum(N,D,R):
    v, d = abs(N)*10, abs(D)
    while R:
        (v, r, R) = (v*10, v, R-1) if v < d else ((v%d)*10, v//d, R-1)

    return r

This function can be written more compact as:

def f(N,D,R):
 v,d=abs(N)*10,abs(D)
 while R:v,r=(((v%d)*10,v//d),(v*10,v))[v<d];R-=1
 return r
\$\endgroup\$
3
  • \$\begingroup\$ You didn't give yourself a score, but if you golf your code like this (replacing \n with literal newlines): def g(n,d,r):\n f=abs;v,d=f(n)*10,f(d);\n while r:(v,e,r)=(((v%d)*10,v//d,r-1),(v*10,v,r-1))[v<d]\n return e it should come out to 105 bytes. \$\endgroup\$
    – Kaya
    Dec 29, 2013 at 16:04
  • \$\begingroup\$ Ah ok, I see. I'll make an edit showing a more compact version. Thanks! \$\endgroup\$
    – brm
    Dec 29, 2013 at 16:32
  • \$\begingroup\$ +1, oops I missed the r-1 nice answer \$\endgroup\$
    – Kaya
    Dec 29, 2013 at 16:38
1
\$\begingroup\$

Awk: 38

BEGIN{b=n/d"";print substr(b,r+2,1)}

Called by the slightly cumbersome awk -f division.awk -v n=? -v d=? -v r=? where ? represents the variable you want in there. Note that this is limited by precision, so choice of 1 4 3 would result in a blank line.

\$\endgroup\$
0
\$\begingroup\$

PHP — 54 (Exact precision)

echo bcdiv(bcmul(bcpow(10,$r+1),abs($n)),abs($d))[$r];

PHP — 41 (Not so exact precision (eventual floating point errors))

echo strval(abs(pow(10,$r+1)*$n/$d))[$r];
\$\endgroup\$
0
\$\begingroup\$

Mathematica 63 65

This now handles rational numbers close to zero. Should work to (one million places - no. places to the left of decimal point).

f[n_,d_,r_]:=({w,z}=RealDigits[N[n/d,10^6]];If[z+r<1,0,w[[z+r]]])

Testing

The following returns the digits at positions min through max, allowing for easy checking of results.

g[n_, d_, {min_, max_}] := Grid@{{"num", "den", "decimal", "digits " <> ToString@min <> 
" to " <> ToString@max}, {n, d, N[n/d, max], Table[f[n, d, k], {k, min, max}]}}

Verify the digits of 1/7 from 3 to 7 places to the right of the decimal point.

g[1, 7, {3, 7}]

t1


g[1, 7000, {3, 6}]

t2


g[1, 2, {1, 5}]

t3

\$\endgroup\$
2
  • \$\begingroup\$ David, I also used RealDigits ;-) \$\endgroup\$
    – Yves Klett
    Dec 30, 2013 at 16:08
  • \$\begingroup\$ @Yves Yes, and you exploited the third and fourth arguments in ways I was until now unaware of! Nice. \$\endgroup\$
    – DavidC
    Dec 30, 2013 at 18:18
0
\$\begingroup\$

Python: 69 bytes

def f(N,D,R): 
    return ('%.{0}f'.format(R+1)%(float(N)/float(D)))[-2]

(first time posting here, please be gentle for any formatting/misc errors :D)

\$\endgroup\$
0
\$\begingroup\$

JavaScript - 40

function f(n,d,r){return(n/d%1+'')[r+1]}
\$\endgroup\$
0
\$\begingroup\$

BASH - 52

f=$(echo "scale=$R; $N/$D"|bc -l)
n=${f:$((${#f}-1))}
\$\endgroup\$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.