Nhân số nguyên do hợp lý mà không tràn trung

Question

Tôi có một cấu trúc đại diện cho một âm hợp lý số p/q:

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

Tôi muốn nhân hợp lý của tôi bằng một uint64 n và nhận được một kết quả số nguyên, làm tròn xuống. Tức là, tôi muốn tính toán:

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

trong khi tránh tràn trung gian trong n * r.p. (Tất nhiên kết quả cuối cùng có thể tràn, có thể chấp nhận được.)

Làm cách nào để thực hiện việc này? Có cách nào để làm điều đó mà không cần nhân lên cao không?

(Tôi nhìn boost :: hợp lý nhưng nó không xuất hiện để cung cấp tính năng này.)

Answer 1

Hoặc 128-bit, và bạn có thể sử dụng Karatsuba nhân đó; hoặc bạn có thể sử dụng Định lý còn lại của Trung Quốc để đại diện cho (n * r.p) mod p1 và cũng mod p2. Thứ hai có thể chậm hơn.

Answer 2

Bạn có thể sử dụng 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; 
}