बड़े पूर्णांक

Question

के लिए "आधार रूपांतरण" को तेज़ी से बढ़ाकर मैं एक बड़े पूर्णांक (32-बिट शब्दों में विभाजित) से क्रमपरिवर्तन उत्पन्न करने के लिए आधार-रूपांतरण एल्गोरिदम का उपयोग कर रहा हूं।

मैं इस के लिए एक अपेक्षाकृत मानक एल्गोरिथ्म का उपयोग करें:

/* N = count,K is permutation index (0..N!-1) A[N] contains 0..N-1 */ 
i = 0; 
while (N > 1) { 
    swap A[i] and A[i+(k%N)] 
    k = k/N 
    N = N - 1 
    i = i + 1 
} 

दुर्भाग्य से, फूट डालो और सापेक्ष प्रत्येक यात्रा कहते हैं, विशेष रूप से बड़ी पूर्णांकों में जाने - लेकिन, ऐसा लगता है मैं सिर्फ गुणा इस्तेमाल कर सकते हैं!

/* As before, N is count, K is index, A[N] contains 0..N-1 */ 
/* Split is arbitrarily 128 (bits), for my current choice of N */ 
/* "Adjust" is precalculated: (1 << Split)/(N!) */ 
a = k*Adjust; /* a can be treated as a fixed point fraction */ 
i = 0; 
while (N > 1) { 
    a = a*N; 
    index = a >> Split;   
    a = a & ((1 << Split) - 1); /* actually, just zeroing a register */  
    swap A[i] and A[i+index] 
    N = N - 1 
    i = i + 1 
} 

यह अच्छा है, लेकिन बड़े पूर्णांक गुणा करने से अभी भी सुस्त है।

प्रश्न 1:
क्या यह तेजी से करने का कोई तरीका है?

ईजी। चूंकि मुझे पता है कि एन * (एन -1) 2^32 से कम है, क्या मैं उन संख्याओं को एक शब्द से बाहर खींच सकता हूं, और 'बचे हुए' में विलय कर सकता हूं?
या, क्या एक समय में एक व्यक्ति को बाहर निकालने के लिए एक दयनीय डीकोडर को संशोधित करने का कोई तरीका है?

प्रश्न 2:
जिज्ञासा के लिए - यदि मैं समायोजन के बिना किसी संख्या को आधार 10 में परिवर्तित करने के लिए गुणा का उपयोग करता हूं, तो परिणाम (10^अंक/2^शिफ्ट) से गुणा किया जाता है। दशमलव अंकों के साथ काम कर रहे इस कारक को हटाने का कोई मुश्किल तरीका है? समायोजन कारक के साथ भी, ऐसा लगता है कि यह तेज़ होगा - मानक पुस्तकालय इस बनाम विभाजन और मोड का उपयोग क्यों नहीं करेंगे?

Answer 1

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

आप वैकल्पिक तरीकों का उपयोग कर सकते हैं:

• उपयोग एएसएम (कोडांतरक) -, मेरे अनुभव से एक लंबे समय के बाद यह पता लगाने की कैसे एक निश्चित एल्गोरिथ्म एएसएम में लिखा जाएगा चाहिए की कोशिश कर रहा है, यह धीमी जा रहा समाप्त हो गया कंपाइलर द्वारा जेनरेट किए गए संस्करण की तुलना में :) शायद क्योंकि संकलक भी कोड को लेआउट करने के बारे में जानता है, इसलिए सीपीयू कैश अधिक कुशल होगा, और/या वास्तव में कौन से निर्देश वास्तव में तेज़ हैं और कौन सी स्थितियां (यह जीसीसी/लिनक्स पर थी)।
• उपयोग बहु प्रसंस्करण:
  • अपने एल्गोरिथ्म बहु बनाने के लिए, और सुनिश्चित करें कि आप उपलब्ध सीपीयू कोर की संख्या के रूप में धागे की एक ही नंबर के साथ चलाने के बनाने के (सबसे CPU के nowdays कई कोर/बहु सूत्रण है)
  • मेकअप आप एल्गोरिदम नेटवर्क पर एकाधिक मशीनों पर चलने में सक्षम हैं, और इन नंबरों को नेटवर्क में मशीनों को भेजने का एक तरीका तैयार करते हैं, ताकि आप उनकी सीपीयू पावर का उपयोग कर सकें।

Answer 2

देखकर कि आप (मेरे गणना के अनुसार एन < 35) 2^128/(एन), ऐसा लगता है कि आपकी समस्या में एन अपेक्षाकृत छोटे होने जा रहा है की तरह संख्या के बारे में बात कर रहे हैं। मैं मूल एल्गोरिदम को प्रारंभिक बिंदु के रूप में लेने का सुझाव देता हूं; सबसे पहले लूप की दिशा स्विच करें:

i = 2; 
while (i < N) { 
    swap A[N - 1 - i] and A[N - i + k % i] 
     k = k/i 
     i = i + 1 
} 

अब लूप को प्रति पुनरावृत्ति के लिए कई क्रमपरिवर्तन करने के लिए बदलें। मुझे लगता है कि विभाजन की गति वही है, जब तक मैं < 2^32।
श्रेणी 2 विभाजित करें ...N-1 उप श्रेणियों में इतना है कि प्रत्येक उप-श्रेणी में संख्याओं का गुणनफल कम से कम 2^32 है:

2, 3, 4, ..., 12: product is 479001600 
13, 14, ..., 19: product is 253955520 
20, 21, ..., 26: product is 3315312000 
27, 28, ..., 32: product is 652458240 
33, 34, 35:  product is 39270 

फिर, बजाय मैं से विभाजित के उत्पादों द्वारा लंबे समय से नंबर कश्मीर विभाजित करते हैं। प्रत्येक पुनरावृत्ति शेष (2^32 से कम) और एक छोटी संख्या के उत्पन्न करेगा। जब आपके पास शेष होता है, तो आप मूल एल्गोरिदम का उपयोग करके आंतरिक लूप में इसके साथ काम कर सकते हैं; जो अब तेजी से होगा क्योंकि इसमें लंबी विभाजन शामिल नहीं है।

static const int rangeCount = 5; 
static const int rangeLimit[rangeCount] = {13, 20, 27, 33, 36}; 
static uint32_t rangeProduct[rangeCount] = { 
    479001600, 
    253955520, 
    3315312000, 
    652458240, 
    39270 
}; 

for (int rangeIndex = 0; rangeIndex < rangeCount; ++rangeIndex) 
{ 
    // The following two lines involve long division; 
    // math libraries probably calculate both quotient and remainder 
    // in one function call 
    uint32_t rangeRemainder = k % rangeProduct[rangeIndex]; 
    k /= rangeProduct[rangeIndex]; 

    // A range starts where the previous range ended 
    int rangeStart = (rangeIndex == 0) ? 2 : rangeLimit[rangeIndex - 1]; 

    // Iterate over range 
    for (int i = rangeStart; i < rangeLimit[rangeIndex] && i < n; ++i) 
    { 
     // The following two lines involve a 32-bit division; 
     // it produces both quotient and remainder in one Pentium instruction 
     int remainder = rangeRemainder % i; 
     rangeRemainder /= i; 
     std::swap(permutation[n - 1 - i], permutation[n - i + remainder]); 
    } 
} 

बेशक

, इस कोड से अधिक 128 बिट में बढ़ाया जा सकता है:
यहाँ कुछ कोड है।
एक और अनुकूलन में श्रेणियों के उत्पादों से 2 की शक्तियों का निष्कर्षण शामिल हो सकता है; यह सीमाओं को लंबे समय तक थोड़ा सा गति जोड़ सकता है। सुनिश्चित नहीं है कि यह सार्थक है (शायद एन के बड़े मूल्यों के लिए, जैसे एन = 1000)।