على الأرجح ، أنت تعرف النسب التالية من المدرسة:

$$

$$\ sin (\ alpha + \ beta) = \ sin \ alpha \ times \ cos \ beta + \ cos \ alpha \ times \ sin \ beta \\ \ cos (\ alpha + \ beta) = \ cos \ alpha \ times \ cos \ beta - \ sin \ alpha \ times \ sin \ beta$$

عندما تعرفت على هذه الصيغة لأول مرة في الطفولة ، على الأرجح ، كان شعورك الأول هو الألم بسبب حقيقة أنه يجب تذكر هذه الصيغة. هذا أمر سيء للغاية ، لأنه في الواقع لا تحتاج إلى تذكر هذه الصيغة - يتم عرضها عند تدوير المثلث على الورق. في الواقع ، أفعل نفس الشيء عندما أكتب هذه الصيغة. سيكون هذا التفسير واضحًا في منتصف هذه المقالة. ولكن الآن ، لترك كل المتعة في وقت لاحق ولتأجيل اللحظة التي تقول "Eureka!" ، دعنا نفكر في سبب تفكيرنا في هذه الصيغة.

دخول

ربما cos() الدوال المثلثية sin() و cos() الأكثر شيوعًا في رسومات الكمبيوتر ، لأنها أساس لوصف أي شكل دائري بطريقة حدودي. من بين الأماكن التي يمكن تطبيقها فيها إنشاء دوائر أو أشياء حجمية للثورة ، عند حساب تحويل فورييه ، والجيل الإجرائي للموجات على متن الطائرة المائية ، ومولدات لمولِّد صوت برنامج ، وما إلى ذلك. في كل هذه الحالات ، يتم استدعاء sin() و cos() داخل الحلقة ، كما يلي:

 for(int n=0; n < num; n++) { const float t = 2.0f*PI*(float)n/(float)num; const float s = sinf(t); const float c = cosf(t); // do something with s and c ... } 

نبدأ في إعادة كتابة الدورة بشكل تدريجي (انظر الكود أدناه) ، لذلك من الأسهل بالنسبة لنا أن نتخيل أنه في التكرار n هذه الدورة مع المرحلة t ، فإن التكرار التالي ، n+1 ، سينظر في sin() و cos() لـ t+f . بمعنى آخر ، يتم حساب sin(t) و cos(t) بالنسبة لنا ، ونحن بحاجة إلى حساب sin(t+f) و cos(t+f) :

 const float f = 2.0f*PI/(float)num; const float t = 0.0f; for( int n=0; n < num; n++ ) { const float s = sinf(t); const float c = cosf(t); // do something with s and c ... t += f; } 

لا يهم كيف حصلنا على t ومدى قيمها (في المثال أعلاه - $$$[0؛ 2 \ pi]$ ). الشيء الوحيد الذي يزعجنا هو أن هناك حلقة تستدعي باستمرار sin() و cos() مع معلمة تزداد بخطوات ثابتة (في هذه الحالة ، $$$\ frac {2 \ pi} {\ text {num}}$ ). تتناول هذه المقالة كيفية تحسين هذا الرمز للسرعة بطريقة يمكن إجراء نفس الحسابات على الإطلاق دون استخدام الدالات sin() أو cos() (في الحلقة الداخلية) ، وحتى الدالة sincos() الأسرع.

لكن إذا نظرت إلى الصيغة الأولى في المقالة ، فسنرى ذلك إذا $$$f = \ alpha$ و $$$t = \ beta$ يمكننا إعادة كتابة هذا باسم

 sin(t+f) = sin(f)*cos(t) + cos(f)*sin(t) cos(t+f) = cos(f)*cos(t) - sin(f)*sin(t) 

أو بعبارة أخرى

 new_s = sin(f)*old_c + cos(f)*old_s new_c = cos(f)*old_c - sin(f)*old_s 

بما أن f ثابت ، فإن sin(f) و cos(f) أيضًا. نسميها a و b على التوالي:

 new_s = b*old_c + a*old_s new_c = a*old_c - b*old_s 

يمكن استخدام هذا التعبير مباشرة في الكود الخاص بنا ، ثم نحصل على حلقة تسمى فيها الدوال المثلثية المكلفة (وفي الحقيقة لا).

 const float f = 2.0f*PI/(float)num; const float a = cosf(f); const float b = sinf(f); float s = 0.0f; float c = 1.0f; for( int n=0; n < num; n++ ) { // do something with s and c ... const float ns = b*c + a*s; const float nc = a*c - b*s; c = nc; s = ns; } 

ترجمة

حتى الآن ، كنا نلعب بشكل أعمى مع الرياضيات ، ولا نفهم ما يحدث بالفعل. دعنا نعيد كتابة الحلقة الداخلية مثل هذا:

$$

$$s_ {n + 1} = s_na + c_nb \\ c_ {n + 1} = c_na - s_nb$$

ربما لاحظ بعضكم أن هذه صيغة لتدوير كائن في مساحة ثنائية الأبعاد. إذا كنت لا تزال لا تفهم هذا ، فربما يساعدك نموذج المصفوفة.

$$

$$\ left (\ start {matrix} s_ {n + 1} \\ c_ {n + 1} \ end {matrix} \ right) = \ left (\ start {matrix} a & b \\ -b & a \ end {matrix} \ right) \ cdot \ left (\ start {matrix} s_ {n} \\ c_ {n} \ end {matrix} \ right)$$

في الواقع ، يمكن تجميع sin(t) و cos(t) في متجه طوله 1 ورسمه كنقطة على الشاشة. استدعاء هذا المتجه x . ثم، $$$x = \ {\ sin \ beta، \ cos \ beta \}$ . لذا فإن الشكل المتجه للتعبير هو $$$x_ {n + 1} = Rx_n$ حيث $$$R = \ left (\ start {matrix} a & b \\ - b & a \ end {matrix} \ right)$ . نرى أن حلقة لدينا تؤدي دوران صغير ثنائي الأبعاد لكل تكرار بحيث يتم تدوير x في دائرة أثناء تنفيذ الدورة. كل تكرار بالتناوب $$$\ frac {2 \ pi} {\ text {num}}$ راديان.
لذلك أساسا

$$

$$\ sin (\ alpha + \ beta) = \ sin \ alpha \ times \ cos \ beta + \ cos \ alpha \ times \ sin \ beta \\ \ cos (\ alpha + \ beta) = \ cos \ alpha \ times \ cos \ beta - \ sin \ alpha \ times \ sin \ beta$$

هذه هي صيغة حركة النقطة $$$x = \ {\ cos \ alpha، \ sin \ alpha \}$ محيط بزيادات $$$\ beta$ راديان. للقيام بذلك ، سنقوم ببناء واحد من محورين التناوب ، على سبيل المثال ، $$$u = \ {\ cos \ beta، \ sin \ beta \}$ . المكون الأول للدوران هو الإسقاط $$$x$ في $$$u$ . ل $$$x$ و $$$u$ تطبيع (لها طول 1) ، والإسقاط هو منتجهم العددية. لذلك، $$$s = x \ cdot u = \ sin \ alpha \ cdot \ cos \ beta + \ cos \ alpha \ cdot \ sin \ beta$ ، والمكون الثاني بالطبع هو الإسقاط المضاد ، والذي يمكن العثور عليه من خلال الإسقاط على المحور العمودي ، $$$v$ . يمكننا إنشاء هذا المتجه من خلال توسيع الإحداثيات $$$u$ وقم بتغيير الإشارة إلى الجهة المقابلة عند الإحداثيات الأولى: $$$c = x \ cdot v = \ cos \ alpha \ cdot \ cos \ beta + \ sin \ alpha \ cdot \ sin \ beta$

الملاحظات

عادة يجب أن تكون قادرًا على أداء هذه الدورات الصغيرة مرارًا وتكرارًا. في الحقيقة $$$| R | = \ left | \ start {matrix} a & b \\ - b & a \ end {matrix} \ right | = a ^ 2 + b ^ 2 = \ sin ^ 2 \ alpha + \ cos ^ 2 \ alpha = 1$ وهو ما يعني أن المصفوفة $$$R$ لا يزيد أو ينقص المساحة التي يتم تطبيقها ، مما يعني ذلك $$$x$ سوف تتحرك في دائرة مثالية. ومع ذلك ، لأن أجهزة الكمبيوتر ليست دقيقة ، $$$x$ سوف تتحرك في دوامة ويتزامن في نهاية المطاف مع مركز دائرة التناوب. لم أواجه مثل هذه المشكلات ، لكنني أعتقد أنها يمكن أن تحدث بعدد كبير جدًا ، أي زوايا تحول صغيرة.

مثال

في Kindercrasher ، عرض 4096 بايت من عام 2008 (لقطة شاشة على KDPV) ، وهي مجموعة من المجالات تنبض بالموسيقى. لهذا ، أحسب تحويل فورييه للصوت. هناك خوارزميات تقوم بذلك في الوقت الفعلي ، على سبيل المثال ، FFT . ومع ذلك ، يجب أن يتلاءم الكود الخاص بي مع عدد قليل من الكيلوبايت ، وقررت الذهاب في الاتجاه الآخر. بدلاً من تطبيق FFT ، كتبت DFT بتعريفه البسيط. يمكنك التحقق من ذلك على ويكيبيديا.

$$

$$X_k = \ sum_ {n = 0} ^ {N-1} {x_ne ^ {- \ frac {2 \ pi i} {N} kn}} \ quad k = 0،1 ، \ ldots ، N-1$$

تأخذ وظيفتي أيضًا مخزن صوت استريو 16 بت مؤقتًا ، x ، وتُرجع أول 128 ترددًا من الطيف الصوتي للصوت y . تعرف على كيفية تنظيم الحلقة الداخلية ، التي يتم تشغيلها 4096 مرة: لا توجد مكالمة واحدة لوظائف sin() أو cos() ، على الرغم من أن هذه الاستدعاءات ستكون في تطبيقات أخرى.

 #include <math.h> void iqDFT12( float *y, const short *x ) { for( int i=0; i<128; i++ ) { const float wi = (float)i*(2.0f*3.1415927f/4096.0f); const float sii = sinf( wi ); const float coi = cosf( wi ); float co = 1.0f; float si = 0.0f; float acco = 0.0f; float acsi = 0.0f; for( int j=0; j<4096; j++ ) { const float f = (float)(x[2*j+0]+x[2*j+1]); const float oco = co; acco += co*f; co = co*coi - si*sii; acsi += si*f; si = si*coi + oco*sii; } y[i] = sqrtf(acco*acco+acsi*acsi)*(1.0f/32767.0f); } }