सी

Question

के साथ uint64_t पूर्णांक ओवरफ़्लो के गुणा का पता लगाने के लिए क्या कोई कुशल और पोर्टेबल तरीका है जब यह जांचने के लिए कोई कुशल और पोर्टेबल तरीका है कि int64_t या uint64_t के साथ गुणात्मक संचालन सी में ऑपरेशन ओवरफ़्लो होता है?

उदाहरण के लिए, uint64_t के अलावा के लिए मैं कर सकते हैं:

if (UINT64_MAX - a < b) overflow_detected(); 
else sum = a + b; 

लेकिन मैं गुणन के लिए एक समान सरल अभिव्यक्ति के लिए नहीं मिल सकता है।

मेरे साथ जो कुछ भी होता है वह ऑपरेशन को उच्च और निम्न uint32_t भागों में तोड़ रहा है और ओवरफ्लो की जांच करते समय उन हिस्सों के गुणा को निष्पादित कर रहा है, कुछ वास्तव में बदसूरत और शायद अक्षम भी है।

अद्यतन 1: जेन्स Gustedt विधि जोड़ा

बेंच मार्किंग कार्यक्रम:

#include <stdio.h> 
#include <stdint.h> 
#include <stdlib.h> 

#define N 100000000 

int d = 2; 

#define POW_2_64 ((double)(1 << 31) * (double)(1 << 31) * 4) 

#define calc_b (a + c) 
// #define calc_b (a + d) 

int main(int argc, char *argv[]) { 
    uint64_t a; 
    uint64_t c = 0; 
    int o = 0; 
    int opt; 

    if (argc != 2) exit(1); 

    opt = atoi(argv[1]); 

    switch (opt) { 

    case 1: /* faked check, just for timing */ 
     for (a = 0; a < N; a++) { 
      uint64_t b = a + c; 
      if (c > a) o++; 
      c += b * a; 
     } 
     break; 

    case 2: /* using division */ 
     for (a = 0; a < N; a++) { 
      uint64_t b = a + c; 
      if (b && (a > UINT64_MAX/b)) o++; 
      c += b * a; 
     } 
     break; 

    case 3: /* using floating point, unreliable */ 
     for (a = 0; a < N; a++) { 
      uint64_t b = a + c; 
      if ((double)UINT64_MAX < (double)a * (double)b) o++; 
      c += b * a; 
     } 
     break; 

    case 4: /* using floating point and division for difficult cases */ 
     for (a = 0; a < N; a++) { 
      uint64_t b = a + c; 
      double m = (double)a * (double)b; 
      if (((double)(~(uint64_t)(0xffffffff)) < m) && 
       ((POW_2_64 < m) || 
        (b && 
        (a > UINT64_MAX/b)))) o++; 
      c += b * a; 
     } 
     break; 

    case 5: /* Jens Gustedt method */ 
     for (a = 0; a < N; a++) { 
      uint64_t b = a + c; 
      uint64_t a1, b1; 
      if (a > b) { a1 = a; b1 = b; } 
      else  { a1 = b; b1 = a; } 
      if (b1 > 0xffffffff) o++; 
      else { 
       uint64_t a1l = (a1 & 0xffffffff) * b1; 
       uint64_t a1h = (a1 >> 32) * b1 + (a1l >> 32); 
       if (a1h >> 32) o++; 
      } 
      c += b1 * a1; 
     } 
     break; 

    default: 
     exit(2); 
    } 
    printf("c: %lu, o: %u\n", c, o); 
} 

अब तक मामले में 4 का उपयोग करता है कुछ बेंचमार्क कोड कई दृष्टिकोण को लागू करने

अद्यतन 2 जोड़ा अधिकांश मामलों को फ़िल्टर करने के लिए फ़्लोटिंग पॉइंट सबसे तेज़ होता है जब यह माना जाता है कि ओवरफ्लो बहुत असामान्य हैं, कम से कम मेरे कंप्यूटर पर जहां यह केवल दो टी है कुछ भी मामला से धीमी गति से imes।

प्रकरण 5, 30% 4 की तुलना में धीमी है, लेकिन यह हमेशा एक ही करता है, वहाँ किसी भी विशेष मामला संख्या कि धीमी संसाधन की आवश्यकता होती साथ 4.

Answer 1

आप Ambrož 'जवाब में के रूप में विभाजन से बचना चाहते हैं:

पहले आप उस दो नंबर के छोटे, कहते हैं कि a को देखने के लिए, कम से कम 2 ^{32 है}, अन्यथा परिणाम किसी भी तरह से बह जाएगा। b को दो 32 बिट शब्दों में विघटित करें जो b = + d है।

गणना तो इतना मुश्किल नहीं है, मुझे लगता है:

uint64_t mult_with_overflow_check(uint64_t a, uint64_t b) { 
    if (a > b) return mult_with_overflow_check(b, a); 
    if (a > UINT32_MAX) overflow(); 
    uint32_t c = b >> 32; 
    uint32_t d = UINT32_MAX & b; 
    uint64_t r = a * c; 
    uint64_t s = a * d; 
    if (r > UINT32_MAX) overflow(); 
    r <<= 32; 
    return addition_with_overflow_check(s, r); 
} 

तो यह दो गुणा, दो पालियों, कुछ जोड़ और हालत की जाँच करता है। यह विभाजन से अधिक कुशल हो सकता है क्योंकि उदाहरण के लिए दो गुणाओं को समानांतर में पाइपलाइन किया जा सकता है। आपको यह देखने के लिए बेंचमार्क करना होगा कि आपके लिए क्या बेहतर काम करता है।

Answer 2

असल में होता है के रूप में नहीं है, इसी सिद्धांत इस्तेमाल किया जा सकता गुणन के लिए:

uint64_t a; 
uint64_t b; 
... 
if (b != 0 && a > UINT64_MAX/b) { // if you multiply by b, you get: a * b > UINT64_MAX 
    <error> 
} 
uint64_t c = a * b; 

समान हस्ताक्षर किए पूर्णांक के लिए किया जा सकता है, तो आप शायद लक्षण के प्रत्येक संयोजन के लिए एक मामला नहीं करनी होंगी।

Answer 3

कुछ (उम्मीदवार) उपयोगी उत्तरों के साथ संबंधित प्रश्न: Best way to detect integer overflow in C/C++। साथ ही यह न केवल uint64_t को शामिल किया गया;)

Answer 4

case 6: 
    for (a = 0; a < N; a++) { 
     uint64_t b = a + c; 
     uint64_t a1, b1; 
     if (a > b) { a1 = a; b1 = b; } 
     else  { a1 = b; b1 = a; } 
     uint64_t cc = b1 * a1; 
     c += cc; 
     if (b1 > 0xffffffff) o++; 
     else { 
      uint64_t a1l = (a1 & 0xffffffff) + (a1 >> 32); 
      a1l = (a1 + (a1 >> 32)) & 0xffffffff; 
      uint64_t ab1l = a1l * b1; 
      ab1l = (ab1l & 0xffffffff) + (ab1l >> 32); 
      ab1l += (ab1l >> 32); 
      uint64_t ccl = (cc & 0xffffffff) + (cc >> 32); 
      ccl += (ccl >> 32); 
      uint32_t ab32 = ab1l; if (ab32 == 0xffffffff) ab32 = 0; 
      uint32_t cc32 = ccl; if (cc32 == 0xffffffff) cc32 = 0; 
      if (ab32 != cc32) o++; 
     } 
    } 
    break; 

इस विधि गुणन का परिणाम है, जो नहीं कर सकते अतिप्रवाह के साथ तुलना (संभवतः बह निकला) सामान्य गुणा का परिणाम है। सभी गणना मॉड्यूलो (2^32 - 1) हैं।

यह अधिक जटिल और (सबसे अधिक संभावना है) जेन्स गुस्टेड की विधि से तेज़ नहीं है।

कुछ छोटे बदलावों के बाद यह 96-बिट परिशुद्धता (लेकिन अतिप्रवाह नियंत्रण के बिना) गुणा कर सकता है। और अधिक रोचक क्या हो सकता है, इस विधि का विचार अंकगणितीय परिचालनों (गुणाओं, जोड़ों, घटाव) की श्रृंखला के लिए अतिप्रवाह की जांच के लिए उपयोग किया जा सकता है।

कुछ सवाल सभी के जवाब

पहले, "your code is not portable" के बारे में। हां, कोड पोर्टेबल नहीं है क्योंकि यह uint64_t का उपयोग करता है, जिसे मूल प्रश्न में अनुरोध किया जाता है। कड़ाई से बोलते हुए, आपको (u)int64_t के साथ कोई पोर्टेबल उत्तर नहीं मिल सकता है क्योंकि यह मानक द्वारा आवश्यक नहीं है।

लगभग "once some overflow happens, you can not assume the result value to be anything"। मानक कहता है कि हस्ताक्षरित itegers ओवरफ्लो नहीं कर सकते हैं। अध्याय 6.2.5, आइटम 9:

एक अभिकलन अहस्ताक्षरित ऑपरेंड को शामिल कर सकते हैं कभी नहीं अतिप्रवाह, क्योंकि एक परिणाम है कि जिसके परिणामस्वरूप अहस्ताक्षरित पूर्णांक प्रकार से नहीं दर्शाया जा सकता कम हो जाता है कि संख्या सबसे बड़ा एक से अधिक है सापेक्ष मूल्य जो परिणामस्वरूप प्रकार से दर्शाया जा सकता है।

तो बिना हस्ताक्षर किए 64-बिट गुणा मॉड्यूलो 2^64, ओवरफ्लो के बिना किया जाता है।

अब "logic behind" के बारे में। "हैश फ़ंक्शन" यहां सही शब्द नहीं है। मैं केवल गणना मॉड्यूलो (2^32 - 1) का उपयोग करता हूं। गुणा के परिणाम को n*2^64 + m के रूप में दर्शाया जा सकता है, जहां m दृश्य परिणाम है, और n का अर्थ है कि हम कितना अधिक बहते हैं। 2^64 = 1 (mod 2^32 - 1) के बाद से, हम [true value] - [visible value] = (n*2^64 + m) - m = n*2^64 = n (mod 2^32 - 1) की गणना कर सकते हैं। यदि n की गणना मान शून्य नहीं है, तो एक ओवरफ़्लो है। यदि यह शून्य है, तो कोई ओवरफ़्लो नहीं है। n >= 2^32 - 1 के बाद ही कोई टक्कर संभव है। ऐसा कभी नहीं होगा क्योंकि हम जांचते हैं कि गुणों में से एक 2^32 से कम है।

Answer 5

यह सटीक अतिप्रवाह का पता लगा सकते है, लेकिन सामान्य रूप में आप एक लघुगणकीय पैमाने पर अपने गुणन का परिणाम परीक्षण कर सकते हैं:

if (log(UINT64_MAX-1) - log(a) - log(b) < 0) overflow_detected(); // subtracting 1 to allow some tolerance when the numbers are converted to double 
else prod = a * b; 

यह निर्भर करता है यदि आप वास्तव में UINT64_MAX सटीक गुणा अप करने की जरूरत है, अन्यथा इस बड़ी संख्या के गुणाओं की जांच करने के लिए एक बहुत ही पोर्टेबल और सुविधाजनक तरीका।