تقدير الجذر التربيعي

Question

أنا أكتب اي فون التطبيق الذي يحتاج إلى حساب الجذر التربيعي لعدد حوالي 2000 مرة كل 1/30 ثانية.الجذر التربيعي() يعمل بشكل جيد على جهاز كمبيوتر ، ولكن معدل الإطار تنخفض إلى حوالي 10 FPS على جهاز اي فون أو آي باد ، و لقد سبق الأمثل بقية التعليمات البرمجية.لقد سمعت أن هذا يمكن أن تسرع بشكل كبير من خلال تقدير الجذر التربيعي, ولكن أنا لا يمكن العثور على أي رمز للقيام بذلك.أحتاج فقط واحد أو اثنين من المنازل العشرية من الدقة.أي اقتراحات حول كيفية القيام بذلك ، أو طرق أخرى لتسريع الامور سيكون موضع تقدير.

وذلك بفضل!

Answer 1

مدى دقة هل تريد تقدير أن تكون ؟ إذا كنت تعرف كيفية إغلاق تريد تقدير أن يكون الحقيقية على الجذر التربيعي طريقة نيوتن هو صديقك.

هل تعرف مجموعة من القيم التي تم تمريرها إلى الجذر التربيعي?إذا كان يمكنك جعل ما يصل الى الجدول الذي هو precomputed عند بدء التشغيل (أو حتى القراءة من القرص عند بدء التشغيل اعتمادا على ما تتحول إلى أن تكون أسرع).العثور على أقرب في الجدول إلى المدخلات الخاصة بك وتحصل على التقدير الخاص بك.

Answer 2

إلا إذا كنت فعلا تحتاج الجذر التربيعي ، مقارنة تربيع القيم بدلا من الخام قيم الجذر التربيعي.

التوفيق هو أسرع بكثير (وأكثر دقة) من أخذ الجذر التربيعي ، إذا كنت تحتاج فقط المقارنات.هذه هي الطريقة الأكثر ألعاب تفعل ذلك.

Answer 3

هل تعرف مجموعة من القيم التي تحاول إيجاد الجذر التربيعي ؟ نقول لديك قيم تتراوح من 0 إلى 10.ثم يمكنك precalculate مجموعة:

sqrt_val[0] = 0;
sqrt_val[1] = 1;
sqrt_val[2] = // the sqrt of 2
...
sqrt_val[10] = // the sqrt of 10

ثم خلال وقت كنت تأخذ الرقم الذي تريد الجذر التربيعي من تحويل هذا إلى عدد صحيح (على سبيل المثال 3.123 يصبح 3) واستخدام ذلك مؤشر (3) للبحث عن precalculated القيمة.

بالطبع إذا كنت تريد الدقيقة القرار يمكنك فقط زيادة عدد العناصر في الصفيف الخاص بك.

Answer 4

أولا هل أنت متأكد أن الجذر التربيعي هو في الواقع عنق الزجاجة ؟ هل لمحة?2000 متر جذور كل 1/30 ثانية في الواقع ليست كثيرة حتى على الهاتف الخليوي.الذراع الوثائق ونقلت 33 دورة واحدة-الدقة الجذر التربيعي و 60 دورات مزدوجة الدقة ؛ أ 600mHz processor يمكن أن تفعل 10 مليون الجذور التربيعية في الثانية (أكثر إذا كان التعليم هو قيد الإعداد في كل شيء).

إذا كان لديك لمحة و الجذر التربيعي حقا هو عنق الزجاجة ، سوف تحتاج إلى استخدام النيون vrsqrte.f32 التعليمات.هذا الأمر هو سريع جدا و يعطيك التقريبية متبادلة الجذور التربيعية من أربعة أرقام الفاصلة العائمة في وقت واحد.ثم يمكنك استخدام vmul.f32 تعليمات الحصول على التقريبية الجذور التربيعية (على الرغم من العديد من الاستخدامات المتبادل هو أكثر فائدة من الجذر التربيعي نفسه).

Answer 5

ربما هذا هو بالنسبة لك:
سريع معكوس مربع الجذر
إذا كان هذا الأسلوب لا يوفر دقة تحتاج أيضا هناك الكثير من غيرها من أساليب متكررة حيث يمكنك اختيار أكثر أو أقل دقة بين السرعة والدقة:
طرق حوسبة الجذور التربيعية

Answer 6

أسهل تغيير يمكنك جعل على اي فون هو استخدام sqrtf() بدلا من الجذر التربيعي().دقة واحدة تطفو الرياضيات هو أسرع بكثير من الدقة المزدوجة ، خاصة على أجهزة 3GS خمر و أحدث.

Answer 7

إذا كنت في حاجة إلى الجذر التربيعي لحساب مثلث فيثاغورس (sqrt(x*x + y*y)), و كل من x و y هي غير سلبي ، ثم سريع جدا تقريب هذا هو

max(x,y) + min(x,y)*0.333

هذا أقصى خطأ من 5.7%.احترس من فرع misprediction في مين() وماكس() على الرغم من.

Answer 8

جوجل للبحث سريع يتحول كل أنواع الروابط.

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Approximations_that_depend_on_IEEE_representation

http://www.azillionmonkeys.com/qed/sqroot.html

Answer 9

إذا كان لديك "طبيعية" إيجابية تعويم أو مزدوجة ، لا int, و ترغب في استخدام طاولة البحث في الطريقة ، يمكنك أن تفعل اثنين من جدول منفصل عمليات البحث ، واحدة الأس (إعادة منحازة) و بضع قطع من العشري (shift و قناع bitfield استخراج) ، ثم ضرب اثنين الجدول تبدو النتائج معا.