Find the kth digit after the decimal point of a fraction a/b with a,b,k being very large integers (less than 10e18)

Question

I was tasked to find a digit of kth position after the decimal point of a fraction(a/b). Yesterday I found out this algorithm.
To get any digit after the decimal point, I generate a variable called rem and make a loop

for (int i = 1; i <= k+1; i++)    
      {
         rem = a%b;
         a = rem*10;
      }
      cout << a/b;

the loop will return a value being the kth digit after the decimal point.
However the task require me to calculate with a,b,k being very large number ( less or equal to 10e18), so it's sure that the code will exceed the time limit.

Find the number of the digits before the repetend. It's the greater of the numbers of 2 and 5 factors in the denominator.
If the k doesn't exceed the number of digits, run the for loop.
Else, we will still run the for loop to k+1. Store the value of the remainder of the division in a variable x.
Run a while loop with the same content above until the remainder again have the value of x. Since then, store every quotient of the division into an array name qut.
After the while loop terminates, the array will have stored every digit inside the repetend. According to the number of the digits inside the array, we can calculate the kth digit.
However, this algorithm still prove to be time consuming because in the case of a and b are two consecutive integer, the repetend become very large. Can you help me with any idea?

if all variables fit in 64 bits then there's nothing more to be done, unless b is so large than 10*b overflows — phuclv
If all the variables are integers, then how can they be less than or equal to 10e18?? As far as I know, the highest limit of integer in c++ (which is that of unsigned long int is about 4.29e9. — progyammer
@progy_rock: Try uint64_t. It doesn't have to exist, but if it does it will hold 10e18. — Martin Bonner supports Monica

orlp orlp · Accepted Answer · 2016-09-21T09:25:33

What your for loop calculates is effectively 10 * (a*10^k % b) / b. We can do this more efficiently by doing exponentiation by squaring. We have to be careful not to overflow at every point though:

int kth_digit_frac(uint64_t a, uint64_t b, uint64_t k) {
    return 10 * mulmodu64(a, powmod(10, k, b), b) / b;
}

// a*b % m, overflow safe
inline uint64_t mulmodu64(uint64_t a, uint64_t b, uint64_t m) {
    #if defined(__GNUC__) && defined(__x86_64__)
        uint64_t q, r;
        asm("mulq %3;"
            "divq %4;"
            : "=a"(q), "=d"(r)
            : "a"(a), "d"(b), "rm"(m)
            : "cc");
        return r;
    #else
        a %= m;
        b %= m;

        // No overflow possible.
        if (a == 0) return 0;
        if (b <= std::numeric_limits<uint64_t>::max() / a) return (a*b) % m;

        uint64_t res = 0;
        while (a != 0) {
            if (a & 1) {
                if (b >= m - res) res -= m;
                res += b;
            }

            a >>= 1;
            if (b >= m - b) b += b - m;
            else            b += b;
        }

        return res;
    #endif
}


// b^e % m, overflow safe
inline uint64_t powmod(uint64_t b, uint64_t e, uint64_t m) {
    uint64_t r = 1;

    b %= m;
    while (e) {
        if (e % 2 == 1) r = mulmodu64(r, b, m);
        b = mulmodu64(b, b, m);
        e >>= 1;
    }

    return r;
}

It runs in the blink of an eye for any a,b,k that fit in 64 bit integers.

Find the kth digit after the decimal point of a fraction a/b with a,b,k being very large integers (less than 10e18)

2 Answers