c - णधर - 64-बिट पूर्णांक के लिए लॉग 2 की तेज़ कंप्यूटिंग




संवृत गुणधर्म (4)

एक महान प्रोग्रामिंग संसाधन, बिट ट्विडलिंग हैक्स, 32-बिट पूर्णांक के लॉग 2 की गणना करने के लिए निम्न विधि ( here ) प्रस्तावित करता है:

#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
static const char LogTable256[256] = 
{
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries
if (tt = v >> 16)
{
    r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else 
{
    r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

और उल्लेख है कि

लुकअप टेबल विधि 32-बिट मान के लॉग को खोजने के लिए केवल 7 ऑपरेशन लेती है। यदि 64-बिट मात्रा के लिए विस्तारित किया गया है, तो इसमें लगभग 9 ऑपरेशन होंगे।

लेकिन, हां, 64-बिट पूर्णांक में एल्गोरिदम का विस्तार करने के लिए वास्तव में किस तरह से जाना चाहिए इसके बारे में कोई अतिरिक्त जानकारी नहीं देता है।

इस तरह के 64-बिट एल्गोरिदम कैसा दिखता है इसके बारे में कोई संकेत?


बेस -2 इंटीजर लॉगरिदम

64-बिट हस्ताक्षरित पूर्णांक के लिए मैं यह करता हूं। यह बेस -2 लॉगरिदम की मंजिल की गणना करता है, जो सबसे महत्वपूर्ण बिट के सूचकांक के बराबर है। यह विधि बड़ी संख्या में धूम्रपान करने वाली तेज़ है क्योंकि यह एक अनियंत्रित लूप का उपयोग करती है जो हमेशा log₂64 = 6 चरणों में निष्पादित होती है।

अनिवार्य रूप से, यह अनुक्रम में प्रगतिशील छोटे वर्गों को दूर करता है {0 ≤ के ≤ 5: 2 ^ (2 ^ के)} = {2³², 2¹⁶, 2⁸, 2⁴, 2², 2¹} = {42 9 4 9 67296, 65536, 256 , 16, 4, 2, 1} और घटाए गए मानों के एक्सपोनेंट्स को बताता है।

int uint64_log2(uint64_t n)
{
  #define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }

  int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;

  #undef S
}

ध्यान दें कि यह रिटर्न -1 है यदि 0 का अमान्य इनपुट दिया गया है (जो प्रारंभिक है -(n == 0) की जांच कर रहा है)। यदि आप कभी भी n == 0 साथ इसे आमंत्रित करने की अपेक्षा नहीं करते हैं, तो आप int i = 0; को प्रतिस्थापित कर सकते हैं int i = 0; प्रारंभकर्ता के लिए और assert(n != 0); जोड़ें assert(n != 0); समारोह में प्रवेश पर।

बेस -10 इंटीजर लॉगरिदम

बेस -10 पूर्णांक लॉगरिदम की गणना इसी प्रकार की जा सकती है - सबसे बड़ा वर्ग 10¹⁶ होने का परीक्षण करने के लिए क्योंकि log₁₀2⁶⁴ ≅ 19.2659 ... (नोट: बेस -10 पूर्णांक लॉगरिदम को पूरा करने का यह सबसे तेज़ तरीका नहीं है, क्योंकि यह पूर्णांक विभाजन का उपयोग करता है, जो स्वाभाविक रूप से धीमा है। एक तेजी से कार्यान्वयन एक संचयक का उपयोग मूल्यों के साथ होता है जो तेजी से बढ़ते हैं, और संचयक के खिलाफ तुलना करते हैं, असल में बाइनरी खोज करते हैं।)

int uint64_log10(uint64_t n)
{
  #define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }

  int i = -(n == 0);
  S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
  return i;

  #undef S
}

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

const int tab64[64] = {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5};

int log2_64 (uint64_t value)
{
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    value |= value >> 32;
    return tab64[((uint64_t)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58];
}

2 की अगली निचली शक्ति तक घूमने का हिस्सा पावर ऑफ 2 सीमाओं से लिया गया था (bb & -bb) कोड से पिछली शून्यों की संख्या प्राप्त करने का हिस्सा लिया गया था, सही बिट जो 1 पर सेट है, जिसकी कीमत को 2 की अगली शक्ति तक मानने के बाद आवश्यकता नहीं है)।

और 32-बिट कार्यान्वयन, वैसे, है

const int tab32[32] = {
     0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7,
    19, 27, 23,  6, 26,  5,  4, 31};

int log2_32 (uint32_t value)
{
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}

किसी अन्य कम्प्यूटेशनल विधि के साथ, लॉग 2 को इनपुट मान शून्य से अधिक होने की आवश्यकता होती है।


कोई अतिरिक्त अस्थायी और तेजी से विस्तार नहीं है, कोई अतिरिक्त अस्थायी नहीं है:

r = 0;

/* If its wider than 32 bits, then we already know that log >= 32.
So store it in R.  */
if (v >> 32)
  {
    r = 32;
    v >>= 32;
  }

/* Now do the exact same thing as the 32 bit algorithm,
except we ADD to R this time.  */
if (tt = v >> 16)
  {
    r += (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
  }
else
  {
    r += (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
  }

यहां एक एस श्रृंखला की श्रृंखला के साथ बनाया गया है, फिर से कोई अतिरिक्त अस्थायी नहीं है। यद्यपि सबसे तेज़ नहीं हो सकता है।

  if (tt = v >> 48)
    {
      r = (t = tt >> 8) ? 56 + LogTable256[t] : 48 + LogTable256[tt];
    }
  else if (tt = v >> 32)
    {
      r = (t = tt >> 8) ? 40 + LogTable256[t] : 32 + LogTable256[tt];
    }
  else if (tt = v >> 16)
    {
      r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
    }
  else 
    {
      r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
    }

मैं ओ (एलजी (एन)) संचालन में एक एन-बिट पूर्णांक के लॉग बेस 2 को गुणा करने के लिए कोशिश कर रहा था और जादू संख्या को मजबूर कर ब्रूट द्वारा 64-बिट तक लुकअप के साथ लुकअप किया था। कहने की जरूरत नहीं है कि इसमें कुछ समय लग रहा था।

तब मैंने डेसमंड के जवाब को पाया और एक प्रारंभ बिंदु के रूप में अपने जादू संख्या का प्रयास करने का फैसला किया। चूंकि मेरे पास 6 कोर प्रोसेसर है, इसलिए मैंने इसे समानांतर में 0x07EDD5E59A4E28C2 / 6 गुणकों से शुरू किया। मुझे आश्चर्य हुआ कि यह तुरंत कुछ मिला। 0x07EDD5E59A4E28C2 / 2 काम करता है।

तो यहां 0x07EDD5E59A4E28C2 का कोड है जो आपको एक शिफ्ट और घटाना बचाता है:

int LogBase2(uint64_t n)
{
    static const int table[64] = {
        0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,
        51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,
        57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
        45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };

    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n |= n >> 32;

    return table[(n * 0x03f6eaf2cd271461) >> 58];
}




lookup