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\$
  • \$\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 '13 at 9:37
  • 1
    \$\begingroup\$ Mat I suggest you include some test cases? \$\endgroup\$ – DavidC Dec 29 '13 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 '13 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\$
  • \$\begingroup\$ Doesn't work with negative N or D, e.g. -1 3 1. \$\endgroup\$ – Howard Dec 29 '13 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 '13 at 15:10
  • \$\begingroup\$ How does it handle 1 70000 3? 1 2 5? \$\endgroup\$ – DavidC Dec 29 '13 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 '13 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\$
  • \$\begingroup\$ Mind sharing an explanantion as well? \$\endgroup\$ – CinCout - Reinstate Monica Apr 16 '17 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 '17 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\$
  • \$\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 '13 at 16:04
  • \$\begingroup\$ Ah ok, I see. I'll make an edit showing a more compact version. Thanks! \$\endgroup\$ – brm Dec 29 '13 at 16:32
  • \$\begingroup\$ +1, oops I missed the r-1 nice answer \$\endgroup\$ – Kaya Dec 29 '13 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\$
  • \$\begingroup\$ David, I also used RealDigits ;-) \$\endgroup\$ – Yves Klett Dec 30 '13 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 '13 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\$

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