तेज गणित एल्गोरिदम सटीकता बलिदान

Question

मैं एक ऐसा गेम विकसित कर रहा हूं जो भौतिकी और प्रतिपादन के लिए बहुत सारे गणित कार्यों को बुलाता है। Quake3 में "Fast inverse sqrt" एसकर्ट() से तेज़ होने के लिए जाना जाता है और इसकी पृष्ठभूमि सुंदर है।

क्या आप किसी भी अन्य एल्गोरिदम को जानते हैं जो स्वीकार्य शुद्धता हानि के साथ सामान्य से तेज है?

Answer 1

इन एल्गोरिदम को साहित्य में "सन्निकटन एल्गोरिदम" कहा जाता है। उदाहरण के साथ मानक पुस्तक Approximation Algorithms by Vijay V. Vazirani है।

पाप x ~~ x का मामला थोड़ा अधिक सामान्य मामला है: अपने कार्य के Taylor series (या आवधिक कार्यों के मामले में फूरियर श्रृंखला) देखें और केवल पहले कुछ शर्तों की गणना करें।

एक और (कुछ हद तक क्रूर) तकनीक यादृच्छिक रूप से आपके फ़ंक्शन के कुछ बिंदुओं को इकट्ठा करना है और उसके बाद एक रैखिक प्रतिगमन चलाएं। इस तरह, आप भी अपने कार्य का वर्णन करने वाला एक अच्छा बहुपद प्राप्त कर सकते हैं :)।

Answer 2

छोटे एक्स के लिए: sin (x) ~ = एक्स एक है कि अक्सर भौतिक विज्ञान में प्रयोग किया जाता

Answer 3

कुछ भी संभाव्य आम तौर पर इस तरह है। एक सिमुलेशन चलाना 10 गुना तेज होगा, लेकिन सिमुलेशन 1000 बार चलाने से कम सटीक परिणाम प्राप्त करेगा।

Answer 4

निको के कुछ अच्छे सुझाव हैं जिनके लिए मैं पुरानी फैशन लुकअप टेबल जोड़ूंगा।

मैंने परिपत्र कार्यों (पाप/कोस/तन) के लिए उच्च प्रदर्शन वास्तविक समय सिस्टेम में सफलतापूर्वक कई बार तालिका का उपयोग किया है। Sqrt() इस तरह से कठिन है, लेकिन यदि आपकी इनपुट सीमा प्रतिबंधित है (स्क्रीन पिक्सल कहने के लिए) गति के लिए हरा करना मुश्किल है, और आप अंतरिक्ष/सटीकता व्यापार को बिल्कुल ठीक कर सकते हैं। आप एक सामान्य श्रेणी के लिए लुकअप का भी उपयोग कर सकते हैं, और उसके बाद दुर्लभ मामले के लिए एक फ्रेमवर्क sqrt() फ़ंक्शन में गिरावट आ सकती है।

पॉल

Answer 5

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

टेलर श्रृंखला आमतौर पर एक खराब विकल्प होती है; चेबिसहेव या मिनिमैक्स बहुपदों में अधिकांश कम्प्यूटेशनल उपयोगों के लिए बहुत बेहतर त्रुटि विशेषताएं होती हैं। मिनीमैक्स बहुपदों को फिट करने के लिए मानक तकनीक रीमेस 'एल्गोरिदम का उपयोग करना है, जिसे बहुत सारे व्यावसायिक गणित सॉफ्टवेयर में लागू किया गया है, या यदि आप जानते हैं कि आप क्या कर रहे हैं तो आप अपने स्वयं के कार्यान्वयन को एक दिन के काम के साथ रोल कर सकते हैं।

रिकॉर्ड, "तेजी से उलटा वर्गमूल" के लिए, आधुनिक प्रोसेसर पर बचा जाना चाहिए के रूप में यह काफी हद तक तेजी से एक फ्लोटिंग प्वाइंट पारस्परिक वर्गमूल अनुमान अनुदेश (rsqrtss/rsqrtps SSE पर, vrsqrte नियोन पर, vrsqrtefp उपयोग करने के लिए है AltiVec पर)। यहां तक ​​कि (गैर-अनुमानित) हार्डवेयर वर्ग रूट वर्तमान इंटेल प्रोसेसर पर काफी तेज है।

Answer 6

कयामत स्रोत कोड, दो 2 डी अंक के बीच अनुमानित दूरी के लिए से sqrt() या त्रिकोणमितीय कार्यों का उपयोग किए बिना:

fixed_t P_AproxDistance(fixed_t dx, fixed_t dy) 
{ 
    dx = abs(dx); 
    dy = abs(dy); 
    if (dx < dy) 
     return dx+dy-(dx>>1); 
    else 
     return dx+dy-(dy>>1); 
} 

ध्यान दें कि x >> 1x/2 लेकिन थोड़ा तेजी के रूप में एक ही है - अच्छा आधुनिक compilers आजकल यह स्वचालित रूप से करें लेकिन फिर वापस वे बहुत अच्छे नहीं थे।