यह जांचने की आवश्यकता थी कि क्या पूर्णांक एक वर्ग है, और यदि ऐसा है, तो रूट की गणना करें। और मैं पूर्णांक अंकगणित में ऐसा करना चाहता हूं। यह स्पष्ट है कि न्यूटन विधि को पूर्णांकों में लागू किया जा सकता है, लेकिन इसके लिए हर कदम पर विभाजन की आवश्यकता होती है। लेकिन क्या यह अन्यथा हो सकता है? वर्गाकार जड़ को दो की शक्ति में खोजें, और जांचें कि क्या यह एक साधारण वर्गमूल होगा।
आप अपने आप को विषम संख्याओं तक सीमित कर सकते हैं: एक सम संख्या के लिए, यदि कम से कम महत्वपूर्ण शून्य अंकों की संख्या विषम है, तो कोई जड़ नहीं है, लेकिन अगर यह सम है, तो आप संख्या को दाईं ओर शिफ्ट कर सकते हैं, विषम की जड़ की गणना कर सकते हैं, और मूल संख्याओं के मूल संख्या के बाएं आधे भाग में वापस आ सकते हैं।
विषम एन और 2
k के लिए , k> 3, यदि N 8 1 मॉड 8, तो 4 अलग-अलग जड़ें modulo 2
k हैं , अन्यथा जड़ें नहीं हैं। हमें x की चार जड़ों में से सबसे छोटी चाहिए। अन्य तीन जड़ें 2
k - x, 2
k-1 + x और 2
k - 2
k-1 - x हैं
मैं
उलटा modulo 2 k की गणना के समान कुछ चाहूंगा - प्रति बिट वैध बिट्स की संख्या को दोगुना करना।
मान लें कि हमारे पास पहले से ही N modulo 2
k :
N - x 0 2 = 2 k a की जड़ x
0 हैऔर हम
x 1 = x 0 + 2 k-1 y को ऐसे खोजना चाहते हैं जैसे N - x
1 2 में कम शून्य बिट्स हों।
N - (x 0 + 2 k-1 y) 2 = 2 k a - 2 k x 0 * y - 2 2k-2 y 22
k से विभाजित करें:
a - x 0 * y - 2 k-2 y 2और 0 modulo 2
k-2 :
y = a * x 0 -1 mod 2 k-2 के बराबर है
प्राप्त
x 1 = x 0 + 2 k-1 a (x 0 -1 mod 2 k-2 )और अंत में
x 1 = x 0 + (N - x 0 2 ) / 2 * (x 0 -1 mod 2 k-2 )अगले पुनरावृत्ति में k बिट्स में से, आपको 2 (k-1) बिट्स मिलते हैं। उसी समय, हम प्रत्येक पुनरावृत्ति पर जड़ के विपरीत मानते हैं।
टेस्ट कोड:
uint8_t sqr16(uint16_t n) { if (n % 8 != 1) return 0; uint16_t sqr = (n + 1) / 2; //4 bit uint16_t inv = 2 - sqr; sqr += inv * (n-sqr*sqr)/2; //6 bit inv *= 2 - sqr * inv; sqr += inv * (n-sqr*sqr)/2; //10 bit //inv *= 2 - sqr * inv; if (sqr & 256) sqr = 0u - sqr; sqr = (uint8_t)sqr; // lowest root if (n == sqr*sqr) return sqr; return 0; }
पुनरावृत्तियों के एक जोड़े को जोड़कर, हम uint_64 से रूट प्राप्त करते हैं