लिए सबसे कारगर तरीका एक बहुपद

Question

बहुपद: a0x^0 + a1x^1 + a2x^2 + A3X^3 + ... + anx^n

सरणी: array_a [] = {a0, A1, ए 2, ए 3 ... ए};

मैं जावा में इस बहुपद गणना करने के लिए एक समारोह लिखा है:

public double cal(double x) { 
    double y = 0.0; 
    for (int index = array_a.length - 1; index >= 0; index--) { 
     y = array_a[index] + y * x; 
    } 
    return y; 
} 

यह 5 बार पाश y += array_a[index] * Math.Pow(x, index);

लेकिन मैं सोच अगर वहाँ इस बहुपद गणना करने के लिए एक बेहतर तरीका है की तुलना में तेजी है?

** किसी के लिए यह सोचता है कि यह एक अलग गणना है: मैंने ऊपर दिए गए कार्य का परीक्षण किया था। यह y += array_a[index] * Math.Pow(x, index); के साथ एक ही चीज़ करता है और वे एक ही परिणाम की गणना करते हैं।

धन्यवाद।

Answer 1

यह हॉर्नर विधि है।

... होर्नर की विधि केवल n जोड़ और n गुणा की आवश्यकता है, और उसके भंडारण आवश्यकताओं केवल n बार के बिट्स की संख्या इस प्रकार हैं: आप केवल बहुपद प्रति एक बार यह गणना करने के लिए, this is the most efficient algorithm चाहते हैं एक्स। ...

हॉर्नर विधि इष्टतम है, इस अर्थ में कि किसी भी एल्गोरिदम को मनमाने ढंग से बहुपद का मूल्यांकन करने के लिए कम से कम कई परिचालनों का उपयोग करना चाहिए। अलेक्जेंडर ओस्ट्रोस्की ने 1 9 54 में साबित किया कि आवश्यक जोड़ों की संख्या न्यूनतम है। विक्टर पैन 1 9 66 में साबित हुआ कि गुणा की संख्या न्यूनतम है।

आप बहुपद अत्यंत कई बार मूल्यांकन करने की जरूरत है और डिग्री बहुत अधिक है, तो बहुपद के प्रतिनिधित्व ( शर्त) ताकि गुणा की संख्या lfloor लिए & कम हो जाता है को बदलने के लिए तरीके हैं, एन/2 और आरएफएलआर; + 2. यह बहुत व्यावहारिक प्रतीत नहीं होता है, कम से कम मैंने इसे कभी जंगली में नहीं देखा है। I've found an online paper that describes some of the algorithms if you are interested।

public double cal(double x) { 
    double x2 = x * x; 
    double y_odd = 0.0, y_even = 0.0; 
    int index = array_a.length - 1; 
    if (index % 2 == 0) { 
     y_even = array_a[index]; 
     index -= 1; 
    } 
    for (; index >= 0; index -= 2) { 
     y_odd = array_a[index] + y_odd * x2; 
     y_even = array_a[index-1] + y_even * x2; 
    } 
    return y_even + y_odd * x; 
} 

JIT/संकलक हो सकता है:

इसके अलावा CPU वास्तुकला यह और अधिक कुशल हो सकता है अगर आप भी अजीब मामले को अलग से मूल्यांकन और इसलिए वे समानांतर पाइपलाइनों में रखा जा सकता की वजह से, समाचार पत्र में उल्लेख किया आपके लिए यह रूपांतरण करने में सक्षम है या इसे स्वचालित रूप से बहुत तेज़ बनाने के लिए सिमड का उपयोग भी कर सकते हैं। वैसे भी, इस तरह के सूक्ष्म अनुकूलन के लिए, अंतिम समाधान करने से पहले हमेशा प्रोफ़ाइल।