Multipliziert ganze Zahl durch rationale ohne Zwischenüberlauf

Question

Ich habe eine Struktur darstellt, eine nicht-negative rationale Zahl p/q:

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

Ich mag würde mein rational durch eine uint64 n und bekommen eine ganze Zahl Ergebnis abgerundet multiplizieren. Das heißt, würde ich berechnen mag:

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

während Zwischenüberlauf zu vermeiden in n * r.p. (Natürlich kann das Endergebnis überlaufen, was akzeptabel ist.)

Wie kann ich das tun? Gibt es einen Weg, dies ohne eine hohe Multiplikation zu tun?

(ich boost :: sah rational, aber es scheint nicht, diese Funktion zur Verfügung zu stellen.)

Answer 1

Entweder 128-Bits und man könnte es Karatsuba Multiplikation verwenden; oder Sie könnten den chinesischen Restsatz verwenden, um (n * r.p) mod p1 und auch mod p2 darzustellen. Die zweite könnte langsamer sein.

Answer 2

können Sie peasant multiplication verwenden:

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