तर्कसंगत से गुणा पूर्णांक मध्यवर्ती अतिप्रवाह

Question

बिना मैं एक struct गैर नकारात्मक तर्कसंगत संख्या p/q का प्रतिनिधित्व किया है:

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

मैं एक uint64 n के आधार पर अपने तर्कसंगत गुणा और एक पूर्णांक परिणाम प्राप्त करना चाहते हैं, पूर्णांक। जो है, मैं गणना करने के लिए करना चाहते हैं:

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

जबकि n * r.p में मध्यवर्ती अतिप्रवाह से परहेज। (बेशक अंतिम परिणाम अतिप्रवाह हो सकता है, जो स्वीकार्य है।)

मैं यह कैसे कर सकता हूं? क्या उच्च-गुणा के बिना ऐसा करने का कोई तरीका है?

(मैं बढ़ावा :: तर्कसंगत को देखा है, लेकिन यह इस सुविधा प्रदान करने के लिए यह मौजूद नहीं था।)

Answer 1

या तो 128-बिट और आप Karatsuba गुणा वहाँ का उपयोग कर सकते हैं, या आप चीनी रिमेन्डर प्रमेय का प्रतिनिधित्व करने के लिए (एन * आरपी) मॉड पी 1 और मॉड पी 2 भी उपयोग कर सकते हैं। दूसरा धीमा हो सकता है।

Answer 2

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