फैक्टोरियल

Question

की गणना के लिए फास्ट एल्गोरिदम मैंने this page को फैक्टोरियल की गणना करने के लिए कई एल्गोरिदम का वर्णन किया। दुर्भाग्य से, स्पष्टीकरण terse हैं और मैं एल्गोरिदम के पीछे बुनियादी सिद्धांतों को समझने के लिए स्रोत कोड की रेखा के बाद लाइन के माध्यम से लाइन के माध्यम से बहने की तरह महसूस नहीं करता है।

क्या कोई मुझे फैक्टोरियल की गणना के लिए इन (या अन्य तेज़) एल्गोरिदम के अधिक विस्तृत विवरणों के बारे में बता सकता है?

संपादित करें:This page प्रधानमंत्री गुणन की विधि, तकनीक सबसे अच्छा प्रदर्शन करने भाज्य एल्गोरिदम के सभी के लिए आम का वर्णन है। इसमें पायथन में कुछ अच्छा उदाहरण कोड भी शामिल है। लेखक a description of binary splitting से लिंक करता है और जर्नल ऑफ़ एल्गोरिदम ("फैक्टोरियल की गणना की जटिलता पर) में एक आलेख का संदर्भ देता है जो वादा करता है, अगर मैं केवल उस पर अपना हाथ प्राप्त कर सकता हूं।

Answer 1

रिचर्ड फ़ेटमैन द्वारा paper (PDF link) देखें। कोड नमूने लिस्प में हैं, लेकिन किसी भी घटना में, अधिकांश गुप्त फोड़े नीचे आपको बिग्नम (मनमाना सटीक पूर्णांक) गणनाओं की संख्या को कम करने के लिए नीचे उबलते हैं।

स्वाभाविक रूप से, यदि आपको bignums की आवश्यकता नहीं है, तो यह छोटा है; या तो एक लुकअप टेबल या एक साधारण पाश ठीक हो जाएगा।

संपादित करें: यदि आप एक अनुमानित जवाब का उपयोग कर सकते हैं, तो आप भाज्य के लघुगणक की गणना कर सकता या तो सीधे k = 2 ... n के लिए log(k), संक्षेप द्वारा या सम्मानित Stirling approximation का उपयोग करके। अतिप्रवाह से बचने के लिए आप जहां भी संभव हो लॉगरिदम के साथ काम करना चाहते हैं; विशेष रूप से, स्टर्लिंग के अनुमान का एक बेवकूफ आवेदन बहुत से स्थानों में बह जाएगा जहां इसे नहीं करना है।

Answer 2

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