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

Question

I was tasked with finding the digit of the kth position after the decimal point of the fraction (a / b). Yesterday I found out about this algorithm.
To get any digit after the decimal point, I create a variable called rem and create 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 that is the kth digit after the decimal point.
However, the task requires me to calculate that a, b, k is a very large number (less than or equal to 10e18), so he is confident that the code will exceed the time limit.

• Find the number of digits before repeating. This is more of the 2 and 5 factors in the denominator.
• If k does not exceed the number of digits, run the for loop.
• Otherwise, we will continue the for loop to k + 1. Save the value of the rest of the division of the variable x.
• Run the while loop with the same contents as before the remaining x value. From then on, save each private partition to the qut array name.
• After the while loop finishes, the array will store each digit inside the repeat. According to the number of digits inside the array, we can calculate the kth number.
  However, this algorithm still requires a lot of time, because in case a and b are two consecutive integers, the repetition becomes very large. Can you help me with any idea?

Answer 1

, for , 10 * (a * 10 ^k% b)/b. , . , , :

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;
}

a,b,k, 64- .