रूट-गणना फ़ंक्शन लागू करना

Question

विभिन्न चीजों के लिए गणित कार्यों को कार्यान्वित करना काफी आसान है। int mul(int,int);, int pow(int,int);, यहां तक ​​कि double div(float,float); करना आसान है और लूप या रिकर्सन के साथ कार्यान्वित किया जा सकता है। (ये वही विधियां हैं जो इन कार्यों को हाथ से या सिर में करने के लिए उपयोग की जाती हैं।) गुणा करने के लिए, बार-बार संख्या को जोड़ दें। विभाजित करने के लिए, इसे बार-बार घटाएं। शक्ति प्राप्त करने के लिए, बार-बार गुणा करें। और इसी तरह।

एक गणितीय फ़ंक्शन जिसे मैंने हमेशा के बारे में सोचा है, वह जड़ों है। उदाहरण के लिए, आप किसी संख्या (यानी double root(float num, float root);) के वर्ग (या घन, आदि) रूट की गणना करने के लिए फ़ंक्शन कैसे लिखेंगे? मैंने चारों ओर देखने की कोशिश की और ऐसा करने के लिए एल्गोरिदम या विधि नहीं मिली।

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

स्पष्ट रूप से LUT प्रासंगिक नहीं हैं क्योंकि इसे किसी भी ऑपरेंड लेने के लिए पर्याप्त सामान्य होना होगा (जब तक कि आप डेटा के सीमित सेट के साथ गेम नहीं लिख रहे हों)। Wikipedia article अनुमान विधि का उल्लेख करता है और कुछ प्राचीन लोगों को सूचीबद्ध करता है (कंप्यूटरों का आविष्कार करने से बहुत पहले) साथ ही कुछ शुद्ध गणित और यहां तक ​​कि गणित विधियों (जिनमें से कुछ "घटक के रूप में" अनंतता "है)। इलेक्ट्रॉनिक्स के साथ ट्रिक या लॉजिरिथम का उपयोग करने वाले कुछ भी ऐसा लगता है। (और यह सिर्फ वर्ग-जड़ के लिए है, अकेले घन-जड़ें, और ऐसे।)

क्या कोई आसान रूट गणना विधि नहीं है? कैलकुलेटर यह कैसे करते हैं? कंप्यूटर यह कैसे करते हैं? (नहीं, बस double pow(a,0.5); काम नहीं करेगा क्योंकि double pow(float,float) लागू किया जाएगा?)

क्या मैं बस गलत कार्यों के साथ रूट फ़ंक्शंस को गलत तरीके से समूहीकृत कर रहा हूं? क्या वे प्रतीत होने से अधिक जटिल हैं?

Answer 1

N-th root algorithm को आपके द्वारा बताए गए लेख से सीधे लिंक करने के लिए एक आसान है। यह Newton's method से लिया गया है।

Answer 2

कुछ संभावनाएं हैं। कुछ अलग-अलग पुनरावृत्तियों के दृष्टिकोण हैं, जैसे कि बिसेक्शन या न्यूटन। जहां तक ​​pow का उपयोग किया जाता है, कुछ कंप्यूटर (उदाहरण के लिए x86) के पास एक शक्ति को बढ़ाने के लिए (कम से कम भाग) करने का निर्देश होता है, इसलिए यह पूरी तरह से उस पर थोड़ा सा ढांचा लिखने का विषय है।

यहां एक वर्ग रूट के लिए न्यूटन की विधि का असेंबली भाषा कार्यान्वयन है, इस मामले में केवल 16-बिट पूर्णांक के साथ काम करते हैं, लेकिन वही मूल विचार अन्य प्रकारों पर लागू होता है। मैंने इसे लगभग 20 साल पहले लिखा था, इसलिए यह 16-बिट CPUs के लिए नहीं था जिसमें फ्लोटिंग पॉइंट हार्डवेयर नहीं था। ,

pow proc 
    ; x^y = 2^(log2(x) * y) 
    fyl2x  
    fld st(0) 
    frndint 
    fld1  
    fscale 
    fxch st(2) 
    fsubrp 
    f2xm1  
    fld1  
    faddp  
    fmulp  
    ret 
endp 

नोट यह है कि आप नहीं है सामान्य रूप से बस बार-बार घटा कर केवल बार-बार जोड़कर गुणा, या विभाजन लागू करना चाहते हैं:

isqrt proc uses di, number:word 
; 
; uses bx, cx, dx 
; 
    mov di,number 
    mov ax,255 
start_loop: 
    mov bx,ax 
    xor dx,dx 
    mov ax,di 
    div bx 
    add ax,bx 
    shr ax,1 
    mov cx,ax 
    sub cx,bx 
    cmp cx,2 
    ja start_loop 
    ret 
isqrt endp 

यहाँ मनमाना शक्तियों गणना करने के लिए एक x87 के लिए कुछ कोड है । इसके बजाय, आप परिणाम को और अधिक तेज़ी से प्राप्त करने के लिए दो की लगातार शक्तियों को स्थानांतरित और घटा सकते हैं।

यहाँ कुछ कोड है कि सामान्य विचार से पता चलता है:

mult proc 
; multiplies eax by ebx and places result in edx:ecx 
    xor ecx, ecx 
    xor edx, edx 
mul1: 
    test ebx, 1 
    jz mul2 
    add ecx, eax 
    adc edx, 0 
mul2: 
    shr ebx, 1 
    shl eax, 1 
    test ebx, ebx 
    jnz mul1 
done: 
    ret 
mult endp 

यह x86 के लिए सुंदर व्यर्थ है, क्योंकि यह में बनाया गुणा निर्देश है, लेकिन पुराने प्रोसेसर (PDP-11, 8080, 6502, आदि पर) इस तरह का कोड काफी आम था।

Answer 3

यह इस बात पर निर्भर करता है कि आप कितना सामान्य होना चाहते हैं। उदाहरण के लिए, यदि आप गणना करना चाहते हैं, (-4.2) ^0.23, आपको जटिल अंकगणितीय की आवश्यकता होगी। चूंकि मैट इंगित करता है, पूर्णांक n और सकारात्मक x के लिए x ^1/n कंप्यूटिंग के लिए तेज़ एल्गोरिदम हैं। यदि आप सकारात्मक x और किसी भी वाई के लिए x ^y चाहते हैं, तो लॉग और घातीय कार्य कार्य करेंगे।