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




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

एक महान प्रोग्रामिंग संसाधन, बिट ट्विडलिंग हैक्स, 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 के कंपाइलर-स्वतंत्र कार्यान्वयन के लिए अपर्याप्त हैं। तो यदि कोई दिलचस्पी लेता है, तो यहां सबसे तेज़, शाखा-मुक्त, सीपीयू-अमूर्त डेब्रूज़न-जैसे एल्गोरिदम है, मैं अपने विषय पर शोध करते समय आया हूं।

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 को इनपुट मान शून्य से अधिक होने की आवश्यकता होती है।


एल्गोरिदम मूल रूप से पता लगाता है कि किस बाइट में सबसे महत्वपूर्ण 1 बिट होता है, और उसके बाद बाइट के लॉग को खोजने के लिए लुकअप में बाइट दिखता है, फिर इसे बाइट की स्थिति में जोड़ता है।

32-बिट एल्गोरिदम का कुछ सरल संस्करण यहां दिया गया है:

if (tt = v >> 16)
{
    if (t = tt >> 8)
    {
        r = 24 + LogTable256[t];
    }
    else
    {
        r = 16 + LogTable256[tt];
    }
}
else 
{
    if (t = v >> 8)
    {
        r = 8 + LogTable256[t];
    }
    else
    {
        r = LogTable256[v];
    }
}

यह बराबर 64-बिट एल्गोरिदम है:

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

मैं किसी भी आकार के प्रकार के लिए एक एल्गोरिदम के साथ आया जो मुझे लगता है कि मूल से अच्छा है।

unsigned int v = 42;
unsigned int r = 0;
unsigned int b;
for (b = sizeof(v) << 2; b; b = b >> 1)
{
    if (v >> b)
    {
        v = v >> b;
        r += b;
    }
}

नोट: b = sizeof(v) << 2 v में बिट्स की आधा संख्या सेट करता है। मैंने यहां गुणा के बजाय स्थानांतरित किया था (सिर्फ इसलिए कि मुझे ऐसा लगा)।

आप संभवतः इसे गति देने के लिए उस एल्गोरिदम में एक लुकअप तालिका जोड़ सकते हैं, लेकिन यह सबूत का सबूत है।


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

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-बिट हस्ताक्षरित पूर्णांक के लिए मैं यह करता हूं। यह बेस -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
}

यदि आप जीसीसी का उपयोग कर रहे हैं, तो इस मामले में एक लुकअप टेबल अनावश्यक है।

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

अंतर्निहित फ़ंक्शन: int __builtin_clz (unsigned int x)
सबसे महत्वपूर्ण बिट स्थिति से शुरू, एक्स में अग्रणी 0-बिट्स की संख्या देता है। यदि एक्स 0 है, तो परिणाम अपरिभाषित है।

तो आप परिभाषित कर सकते हैं:

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

और यह किसी भी हस्ताक्षरित लंबे लंबे int के लिए काम करेगा। परिणाम गोलाकार है।

X86 और AMD64 GCC के लिए इसे एक bsr निर्देश में संकलित कर देगा, इसलिए समाधान बहुत तेज़ है (लुकअप टेबल से बहुत तेज़)।

कार्य उदाहरण :

#include <stdio.h>

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

int main(void) {
    unsigned long long input;
    while (scanf("%llu", &input) == 1) {
        printf("log(%llu) = %u\n", input, LOG2(input));
    }
    return 0;
}






lookup