Mnożąc liczbę całkowitą przez racjonalne bez pośredniego przelewem

Question

Mam struct reprezentujący nieujemną liczbą wymierną P/Q:

struct rational { 
    uint64_t p; 
    uint64_t q; // invariant: always > 0 
}; 

chciałbym mnożyć mój racjonalny przez uint64 n i uzyskać wynik całkowitą, zaokrąglony dół. Oznacza to, że jak to obliczenie:

uint64_t m = (n * r.p)/r.q; 

unikając pośredniego przepełnienie n * r.p. (Oczywiście końcowy wynik może być przepełniony, co jest dopuszczalne.)

Jak mogę to zrobić? Czy istnieje sposób, aby to zrobić bez wysokiego mnożenia?

(I spojrzał na boost :: racjonalne, ale nie wydaje się, aby zapewnić tę funkcję).

Answer 1

Albo 128-bitów i można użyć Karatsuba mnożenie tam; lub możesz użyć Chińskiego Twierdzenia o Pozostałości do reprezentowania (n * r.p) mod p1, a także mod p2. Drugi może być wolniejszy.

Answer 2

Można użyć peasant multiplication:

// requires 0 < c < 2^63 
// returns (a * b)/c. 
uint64_t multDiv(uint64_t a, uint64_t b, uint64_t c) { 
    uint64_t rem = 0; 
    uint64_t res = (a/c) * b; 
    a = a % c; 
    // invariant: a_orig * b_orig = (res * c + rem) + a * b 
    // a < c, rem < c. 
    while (b != 0) { 
    if (b & 1) { 
     rem += a; 
     if (rem >= c) { 
     rem -= c; 
     res++; 
     } 
    } 
    b /= 2; 
    a *= 2; 
    if (a >= c) { 
     a -= c; 
     res += b; 
    } 
    } 
    return res; 
}