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.
-
\$\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\$– HowardDec 29, 2013 at 9:37
-
1\$\begingroup\$ Mat I suggest you include some test cases? \$\endgroup\$– DavidCDec 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\$– KayaDec 29, 2013 at 19:17
10 Answers
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
-
\$\begingroup\$ Doesn't work with negative
N
orD
, e.g.-1 3 1
. \$\endgroup\$– HowardDec 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\$ Dec 29, 2013 at 15:10 -
-
\$\begingroup\$ @DavidCarraher For
1 70000 3
it calculates10^3/70000
using integer division, which is0
, as desired. Note that1 70000 5 = 10^5/70000 = 1
, as desired. Similarly,1 2 5=10^5/2=0
, since the decimal expansion of1/2
has a0
in the fifth decimal place. \$\endgroup\$ Dec 30, 2013 at 2:57
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 asP=N;
- but is more "smiling" :-)
-
-
1\$\begingroup\$ @CinCout Added explanation, admitting it was hard to recall what I was thinking/intending so long ago ... :-) \$\endgroup\$– memnonApr 16, 2017 at 11:13
Mathematica: 36 chars
f = RealDigits[#1/#2, 10, 1, -#3][[1, 1]] &
Test case:
f[1, 70000, 5]
1
Python: 96 bytes
The following code counts the number of digits after the decimal point, e.g. forN = 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
-
\$\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\$– KayaDec 29, 2013 at 16:04 -
\$\begingroup\$ Ah ok, I see. I'll make an edit showing a more compact version. Thanks! \$\endgroup\$– brmDec 29, 2013 at 16:32
-
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.
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];
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}]
g[1, 7000, {3, 6}]
g[1, 2, {1, 5}]
-
-
\$\begingroup\$ @Yves Yes, and you exploited the third and fourth arguments in ways I was until now unaware of! Nice. \$\endgroup\$– DavidCDec 30, 2013 at 18:18
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)
JavaScript - 40
function f(n,d,r){return(n/d%1+'')[r+1]}
BASH - 52
f=$(echo "scale=$R; $N/$D"|bc -l)
n=${f:$((${#f}-1))}