كورديك

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 51 صور
الموسوعة الحرة

كورديك (CORDIC )، اختصارًا لـ "الحاسوب الرقمي لدوران الإحداثيات" ، هي خوارزمية بسيطة وفعالة لحساب الدوال المثلثية ، والدوال الزائدية ، والجذور التربيعية ، وعمليات الضرب ، والقسمة ، والأسس ، واللوغاريتمات ذات الأساس العشوائي، وعادةً ما تتقارب برقم واحد (أو بت) لكل تكرار. لذا، تُعد كورديك مثالًا على خوارزمية حساب الأرقام رقمًا برقم . ويُشار إلى النظام الأصلي أحيانًا باسم خوارزمية فولدر .

تُستخدم خوارزمية CORDIC والأساليب المشابهة لها، مثل الضرب الزائف والقسمة الزائفة أو دمج العوامل، بشكل شائع عندما لا يتوفر مُضاعِف مادي (كما هو الحال في المتحكمات الدقيقة البسيطة ومصفوفات البوابات المنطقية القابلة للبرمجة الميدانية FPGA)، حيث أن العمليات الوحيدة التي تتطلبها هي الجمع والطرح وإزاحة البتات وجداول البحث . ولذلك ، تنتمي جميعها إلى فئة خوارزميات الإزاحة والجمع . في علوم الحاسوب، تُستخدم خوارزمية CORDIC غالبًا لتنفيذ العمليات الحسابية ذات الفاصلة العائمة عندما تفتقر المنصة المستهدفة إلى الأجهزة اللازمة للضرب لأسباب تتعلق بالتكلفة أو المساحة. كان هذا هو الحال بالنسبة لمعظم الحواسيب الصغيرة المبكرة التي تعتمد على معالجات مثل MOS 6502 و Zilog Z80 .

على مر السنين، ظهر عدد من الاختلافات في المفهوم، بما في ذلك CORDIC الدائري ( جاك إي. فولدر )، [ 1 ] [ 2 ] وCORDIC الخطي ، و CORDIC الزائدي (جون ستيفن والثر)، [ 3 ] [ 4 ] و CORDIC الزائدي المعمم ( GH CORDIC ) (يوانيونغ لو وآخرون)، [ 5 ] [ 6 ]

مفهوم

بشكل عام، تتضمن خوارزمية CORDIC الأساسية تطبيق سلسلة من الدورانات المُقاسة على متجه. عوامل القياس وزوايا الدوران معروفة مسبقًا؛ فقط اتجاه كل دوران يعتمد على المُدخل. في وضع الدوران، تُؤخذ زاوية دوران مُستهدفة كمُدخل، ويتم اختيار اتجاهات الدوران بحيث تقترب زاوية الدوران المُتراكمة من الزاوية المُستهدفة. الناتج هو المتجه النهائي. في وضع التوجيه، يُؤخذ متجه كمُدخل، ويتم اختيار اتجاهات الدوران بحيث يقترب الإحداثي y للمتجه من الصفر. الناتج هو زاوية الدوران الكلية. راجع أوضاع التشغيل للاطلاع على التفاصيل الكاملة.

يتم اختيار عوامل القياس وزوايا الدوران بحيث يمكن حساب الدورانات المُقاسة باستخدام الجمع والطرح وإزاحة البتات فقط. ويتم استخراج الزوايا من جدول تم حسابه مسبقًا.

تاريخ

تم نشر تقنيات رياضية مماثلة بواسطة هنري بريجز في وقت مبكر من عام 1624 [ 7 ] [ 8 ] وروبرت  فلاور في عام 1771 [ 9 ] ولكن CORDIC مُحسَّن بشكل أفضل لوحدات المعالجة المركزية ذات الحالة المحدودة منخفضة التعقيد.

تم ابتكار نظام CORDIC عام 1956 [ 10 ] [ 11 ] على يد جاك إي. فولدر في قسم الإلكترونيات الجوية بشركة كونفير، وذلك لحاجة ملحة لاستبدال المحلل التناظري في حاسوب الملاحة الخاص بقاذفة القنابل B-58 بحل رقمي أكثر دقة وسرعة في الوقت الفعلي. [ 11 ] ولذلك، يُشار إلى نظام CORDIC أحيانًا باسم المحلل الرقمي . [ 12 ] [ 13 ]

في بحثه، استلهم فولدر من صيغة في طبعة عام 1946 من دليل CRC للكيمياء والفيزياء : [ 11 ]

كنRالخطيئة⁡(θ±φ)=Rالخطيئة⁡(θ)±2-نRكوس⁡(θ)،كنRكوس⁡(θ±φ)=Rكوس⁡(θ)∓2-نRالخطيئة⁡(θ)،// ),\\\النهاية {المحاذاة}}}

أينφ{\displaystyle \varphi }بحيثلون برونزي⁡(φ)=2-ن{\displaystyle \tan(\varphi )=2^{-n}}، وكن:=1+2-2ن{\displaystyle K_{n}:={\sqrt {1+2^{-2n}}}}.

أفضى بحثه إلى تقرير فني داخلي يقترح خوارزمية CORDIC لحل دوال الجيب وجيب التمام ، بالإضافة إلى نموذج أولي لحاسوب يُنفذها. [ 10 ] [ 11 ] كما ناقش التقرير إمكانية حساب دوران الإحداثيات الزائدية ، واللوغاريتمات ، والدوال الأسية باستخدام خوارزميات CORDIC مُعدلة. [ 10 ] [ 11 ] وتم في ذلك الوقت أيضًا التفكير في استخدام CORDIC للضرب والقسمة . [ 11 ] واستنادًا إلى مبدأ CORDIC، طور دان هـ. داجيت ، زميل فولدر في شركة كونفير، خوارزميات تحويل بين النظام الثنائي والنظام العشري المشفر ثنائيًا (BCD). [ 11 ] [ 14 ]  

في عام 1958، بدأت شركة كونفير أخيرًا في بناء نظام تجريبي لحل مشكلات تحديد المواقع بالرادار ، أُطلق عليه اسم كورديك 1 ، واكتمل بناؤه في عام 1960 بدون فولدر، الذي كان قد غادر الشركة بالفعل. [ 1 ] [ 11 ] وفي عام 1962، قام داجيت وهاري شوس ببناء واختبار نموذجين أكثر شمولية من كورديك 2 ، وهما النموذج أ (الثابت) والنموذج ب (المحمول جوًا). [ 11 ] [ 15 ]

تم وصف خوارزمية CORDIC الخاصة بفولدر علنًا لأول مرة في عام 1959، [ 1 ] [ 2 ] [ 11 ] [ 13 ] [ 16 ] مما أدى إلى دمجها في أجهزة الكمبيوتر الملاحية من قبل شركات مثل مارتن-أورلاندو ، وكمبيوتر كونترول ، وليتون ، وكيرفوت ، ولير-سيجلر ، وسبري ، ورايثيون ، وكولينز راديو . [ 11 ]

تعاون فولدر مع مالكولم ماكميلان لبناء أثينا ، وهي آلة حاسبة مكتبية ذات فاصلة ثابتة تستخدم خوارزمية CORDIC الثنائية الخاصة به. [ 17 ] عُرض التصميم على شركة هيوليت-باكارد في يونيو 1965، لكنه لم يُعتمد. [ 17 ] مع ذلك، عرّف ماكميلان ديفيد إس. كوكران (من شركة هيوليت-باكارد) على خوارزمية فولدر، وعندما التقى كوكران بفولدر لاحقًا، أشار إليه إلى نهج مشابه اقترحه جون إي. ميجيت (من شركة آي بي إم [ 18 ] ) كعملية ضرب وقسمة زائفة في عام 1961. [ 18 ] [ 19 ] كما اقترحت طريقة ميجيت استخدام الأساس 10 [ 18 ] بدلًا من الأساس 2 ، كما هو مستخدم في خوارزمية CORDIC الخاصة بفولدر حتى ذلك الحين. أدت هذه الجهود إلى تنفيذ نموذج أولي لآلة حاسبة عشرية من نوع CORDIC باستخدام منطق قابل للقراءة فقط داخل شركة هيوليت-باكارد عام 1966، [ 20 ] [ 19 ] وقد بُنيت هذه الآلة واستُمدت مفاهيميًا من آلة غرين ماشين النموذجية التي صممها توماس إي. أوزبورن ، وهي آلة حاسبة مكتبية ذات أربع وظائف تعمل بنظام الفاصلة العائمة ، كان قد أنجزها باستخدام منطق DTL [ 17 ] في ديسمبر 1964. [ 21 ] نتج عن هذا المشروع عرضٌ عام لأول آلة حاسبة مكتبية من هيوليت-باكارد مزودة بوظائف علمية، وهي HP 9100A ، في مارس 1968، وبدأ الإنتاج التسلسلي في وقت لاحق من ذلك العام. [ 17 ] [ 21 ] [ 22 ] [ 23 ]

عندما اكتشفت مختبرات وانغ أن جهاز HP  9100A يستخدم نهجًا مشابهًا لطريقة دمج العوامل في آلاتها الحاسبة المكتبية السابقة LOCI-1 [ 24 ] (سبتمبر 1964) و LOCI-2 (يناير 1965) [ 25 ] [ 26 ] لحساب اللوغاريتمات ، [ 27 ] اتهمت شركة هيوليت-باكارد بانتهاك إحدى براءات اختراع آن وانغ في عام 1968، ولكن دون جدوى. [ 19 ] [ 28 ] [ 29 ] [ 30 ]

قام جون ستيفن والثر في شركة هيوليت-باكارد بتعميم الخوارزمية لتصبح خوارزمية CORDIC الموحدة في عام 1971، مما سمح لها بحساب الدوال الزائدية ، والدوال الأسية الطبيعية ، واللوغاريتمات الطبيعية ، وعمليات الضرب ، والقسمة ، والجذور التربيعية . [ 31 ] [ 3 ] [ 4 ] [ 32 ] ويمكن لبرامج CORDIC الفرعية للدوال المثلثية والزائدية أن تتشارك معظم شفرتها البرمجية. [ 28 ] وقد أدى هذا التطور إلى ظهور أول آلة حاسبة علمية محمولة ، وهي HP-35 في عام 1972. [ 28 ] [ 33 ] [ 34 ] [ 35 ] [ 36 ] [ 37 ] وبناءً على خوارزمية CORDIC الزائدية، قام يوانيونغ لو وآخرون... اقترح أيضًا في عام 2019 طريقة CORDIC الزائدية المعممة (GH CORDIC) لحساب اللوغاريتمات والدوال الأسية مباشرةً باستخدام أساس ثابت اختياري. [ 5 ] [ 6 ] [ 38 ] [ 39 ] [ 40 ] نظريًا، تُعد طريقة CORDIC الزائدية حالة خاصة من طريقة GH CORDIC. [ 5 ]

في الأصل، طُبِّقَ نظام CORDIC باستخدام النظام الثنائي فقط ، وعلى الرغم من اقتراح ميجيت استخدام النظام العشري لنهجه في الضرب الزائف، ظل نظام CORDIC العشري غير معروفٍ إلى حد كبير لسنوات عديدة، حتى أن هيرمان شميد وأنتوني بوغاكي استمرا في اقتراحه كابتكار حتى عام 1973 [ 16 ] [ 13 ] [ 41 ] [ 42 ] [ 43 ] ، ولم يُكتشف إلا لاحقًا أن شركة هيوليت-باكارد قد طبقته بالفعل في عام 1966. [ 11 ] [ 13 ] [ 20 ] [ 28 ]

أصبح نظام CORDIC العشري شائع الاستخدام في الآلات الحاسبة الجيبية ، [ 13 ] والتي يعمل معظمها بنظام العد العشري المشفر ثنائيًا (BCD) بدلاً من النظام الثنائي. لم يؤثر هذا التغيير في تنسيق الإدخال والإخراج على خوارزميات الحساب الأساسية لنظام CORDIC. يُعد نظام CORDIC مناسبًا بشكل خاص للآلات الحاسبة المحمولة، حيث تُعد التكلفة المنخفضة - وبالتالي عدد البوابات المنطقية المنخفض - أكثر أهمية من السرعة.

تم تطبيق CORDIC في معالجات ARM-based STM32G4 و Intel 8087 و [ 43 ] [ 44 ] [ 45 ] [ 46 ] [ 47 ] و 80287 و [ 47 ] [ 48 ] و 80387 و [ 47 ] [ 48 ] وصولاً إلى سلسلة المعالجات المساعدة 80486 [ 43 ] وكذلك في معالجات Motorola 68881 و 68882 لبعض أنواع تعليمات الفاصلة العائمة ، وذلك بشكل أساسي كوسيلة لتقليل عدد البوابات (والتعقيد) للنظام الفرعي FPU .

التطبيقات

تستخدم خوارزمية CORDIC عمليات الإزاحة والجمع البسيطة في العديد من المهام الحسابية، مثل حساب الدوال المثلثية والزائدية واللوغاريتمية، والضرب والقسمة الحقيقية والمركبة، وحساب الجذر التربيعي، وحل الأنظمة الخطية، وتقدير القيم الذاتية ، وتحليل القيم المفردة ، وتحليل QR ، وغيرها الكثير. ونتيجةً لذلك، استُخدمت خوارزمية CORDIC في تطبيقات متنوعة في مجالات مثل معالجة الإشارات والصور ، وأنظمة الاتصالات ، والروبوتات ، والرسومات ثلاثية الأبعاد، بالإضافة إلى الحوسبة العلمية والتقنية العامة. [ 49 ] [ 50 ]

الأجهزة

استُخدمت الخوارزمية في نظام الملاحة لمركبة أبولو القمرية لحساب الاتجاه والمدى ، أو المسافة من الوحدة القمرية . [ 51 ] [ 52 ] استُخدمت خوارزمية CORDIC لتنفيذ المعالج المساعد الرياضي Intel 8087 في عام 1980، مما أغنى عن الحاجة إلى تنفيذ عملية الضرب على مستوى الأجهزة. [ 53 ]

تُعدّ خوارزمية CORDIC أسرع عمومًا من الطرق الأخرى عندما لا يتوفر مُضاعِف مادي (مثل المتحكم الدقيق)، أو عندما يكون من الضروري تقليل عدد البوابات اللازمة لتنفيذ الوظائف التي تدعمها (مثل الدوائر المتكاملة القابلة للبرمجة FPGA أو الدوائر المتكاملة الخاصة بالتطبيقات ASIC ). في الواقع، تُعتبر CORDIC وحدة IP قياسية جاهزة للاستخدام في تطبيقات تطوير FPGA مثل Vivado من Xilinx، بينما لا يُعدّ تنفيذ متسلسلات القوى كذلك نظرًا لخصوصية هذه الوحدة، أي أن CORDIC قادرة على حساب العديد من الوظائف المختلفة (للأغراض العامة)، بينما لا يستطيع المُضاعِف المادي المُصمّم لتنفيذ متسلسلات القوى سوى حساب الوظيفة التي صُمّم من أجلها.

من جهة أخرى، عندما يتوفر مُضاعِف مادي ( كما هو الحال في معالج الإشارات الرقمية DSP )، فإن طرق البحث في الجداول ومتسلسلات القوى تكون أسرع عمومًا من خوارزمية CORDIC. في السنوات الأخيرة، استُخدمت خوارزمية CORDIC على نطاق واسع في تطبيقات طبية حيوية متنوعة، لا سيما في تطبيقات FPGA.

تُطبّق سلسلة معالجات STM32G4 و STM32U5 و STM32H5 ، بالإضافة إلى بعض معالجات STM32H7، وحدة CORDIC لتسريع العمليات الحسابية في تطبيقات الإشارات المختلطة المختلفة، مثل الرسومات الخاصة بواجهات التفاعل بين الإنسان والآلة ، والتحكم الموجه للمجال في المحركات. ورغم أن سرعة CORDIC ليست بمستوى تقريب متسلسلة القوى، إلا أنها أسرع من تطبيقات الجداول الاستيفائية، كتلك التي توفرها مكتبات ARM CMSIS وC القياسية. [ 54 ] مع ذلك، قد تكون النتائج أقل دقةً بعض الشيء، إذ لا تتجاوز دقة وحدات CORDIC المُقدّمة 20 بتًا. فعلى سبيل المثال، يُعزى معظم فرق الأداء مقارنةً بتطبيق ARM إلى عبء خوارزمية الاستيفاء، التي تحقق دقة كاملة للفاصلة العائمة (24 بتًا)، ومن المرجح أن تصل نسبة الخطأ فيها إلى تلك الدقة. [ 55 ] ومن المزايا الأخرى أن وحدة CORDIC تُعدّ معالجًا مساعدًا، ويمكن تشغيلها بالتوازي مع مهام وحدة المعالجة المركزية الأخرى.

تكمن مشكلة استخدام متسلسلات تايلور في أنها، على الرغم من أنها توفر خطأً مطلقًا صغيرًا، إلا أنها لا تُظهر خطأً نسبيًا منتظمًا. [ 56 ] ويمكن استخدام وسائل أخرى لتقريب كثيرات الحدود، مثل تحسين المينيماكس ، للتحكم في كلا نوعي الخطأ.

برمجة

قامت العديد من الأنظمة القديمة المزودة بوحدات معالجة مركزية للأعداد الصحيحة فقط بتطبيق خوارزمية CORDIC بدرجات متفاوتة كجزء من مكتبات IEEE الخاصة بها للأعداد العشرية . وبما أن معظم وحدات المعالجة المركزية الحديثة للأغراض العامة تحتوي على سجلات للأعداد العشرية تتضمن عمليات شائعة مثل الجمع والطرح والضرب والقسمة والجيب وجيب التمام والجذر التربيعي واللوغاريتم العشري واللوغاريتم الطبيعي، فإن الحاجة إلى تطبيق خوارزمية CORDIC فيها برمجياً تكاد تكون معدومة. ولا تحتاج إلى استخدام خوارزمية CORDIC إلا في تطبيقات المتحكمات الدقيقة أو التطبيقات البرمجية الخاصة التي تتطلب مراعاة معايير السلامة والوقت.

أنماط التشغيل

وضع الدوران

يمكن استخدام دالة CORDIC لحساب عدد من الدوال المختلفة. يوضح هذا الشرح كيفية استخدام CORDIC في وضع الدوران لحساب جيب وجيب تمام زاوية، بافتراض أن الزاوية المطلوبة معطاة بالراديان وممثلة بنظام النقطة الثابتة. لتحديد جيب أو جيب تمام زاويةβ{\displaystyle \beta }يجب إيجاد الإحداثي y أو x لنقطة على دائرة الوحدة التي تُقابل الزاوية المطلوبة. باستخدام دالة CORDIC ، يبدأ المرء بالمتجهv0{\displaystyle v_{0}}:

v0=[10].{\displaystyle v_{0}={\begin{bmatrix}1\\0\end{bmatrix}}.}
رسم توضيحي لخوارزمية CORDIC قيد التطوير

في التكرار الأول، يتم تدوير هذا المتجه 45 درجة عكس اتجاه عقارب الساعة للحصول على المتجهv1{\displaystyle v_{1}}تُدير التكرارات المتتالية المتجه في أحد الاتجاهين بخطوات متناقصة الحجم، حتى يتم الوصول إلى الزاوية المطلوبة. زاوية كل خطوة هيγأنا=دالة الظل العكسي⁡(2-أنا){\displaystyle \gamma _{i}=\arctan {(2^{-i})}}لأنا=0،1،2،...{\displaystyle i=0,1,2,\dots }.

بصورة أكثر رسمية، تحسب كل تكرار عملية دوران، والتي تتم عن طريق ضرب المتجهvأنا{\displaystyle v_{i}}باستخدام مصفوفة الدورانRأنا{\displaystyle R_{i}}:

vأنا+1=Rأناvأنا.{\displaystyle v_{i+1}=R_{i}v_{i}.}

مصفوفة الدوران معطاة بواسطة

Rأنا=[كوس⁡(γأنا)-الخطيئة⁡(γأنا)الخطيئة⁡(γأنا)كوس⁡(γأنا)].{\displaystyle R_{i}={\begin{bmatrix}\cos(\gamma _{i})&-\sin(\gamma _{i})\\\sin(\gamma _{i})&\cos(\gamma _{i})\end{bmatrix}}.}

باستخدام المتطابقة المثلثية :

لون برونزي⁡(γأنا)≡الخطيئة⁡(γأنا)كوس⁡(γأنا)،{\displaystyle {\begin{aligned}\tan(\gamma _{i})&\equiv {\frac {\sin(\gamma _{i})}{\cos(\gamma _{i})}},\end{aligned}}}

يمكن استخراج عامل جيب التمام لنحصل على:

Rأنا=كوس⁡(γأنا)[1-لون برونزي⁡(γأنا)لون برونزي⁡(γأنا)1].{\displaystyle R_{i}=\cos(\gamma _{i}){\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}.}

صيغة المتجه المُدارvأنا+1=Rأناvأنا{\displaystyle v_{i+1}=R_{i}v_{i}}ثم يصبح:

[xأنا+1yأنا+1]=كوس⁡(γأنا)[1-لون برونزي⁡(γأنا)لون برونزي⁡(γأنا)1][xأناyأنا]،{\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}=\cos(\gamma _{i}){\begin{bmatrix}1&-\tan(\gamma _{i})\\\tan(\gamma _{i})&1\end{bmatrix}}{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}},}

أينxأنا{\displaystyle x_{i}}وyأنا{\displaystyle y_{i}}هي مكوناتvأنا{\displaystyle v_{i}}ضبط الزاويةγأنا{\displaystyle \gamma _{i}}لكل تكرار بحيثلون برونزي⁡(γأنا)=±2-أنا{\displaystyle \tan(\gamma _{i})=\pm 2^{-i}}لا يزال ينتج عنه متسلسلة تتقارب إلى كل قيمة ناتجة ممكنة. لذلك، يمكن استبدال الضرب بدالة الظل بالقسمة على قوة من قوى العدد اثنين، وهو ما يتم بكفاءة في أجهزة الحاسوب الرقمية باستخدام إزاحة البتات . يصبح التعبير حينها كالتالي:

[xأنا+1yأنا+1]=كوس⁡(دالة الظل العكسي⁡(2-أنا))[1-σأنا2-أناσأنا2-أنا1][xأناyأنا]،{\displaystyle {\begin{bmatrix}x_{i+1}\\y_{i+1}\end{bmatrix}}=\cos(\arctan(2^{-i})){\begin{bmatrix}1&-\sigma _{i}2^{-i}\\\sigma _{i}2^{-i}&1\end{bmatrix}}{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}},}

في أيσأنا{\displaystyle \sigma _{i}}يحدد اتجاه الدوران. إذا كانت زاوية الدورانγأنا{\displaystyle \gamma _{i}}أن تكون إيجابياً،σأنا{\displaystyle \sigma _{i}}تكون قيمته +1، وإلا تكون قيمته -1.

يمكن استخدام المتطابقة المثلثية التالية لاستبدال جيب التمام:

كوس⁡(γأنا)≡11+لون برونزي2⁡γأنا{\displaystyle \cos(\gamma _{i})\equiv {\frac {1}{\sqrt {1+\tan ^{2}{\gamma _{i}}}}}}،

إعطاء هذا المضاعف لكل تكرار:

كأنا=كوس⁡(دالة الظل العكسي⁡(2-أنا))=11+2-2أنا.{\displaystyle K_{i}=\cos(\arctan(2^{-i}))={\frac {1}{\sqrt {1+2^{-2i}}}}.}

الكأنا{\displaystyle K_{i}}يمكن بعد ذلك إخراج العوامل من العملية التكرارية وتطبيقها دفعة واحدة لاحقًا باستخدام عامل قياس.ك(ن){\displaystyle K(n)}:

ك(ن)=∏أنا=0ن-1كأنا=∏أنا=0ن-111+2-2أنا،{\displaystyle K(n)=\prod _{i=0}^{n-1}K_{i}=\prod _{i=0}^{n-1}{\frac {1}{\sqrt {1+2^{-2i}}}},}

يتم حساب ذلك مسبقًا وتخزينه في جدول أو كقيمة ثابتة واحدة، إذا كان عدد التكرارات محددًا. ويمكن أيضًا إجراء هذا التصحيح مسبقًا عن طريق تغيير المقياس.v0{\displaystyle v_{0}}وبالتالي توفير عملية الضرب. بالإضافة إلى ذلك، تجدر الإشارة إلى أن [ 43 ]

ك=ليمن→∞ك(ن)≈0.6072529350088812561694{\displaystyle K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694}

للسماح بمزيد من تقليل تعقيد الخوارزمية. قد تتجنب بعض التطبيقات تصحيح ذلك.ك{\displaystyle K}بشكل عام، مما يؤدي إلى زيادة في المعالجةأ{\displaystyle A}: [ 57 ]

أ=1ك=ليمن→∞∏أنا=0ن-11+2-2أنا≈1.64676025812107.{\displaystyle A={\frac {1}{K}}=\lim _{n\to \infty }\prod _{i=0}^{n-1}{\sqrt {1+2^{-2i}}}\approx 1.64676025812107.}

بعد عدد كافٍ من التكرارات، ستكون زاوية المتجه قريبة من الزاوية المطلوبةβ{\displaystyle \beta }. بالنسبة لمعظم الأغراض العادية، فإن 40 تكرارًا ( n  =  40) كافية للحصول على النتيجة الصحيحة حتى المنزلة العشرية العاشرة.

المهمة الوحيدة المتبقية هي تحديد ما إذا كان الدوران يجب أن يكون في اتجاه عقارب الساعة أو عكس اتجاه عقارب الساعة في كل تكرار (اختيار قيمةσ{\displaystyle \sigma }يتم ذلك عن طريق تتبع مقدار دوران الزاوية في كل تكرار وطرح ذلك من الزاوية المطلوبة؛ ثم من أجل الاقتراب أكثر من الزاوية المطلوبةβ{\displaystyle \beta }، لوβن+1{\displaystyle \beta _{n+1}}إذا كانت القيمة موجبة، يكون الدوران باتجاه عقارب الساعة، وإلا فإنها تكون سالبة ويكون الدوران عكس اتجاه عقارب الساعة:

β0=β{\displaystyle \beta _{0}=\beta }
βأنا+1=βأنا-σأناγأنا،γأنا=دالة الظل العكسي⁡(2-أنا).{\displaystyle \beta _{i+1}=\beta _{i}-\sigma _{i}\gamma _{i},\quad \gamma _{i}=\arctan(2^{-i}).}

قيمγن{\displaystyle \gamma _{n}}يجب أيضًا حسابها مسبقًا وتخزينها. بالنسبة للزوايا الصغيرة، يمكن تقريبها باستخدامدالة الظل العكسي⁡(γن)≈γن{\displaystyle \arctan(\gamma _{n})\approx \gamma _{n}}لتقليل حجم الطاولة.

كما هو موضح في الرسم التوضيحي أعلاه، فإن جيب الزاويةβ{\displaystyle \beta }يمثل الإحداثي y للمتجه النهائيvن،{\displaystyle v_{n},}بينما يمثل الإحداثي السيني قيمة جيب التمام.

وضع التوجيه

تستطيع خوارزمية وضع الدوران الموضحة أعلاه تدوير أي متجه (وليس فقط متجه وحدة محاذٍ للمحور السيني ) بزاوية تتراوح بين -90° و+90°. وتعتمد قرارات اتجاه الدوران علىβأنا{\displaystyle \beta _{i}}أن يكون إيجابياً أو سلبياً.

يتطلب نمط التشغيل المتجهي تعديلًا طفيفًا للخوارزمية. يبدأ بمتجه إحداثي س موجب، بينما إحداثي ص اختياري. تهدف عمليات الدوران المتتالية إلى تدوير المتجه حول محور س (وبالتالي تقليل إحداثي ص إلى الصفر). في كل خطوة، تحدد قيمة ص اتجاه الدوران. القيمة النهائية لـβأنا{\displaystyle \beta _{i}}تحتوي على زاوية الدوران الكلية. ستكون القيمة النهائية لـ x هي مقدار المتجه الأصلي مضروبًا في K. لذا، فإن أحد الاستخدامات الواضحة لنمط المتجهات هو التحويل من الإحداثيات الديكارتية إلى الإحداثيات القطبية.

تطبيق

في لغة جافا، تحتوي فئة الرياضيات على scalb(double x, int scale)دالة لإجراء هذا التحويل، [ 58 ] وتحتوي لغة سي على دالة ldexp ، [ 59 ] وتحتوي فئة معالجات x86 على fscaleعملية الفاصلة العائمة. [ 60 ]

مثال برمجي (بايثون)

from math import atan2 , sqrt , sin , cos , radiansعدد التكرارات = 16theta_table = [ atan2 ( 1 , 2 ** i ) for i in range ( ITERS )]دالة حساب_K ( ن ):""" احسب K(n) عندما n = ITERS. يمكن أن يكون هذا أيضًا يتم تخزينها كثابت صريح إذا تم تثبيت ITERS أعلاه. """k = 1.0for i in range ( n ):ك *= 1 / جذر ( 1 + 2 ** ( - 2 * ط ))إرجاع kdef cordic ( alpha : float , n : int ) -> tuple [ float , float ]:افترض أن n <= ITERSK_n = compute_K ( n )θ = 0.0x = 1.0ص = 0.0P2i = 1 # ستكون هذه القيمة 2**(-i) في الحلقة أدناهfor arc_tangent in theta_table [: n ]:سيجما = +1 إذا كانت ثيتا < ألفا ، وإلا -1theta += sigma * arc_tangentس , ص = س - سيجما * ص * P2i , سيجما * P2i * س + صP2i /= 2أرجع x * K_n و y * K_nإذا كان __name__ يساوي "__main__" :# اطبع جدولاً بقيم الجيب وجيب التمام المحسوبة، من -90° إلى +90°، بخطوات مقدارها 15°،# مقارنة بالبرامج الرياضية المتاحة.print ( " x sin(x) diff. sin cos(x) diff. cosine " )for x in range ( - 90 , 91 , 15 ):cos_x , sin_x = كورديك ( راديان ( x ), ITERS )مطبعة (f " { x : +05.1f } ° { sin_x : +.8f } ( { sin_x - sin ( radians ( x )) : +.8f } ) { cos_x : +.8f } ( { cos_x - cos ( radians ( x )) : +.8f } )")

الناتج

$ python cordic.py  x sin(x) diff. sin cos(x) diff. جيب التمام -90.0° -1.00000000 (+0.00000000) -0.00001759 (-0.00001759) -75.0° -0.96592181 (+0.00000402) +0.25883404 (+0.00001499) -60.0° -0.86601812 (+0.00000729) +0.50001262 (+0.00001262) -45.0° -0.70711776 (-0.00001098) +0.70709580 (-0.00001098) -30.0° -0.50001262 (-0.00001262) +0.86601812 (-0.00000729) -15.0° -0.25883404 (-0.00001499) +0.96592181 (-0.00000402) +00.0° +0.00001759 (+0.00001759) +1.00000000 (-0.00000000) +15.0° +0.25883404 (+0.00001499) +0.96592181 (-0.00000402) +30.0° +0.50001262 (+0.00001262) +0.86601812 (-0.00000729) +45.0° +0.70709580 (-0.00001098) +0.70711776 (+0.00001098) +60.0° +0.86601812 (-0.00000729) +0.50001262 (+0.00001262) +75.0° +0.96592181 (-0.00000402) +0.25883404 (+0.00001499) +90.0° +1.00000000 (-0.00000000) -0.00001759 (-0.00001759)

مثال على الأجهزة

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

التكرارات المزدوجة CORDIC

في اثنتين من منشورات فلاديمير بايكوف، [ 61 ] [ 62 ] اقترح استخدام طريقة التكرار المزدوج لتنفيذ الدوال التالية: دالة الجيب العكسية، ودالة جيب التمام العكسية، واللوغاريتم الطبيعي، والدالة الأسية، بالإضافة إلى حساب الدوال الزائدية. تعتمد طريقة التكرار المزدوج على أنه على عكس طريقة CORDIC التقليدية، حيث تتغير قيمة خطوة التكرار في كل تكرار، فإن قيمة خطوة التكرار في طريقة التكرار المزدوج تُكرر مرتين وتتغير خلال تكرار واحد فقط. في الوقت نفسه، عندما تكون قيمة i ثابتة، فإن إشارة (اتجاه) التكرار، أي + أو - (مع عقارب الساعة أو عكس عقارب الساعة)، تعتمد على إشارة المتغير الذي يتم اختزاله إلى الصفر. ومن هنا جاء مصطلح مؤشر الدرجة للتكرار المزدوج.أنا=0،0،1،1،2،2...{\displaystyle i=0,0,1,1,2,2\dots }أما مع التكرارات العادية:أنا=0،1،2...{\displaystyle i=0,1,2\dots }تضمن طريقة التكرار المزدوج تقارب الطريقة في جميع أنحاء النطاق الصحيح لتغييرات الوسائط.

تعميم مسائل تقارب CORDIC لنظام الأعداد الموضعية العشوائي ذي الأساسR{\displaystyle R}أظهرت [ 63 ] أنه بالنسبة للدوال الجيبية، وجيب التمام، وظل الزاوية العكسي، يكفي إجراءR-1{\displaystyle R-1}تكرارات لكل قيمة من قيم i (حيث i = 0 أو 1 إلى n، و n هو عدد الأرقام)، أي لكل رقم من أرقام النتيجة. بالنسبة للوغاريتم الطبيعي، والدالة الأسية، والجيب الزائدي، وجيب التمام، وظل الزاوية العكسي،R{\displaystyle R}ينبغي إجراء عمليات تكرار لكل قيمةأنا{\displaystyle i}بالنسبة للدالتين arcsine و arccosine، اثنانR-1{\displaystyle R-1}ينبغي إجراء عمليات تكرارية لكل رقم، أي لكل قيمة من قيمأنا{\displaystyle i}[ 63 ]​

بالنسبة لدوال الجيب الزائدي العكسي ودالة الجيب العكسي، سيكون عدد التكرارات هو2R{\displaystyle 2R}لكلأنا{\displaystyle i}أي لكل رقم من أرقام النتيجة.

تُعدّ خوارزمية CORDIC جزءًا من فئة خوارزميات "الإزاحة والجمع" ، شأنها شأن خوارزميات اللوغاريتم والأس المشتقة من أعمال هنري بريغز. ومن خوارزميات الإزاحة والجمع الأخرى التي يمكن استخدامها لحساب العديد من الدوال الأساسية خوارزمية BKM ، وهي تعميم لخوارزميات اللوغاريتم والأس لتشمل المستوى المركب. على سبيل المثال، يمكن استخدام BKM لحساب جيب وجيب تمام زاوية حقيقية.x{\displaystyle x}(بالراديان) عن طريق حساب الدالة الأسية لـ0+أناx{\displaystyle 0+ix}، وهوcis⁡(x)=كوس⁡(x)+أناالخطيئة⁡(x){\displaystyle \operatorname {cis} (x)=\cos(x)+i\sin(x)}خوارزمية BKM أكثر تعقيدًا بقليل من خوارزمية CORDIC، ولكن لها ميزة أنها لا تحتاج إلى عامل قياس ( K ).

انظر أيضاً

مراجع

  1. 1 2 3 فولدر، جاك إي. (3 مارس 1959). "تقنية الحوسبة CORDIC" (ملف PDF) . وقائع المؤتمر المشترك الغربي للحاسوب (عرض تقديمي). سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية: اللجنة الوطنية المشتركة للحاسوب : 257-261 . تاريخ الاسترجاع : 2 يناير 2016 .
  2. 1 2 فولدر، جاك إي. (25 مايو 1959). "تقنية الحساب المثلثي CORDIC" (ملف PDF) . معاملات معهد مهندسي الراديو (IRE) في الحواسيب الإلكترونية . 8 (3). معهد مهندسي الراديو (IRE) (نُشر في سبتمبر 1959): 330-334 (إعادة طبع: 226-230). رمز Bibcode : 1959IRTEC...8..330V . doi : 10.1109/TEC.1959.5222693 . EC-8(3):330–334. مؤرشف من الأصل (ملف PDF) في 12 يونيو 2021. تم الاسترجاع في 1 يناير 2016 .
  3. 1 2 والثر، جون ستيفن (مايو 1971). كُتب في بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية. "خوارزمية موحدة للدوال الأولية" (ملف PDF) . وقائع المؤتمر المشترك الربيعي للحاسوب . 38. أتلانتيك سيتي، نيو جيرسي، الولايات المتحدة الأمريكية: شركة هيوليت-باكارد : 379-385 . مؤرشف من الأصل (ملف PDF) في 12 يونيو 2021. تم الاسترجاع في 1 يناير 2016 - عبر الاتحاد الأمريكي لجمعيات معالجة المعلومات (AFIPS).
  4. 1 2 والثر، جون ستيفن (يونيو 2000). "قصة خوارزمية CORDIC الموحدة" . مجلة معالجة إشارات VLSI . 25 (2 (عدد خاص عن CORDIC)). هينغهام، ماساتشوستس، الولايات المتحدة الأمريكية: دار نشر كلوير الأكاديمية : 107-112 . رمز Bibcode : 2000JSPSy..25..107W . doi : 10.1023/A:1008162721424 . ISSN 0922-5773 . S2CID 26922158 .  
  5. 1 2 3 لو، يوانيونغ؛ وانغ، يوكسوان؛ ها، ياجون؛ وانغ، تشونغفنغ؛ تشين، سييوان؛ بان، هونغبينغ (سبتمبر 2019). "خوارزمية CORDIC الزائدية المعممة وحسابها اللوغاريتمي والأسّي مع أساس ثابت اختياري". معاملات IEEE لأنظمة التكامل واسع النطاق جدًا (VLSI) . 27 (9): 2156-2169 . Bibcode : 2019ITVL...27.2156L . doi : 10.1109/TVLSI.2019.2919557 . S2CID 196171166 . 
  6. 1 2 لو، يوانيونغ؛ وانغ، يوكسوان؛ ها، ياجون؛ وانغ، تشونغفنغ؛ تشين، سييوان؛ بان، هونغبينغ (سبتمبر 2019). "تصحيحات على "خوارزمية CORDIC الزائدية المعممة وحسابها اللوغاريتمي والأسّي مع أساس ثابت اختياري"". IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 27 (9): 2222. Bibcode : 2019ITVL...27.2222L . doi : 10.1109/TVLSI.2019.2932174 . S2CID 201711001. " 
  7. ↑ بريغز، هنري (1624). الحساب اللوغاريتمي . لندن.(ترجمة:(أُرشف في 4 مارس 2016 على موقع Wayback Machine )
  8. ↑ لابورت، جاك (2014) [2005]. "هنري بريغز وHP 35" . باريس، فرنسا. مؤرشف من الأصل بتاريخ 9 مارس 2015. تم الاطلاع عليه بتاريخ 2 يناير 2016 .أُرشف بتاريخ 10 أغسطس 2020 في أرشيف الإنترنت (Wayback Machine) .
  9. ↑ فلاور، روبرت (1771). الجذر: طريقة جديدة لعمل اللوغاريتمات . لندن: ج. بيكروفت . تم الاسترجاع في 2016-01-02 .
  10. 1 2 3 فولدر، جاك إي. (15-06-1956)، خوارزميات الحساب الثنائي لتدوير الإحداثيات وتوليد الدوال (تقرير داخلي)، كونفير ، مجموعة الإلكترونيات الجوية، IAR-1.148
  11. 1 2 3 4 5 6 7 8 9 10 11 12 فولدر، جاك إي. (يونيو 2000). "نشأة كورديك" (ملف PDF) . مجلة معالجة إشارات VLSI . 25 (2 (عدد خاص عن كورديك)). هينغهام، ماساتشوستس، الولايات المتحدة الأمريكية: دار نشر كلوير الأكاديمية : 101-105. رمز Bibcode : 2000JSPSy..25..101V . doi : 10.1023/A:1008110704586 . ISSN 0922-5773 . S2CID 112881. مؤرشف من الأصل (ملف PDF) بتاريخ 4 مارس 2016. تم الاطلاع عليه بتاريخ 2 يناير 2016 .  
  12. ↑ بيرل، مايكل د. (يونيو 1971)، "تقنية CORDIC تقلل من البحث عن الدوال المثلثية"، تصميم الحاسوب ، بوسطن، ماساتشوستس ، الولايات المتحدة الأمريكية: شركة نشر تصميم الحاسوب: 72-78(ملاحظة: تشير بعض المصادر خطأً إلى هذا على أنه من تأليف بي زد بيرل أو في تصميم المكونات .)
  13. 1 2 3 4 5 شميد، هيرمان (1983) [1974]. الحساب العشري (الطبعة الأولى (إعادة طبع) ). مالابار، فلوريدا، الولايات المتحدة الأمريكية: شركة روبرت إي. كريجر للنشر. الصفحات 162، 165-176 ، 181-193 . ISBN   0-89874-318-4تم الاطلاع عليه بتاريخ 2016-01-03 .(ملاحظة: احتوت بعض دفعات هذه الطبعة المعاد طباعتها على الأقل على أخطاء مطبعية مع صفحات معيبة من 115 إلى 146. )
  14. ↑ داجيت، دان هـ. (سبتمبر 1959). "التحويلات من النظام العشري إلى النظام الثنائي في CORDIC" . معاملات معهد مهندسي الراديو (IRE) في الحواسيب الإلكترونية . 8 (3). معهد مهندسي الراديو (IRE): 335-339 . رمز Bibcode : 1959IRTEC...8..335D . doi : 10.1109/TEC.1959.5222694 . ISSN 0367-9950 . EC-8(3):335–339 . تاريخ الاسترجاع: 2016-01-02 . 
  15. ↑ مجموعة الأنظمة المتقدمة (6 أغسطس 1962)، الوصف الفني لمعدات ربط تحديد المواقع (تقرير)، فورت وورث، تكساس، الولايات المتحدة الأمريكية: جنرال دايناميكس ، FZE-052
  16. 1 2 شميد، هيرمان (1974). الحساب العشري ( الطبعة الأولى). بينغهامتون، نيويورك، الولايات المتحدة الأمريكية: جون وايلي وأولاده، الصفحات 162 ، 165-176 ، 181-193 . ISBN   0-471-76180-Xتم الاطلاع عليه بتاريخ 3 يناير 2016. حتى الآن ، عُرف أن خوارزمية CORDIC تُطبّق فقط في النظام الثنائي. ولكن، كما سيتبين هنا، يمكن تعديل الخوارزمية بسهولة لتناسب النظام العشري.* […] *في غضون ذلك، عُلم أن شركة هيوليت-باكارد وغيرها من الشركات المصنعة للآلات الحاسبة تستخدم تقنيات CORDIC العشرية في آلاتها الحاسبة العلمية.
  17. 1 2 3 4 ليبسون، ستيفن (2010). "مشروع HP 9100: تفاعل طارد للحرارة" . تم الاسترجاع في 2016-01-02 .
  18. 1 2 3 ميجيت، جون إي. (29 أغسطس 1961). "عمليات القسمة الزائفة والضرب الزائف" (ملف PDF) . مجلة IBM للبحوث والتطوير . 6 (2). ريفرتون، نيو جيرسي، الولايات المتحدة الأمريكية: شركة IBM (نُشر في أبريل 1962): 210-226 ، 287. doi : 10.1147/rd.62.0210 . مؤرشف من الأصل (ملف PDF) في 4 فبراير 2022. تم الاسترجاع في 9 يناير 2016. جون إي. ميجيت، بكالوريوس، 1953؛ دكتوراه، 1958، جامعة كامبريدج . حصل على جائزة سميث الأولى في كامبريدج عام 1955 وانتُخب زميلًا باحثًا في كلية إيمانويل . […] انضم إلى مختبر IBM البريطاني في هورسلي، وينشستر في عام 1958. وتشمل اهتماماته رموز تصحيح الأخطاء وأجهزة الكمبيوتر الصغيرة المبرمجة بدقة.(،)
  19. ١ ٢ ٣ كوكران، ديفيد س. (١٩ نوفمبر ٢٠١٠). "ربع قرن في إتش بي" (نص مقابلة). متحف تاريخ الحاسوب / ذكريات إتش بي. ٧: الآلات الحاسبة العلمية، حوالي عام ١٩٦٦. CHM X5992.2011 . تاريخ الاسترجاع: ٢ يناير ٢٠١٦. حتى أنني سافرت إلى جنوب كاليفورنيا للتحدث مع جاك فولدر، الذي قام بتطبيق الدوال المتسامية في آلة أثينا، وتحدثت معه لمدة ساعة تقريبًا. أحالني إلى الأوراق الأصلية لميجيت، حيث حصل على الدوال المعممة للقسمة الزائفة والضرب الزائف. [...] أجريتُ بحثًا أدبيًا مكثفًا أدى إلى بعض الاكتشافات المثيرة للاهتمام. عثرتُ على رسالة من عام ١٦٢٤ لهنري بريغز تناقش حساب اللوغاريتمات العشرية، ومن المثير للاهتمام أنها استخدمت نفس طريقة القسمة/الضرب الزائفة التي استخدمها ماكميلان وفولدر في برنامج أثينا . كنا قد اشترينا جهاز LOCI-2 من شركة وانغ لابز، ولاحظنا أن جهاز وانغ لابز LOCI II يستخدم نفس الخوارزمية لحساب الجذر التربيعي، بالإضافة إلى اللوغاريتمات والدوال الأسية. بعد طرح جهاز 9100، تلقى قسمنا القانوني رسالة من وانغ تفيد بأننا انتهكنا براءة اختراعهم. فأرسلتُ ردًا يتضمن مرجع بريغز باللاتينية، وجاء فيه: "يبدو لي أنه من التقنيات السابقة ". ولم نتلقَّ أي رد بعد ذلك. ()
  20. 1 2 كوكران، ديفيد س. (14-03-1966)، حول استخدام CORDIC لحساب الدوال المتسامية في BCD (اتصال خاص مع جاك إي. فولدر)
  21. 1 2 أوزبورن، توماس إي. (2010) [1994]. "قصة توم أوزبورن بكلماته الخاصة" . تم الاسترجاع في 1 يناير 2016 .
  22. ↑ ليبسون، ستيفن (2010). "جهاز HP 9100: الرحلة الأولى" . تم الاسترجاع في 2016-01-02 .
  23. ↑ كوكران، ديفيد س. (سبتمبر 1968). "البرمجة الداخلية لآلة حاسبة 9100A" . مجلة هيوليت-باكارد . بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية: هيوليت-باكارد : 14-16 . تاريخ الاسترجاع : 2016-01-02 .()
  24. ↑ عزز قدراتك الحاسوبية الشخصية باستخدام جهاز الحوسبة اللوغاريتمية الجديد LOCI-1 ، مختبرات وانغ ، 1964، الصفحات 2-3 ، تاريخ الاطلاع 2016-01-03 
  25. ↑ بنسين، ريك (31 أغسطس 2013) [1997]. "وانغ لوكي-2" . متحف الآلات الحاسبة القديمة على الإنترنت . بيفركريك، أوريغون سيتي، أوريغون، الولايات المتحدة الأمريكية . تم الاطلاع عليه بتاريخ 3 يناير 2016 .
  26. ↑ "دليل خدمة جهاز وانغ لوكي" (ملف PDF) . مختبرات وانغ، 1967. L55-67 . تم الاطلاع عليه بتاريخ 14-09-2018 .
  27. ↑ بنسين، ريك (23-10-2004) [1997]. "نظام آلة حاسبة وانغ موديل 360SE" . متحف آلات الحاسبة القديمة على الإنترنت . بيفركريك، أوريغون سيتي، أوريغون، الولايات المتحدة الأمريكية . تم الاطلاع عليه بتاريخ 3-1-2016 .
  28. 1 2 3 4 كوكران، ديفيد س. (يونيو 2010). "تصميم HP-35، دراسة حالة في الابتكار" . مشروع ذاكرة HP . تم الاسترجاع في 2 يناير 2016. خلال تطوير آلة حاسبة HP 9100 المكتبية ، كنت مسؤولاً عن تطوير الخوارزميات لتتناسب مع البنية التي اقترحها توم أوزبورن. على الرغم من أن المنهجية المقترحة للخوارزميات جاءت من مالكولم ماكميلان، فقد قرأتُ الكثير لفهم الحسابات الأساسية [...] على الرغم من أن مختبرات وانغ استخدمت طرق حساب مماثلة، إلا أن دراستي وجدت أعمالًا سابقة تعود إلى عام 1624 مذكورة في براءات اختراعهم. [...] مكّن هذا البحث من تكييف الدوال المتسامية من خلال استخدام الخوارزميات لتلبية احتياجات العميل ضمن قيود الأجهزة. وقد أثبت هذا أنه لا يُقدّر بثمن خلال تطوير HP-35 ، [...] تم النظر في متسلسلات القوى ، وتوسعات كثيرات الحدود ، والكسور المستمرة ، وكثيرات حدود تشيبيشيف للدوال المتسامية. كانت جميعها بطيئة للغاية بسبب كثرة عمليات الضرب والقسمة المطلوبة. وكانت الخوارزمية العامة الأنسب لمتطلبات السرعة وكفاءة البرمجة في آلة HP-35 هي طريقة القسمة والضرب الزائفة التكرارية، والتي وصفها هنري بريغز لأول مرة عام 1624 في كتابه " الحساب اللوغاريتمي "، ثم وصفها فولدر وميجيت لاحقًا. وهذا هو نفس نوع الخوارزمية المستخدمة في آلات HP الحاسبة المكتبية السابقة. [...] جعل تعقيد الخوارزميات البرمجة متعددة المستويات ضرورة حتمية. وهذا يعني أن الآلة الحاسبة يجب أن تتمتع بإمكانية استخدام البرامج الفرعية. [...] يتطلب توليد دالة متسامية مثل دالة الظل الزائدي العكسي عدة مستويات من البرامج الفرعية. [...] وثّق كريس كلير هذا لاحقًا كمنهجية آلة الحالة الخوارزمية (ASM). حتى دالة الجيب أو جيب التمام البسيطة تستخدم روتين الظل، ثم تحسب الجيب من المتطابقات المثلثية. كانت هذه العمليات المعقدة ضرورية لتقليل عدد البرامج الفريدة وخطوات البرنامج [...] صُممت مجموعة تعليمات الحساب خصيصًا لآلة حاسبة عشرية للدوال المتسامية. تُنفذ العمليات الحسابية الأساسية بواسطة جامع -طرح بنظام المتمم العشري ، والذي يحتوي على مسارات بيانات إلى ثلاثة من السجلات المستخدمة كذاكرة مؤقتة.
  29. ↑ براءة اختراع أمريكية رقم 3402285A ، وانغ، آن ، "جهاز حسابي"، نُشرت في 17-09-1968، صدرت في 17-09-1968، مُسجلة باسم مختبرات وانغ  (،)
  30. ^ براءة الاختراع رقم 1499281B1 ، وانغ، آن ، "Rechenmaschine fuer logarithmische Rechnungen"، نُشرت بتاريخ 06-05-1970، وصدرت بتاريخ 06-05-1970، وتم تخصيصها لمختبرات وانغ ( )
  31. ↑ شوارتزلاندر الابن، إيرل إي. (1990). الحساب الحاسوبي . المجلد 1 ( الطبعة الثانية). لوس ألاميتوس: مطبعة جمعية مهندسي الكهرباء والإلكترونيات . ISBN   9780818689314. 0818689315 . تم الاسترجاع بتاريخ 2016-01-02 .
  32. ↑ بيتروتشيلي، أورلاندو ر.، محرر (1972)، أفضل أوراق الحاسوب لعام 1971 ، دار نشر أورباخ ، ص 71، رقم ISBN  0877691274تم الاطلاع عليه بتاريخ 2016-01-02
  33. ↑ كوكران، ديفيد س. (يونيو 1972). "الخوارزميات والدقة في HP-35" (ملف PDF) . مجلة هيوليت-باكارد . 23 (10): 10-11 . مؤرشف من الأصل (ملف PDF) بتاريخ 4 أكتوبر 2013. تم الاطلاع عليه بتاريخ 2 يناير 2016 .
  34. ↑ لابورت، جاك (2005-12-06). "خوارزمية HP35 المثلثية" . باريس، فرنسا. مؤرشف من الأصل في 2015-03-09 . تم الاطلاع عليه في 2016-01-02 .أُرشف بتاريخ 10 أغسطس 2020 في أرشيف الإنترنت (Wayback Machine) .
  35. ↑ لابورت، جاك (فبراير 2005) [1981]. "سر الخوارزميات" . L'Ordinateur Individuel (24). باريس، فرنسا. مؤرشف من الأصل في 18 أغسطس 2016. تم الاطلاع عليه في 2 يناير 2016 .أُرشف بتاريخ 12 يونيو 2021 في أرشيف الإنترنت (Wayback Machine) .
  36. ↑ لابورت، جاك (فبراير 2012) [2006]. "طرق الأرقام" . باريس، فرنسا. مؤرشف من الأصل في 18 أغسطس 2016. تم الاطلاع عليه في 2 يناير 2016 .أُرشف بتاريخ 12 يونيو 2021 في أرشيف الإنترنت (Wayback Machine) .
  37. ↑ لابورت، جاك (فبراير 2012) [2007]. "خوارزمية لوغاريتم HP 35" . باريس، فرنسا. مؤرشف من الأصل في 18 أغسطس 2016. تم الاطلاع عليه في 7 يناير 2016 .أُرشف بتاريخ 10 أغسطس 2020 في أرشيف الإنترنت (Wayback Machine) .
  38. ↑ وانغ، يوكسوان؛ لو، يوانيونغ؛ وانغ، تشونغفنغ؛ شين، تشينغهونغ؛ بان، هونغبينغ (يناير 2020). "معمارية قائمة على خوارزمية GH CORDIC لحساب الجذر النوني لعدد ذي دقة مفردة". معاملات IEEE لأنظمة التكامل واسع النطاق جدًا (VLSI) . 28 (4): 864-875 . doi : 10.1109/TVLSI.2019.2959847 . S2CID 212975618 . 
  39. ↑ موبوري، سوريش؛ أشاريا، أميت (سبتمبر 2019). "منهجية تصميم معمارية VLSI عامة منخفضة التعقيد لحسابات الجذر النوني والقوة النونية". معاملات IEEE في الدوائر والأنظمة I: أوراق بحثية عادية . 66 (12): 4673-4686 . doi : 10.1109/TCSI.2019.2939720 . S2CID 203992880 . 
  40. ↑ فاشاني، لينا (نوفمبر 2019). "CORDIC كنظام غير خطي مُبدَّل". الدوائر والأنظمة ومعالجة الإشارات . 39 (6): 3234-3249 . doi : 10.1007/s00034-019-01295-8 . S2CID 209904108 . 
  41. ↑ شميد، هيرمان ؛ بوغاكي، أنتوني (20 فبراير 1973). "استخدام طريقة CORDIC العشرية لتوليد العديد من الدوال المتسامية". EDN : 64-73 .
  42. ↑ فرانك، ريتشارد (8 مايو 1973). تحليل خوارزميات التقييم المادي للوظائف الأساسية (ملف PDF) . مونتيري، كاليفورنيا، الولايات المتحدة الأمريكية: وزارة البحرية ، كلية الدراسات العليا البحرية . NPS-53FE73051A . تاريخ الاسترجاع: 3 يناير 2016 .
  43. 1 2 3 4 5 مولر، جان ميشيل (2006). الدوال الأولية: الخوارزميات والتنفيذ ( الطبعة الثانية). بوسطن: بيركهاوزر . ص 134. ISBN   978-0-8176-4372-0LCCN 2005048094. تم الاطلاع عليه بتاريخ 2015-12-01 . 
  44. 1 2 نافي، رافي (مارس 1983). "تنفيذ الدوال المتسامية على معالج رقمي". المعالجة الدقيقة والبرمجة الدقيقة . 11 ( 3-4 ): 221-225 . doi : 10.1016/0165-6074(83)90151-5 .
  45. ↑ بالمر، جون ف.؛ مورس، ستيفن بول (1984). دليل 8087 ( الطبعة الأولى). جون وايلي وأولاده أستراليا المحدودة . ISBN  04718756949780471875697. تم الاطلاع عليه بتاريخ 2016-01-02 .
  46. ↑ جلاس، إل. برنت (يناير 1990). "معالجات الرياضيات المساعدة: نظرة على ما تفعله وكيف تفعله". بايت . 15 (1): 337-348 . ISSN 0360-5280 . 
  47. 1 2 3 جارفيس، بيتس (1990-10-01). "تطبيق خوارزميات CORDIC - روتين واحد مضغوط لحساب الدوال المتسامية" . مجلة دكتور دوبز : 152-156 . مؤرشف من الأصل في 2016-03-04 . تم الاسترجاع في 2016-01-02 .
  48. 1 2 يوين، أ.ك. (1988). "معالجات النقطة العائمة من إنتل". سجل مؤتمر إلكترو/88 : 48/5/1–7.
  49. ↑ ميهر، برامود كومار؛ فالس، خافيير؛ جوانغ، تسو-بينغ؛ سريدهاران، ك.؛ ماهاراتنا، كوشيك (22 أغسطس/آب 2008). "خمسون عامًا من كورديك: الخوارزميات، والبنى، والتطبيقات" (ملف PDF) . معاملات IEEE في الدوائر والأنظمة I: أوراق بحثية عادية . 56 (9) (نُشر في 9 سبتمبر/أيلول 2009): 1893-1907 . doi : 10.1109/TCSI.2009.2025803 . S2CID 5465045 . 
  50. ↑ ميهر، برامود كومار؛ بارك، سانغ يون (فبراير 2013). "منهجية تصميم معمارية VLSI عامة منخفضة التعقيد لحسابات الجذر النوني والقوة النونية". معاملات IEEE لأنظمة التكامل واسع النطاق جدًا (VLSI) . 21 (2): 217-228 . doi : 10.1109/TVLSI.2012.2187080 . S2CID 7059383 . 
  51. ↑ هيفرون، دبليو جي؛ لابيانا، إف. (11-12-1970). "مذكرة فنية 70-2014-8: نظام الملاحة لمركبة التجوال القمرية" (ملف PDF) . ناسا . واشنطن العاصمة، الولايات المتحدة الأمريكية: بيلكوم . ص 14. 
  52. ↑ سميث، إرنست سي؛ ماستين، ويليام سي (نوفمبر 1973). "المذكرة الفنية D-7469: مراجعة أداء نظام الملاحة لمركبة التجوال القمرية" (ملف PDF) . ناسا . هانتسفيل، ألاباما، الولايات المتحدة الأمريكية: مركز مارشال لرحلات الفضاء . ص 17. 
  53. ↑ شريف، كين (مايو 2020). "استخراج ثوابت ذاكرة القراءة فقط من شريحة المعالج المساعد الرياضي 8087" . righto.com . تاريخ الاسترجاع: 3 سبتمبر 2020. تحتوي ذاكرة القراءة فقط على 16 قيمة لدالة الظل العكسي، وهي قيم الظل العكسي للعدد 2 - ن . كما تحتوي على 14 قيمة للوغاريتم، وهي اللوغاريتمات الثنائية للعدد (1 + 2 - ن ). قد تبدو هذه القيم غير مألوفة، لكنها تُستخدم في خوارزمية فعّالة تُسمى CORDIC، والتي تم اختراعها عام 1958.
  54. ↑ "البدء باستخدام مُسرِّع CORDIC باستخدام حزمة وحدة التحكم الدقيقة STM32CubeG4" (ملف PDF) . شركة STMicroelectronics . تاريخ الاسترجاع: 1 يناير 2021 .
  55. ↑ "CMSIS/CMSIS/DSP_Lib/Source/ControllerFunctions/arm_sin_cos_f32.c" . جيت هاب . ARM . تم الاسترجاع في 1 يناير 2021 .
  56. ↑ "حدود الخطأ في متسلسلة تايلور للدالة الجيبية" . موقع Math Stack Exchange . تم الاطلاع عليه بتاريخ 1 يناير 2021 .
  57. ↑ أندراكا، راي (1998). "دراسة استقصائية لخوارزميات CORDIC لأجهزة الكمبيوتر القائمة على مصفوفات البوابات المنطقية القابلة للبرمجة الميدانية". وقائع الندوة الدولية السادسة لعام 1998 التي نظمتها جمعية ACM/SIGDA حول مصفوفات البوابات المنطقية القابلة للبرمجة الميدانية - FPGA '98 . الصفحات 191-200 . doi : 10.1145/275107.275139 . ISBN  0-89791-978-5.
  58. ↑ "رياضيات الفئات" . معيار منصة جافا ( الطبعة الثامنة). شركة أوراكل . 2018 [1993]. مؤرشف من الأصل في 2018-08-06 . تم الاسترجاع في 2018-08-06 . 
  59. ↑ "ldexp, ldexpf, ldexpl" . cppreference.com . 11-06-2015. مؤرشف من الأصل في 06-08-2018 . تم الاطلاع عليه في 06-08-2018 .
  60. ↑ "القسم 8.3.9 اللوغاريتمي، والأسّي، والمقياس". دليل مطوري برامج معمارية Intel 64 و IA-32، المجلد 1: المعمارية الأساسية (ملف PDF) . شركة Intel . سبتمبر 2016. الصفحات 8-22 . 
  61. ↑ بايكوف، فلاديمير. "مخطط (أطروحة ذاتية) أطروحتي للدكتوراه، نُشر عام 1972" . baykov.de . تاريخ الاسترجاع: 3 مايو 2023 .
  62. ↑ بايكوف، فلاديمير. "التنفيذ المادي للوظائف الأساسية في أجهزة الكمبيوتر" . baykov.de . تم الاطلاع عليه بتاريخ 2023-05-03 .
  63. 1 2 بايكوف، فلاديمير. "معالجات ذات أغراض خاصة: خوارزميات وهياكل تكرارية" . baykov.de . تم الاطلاع عليه بتاريخ 2023-05-03 .

للمزيد من القراءة

  • باريني، جوزيف أ. (5 سبتمبر 1966). "نظام DIVIC يُجيب على أسئلة الملاحة المعقدة". الإلكترونيات : 105-111 . الرقم الدولي الموحد للدوريات 0013-5070 . (ملاحظة: DIVIC تعني "حاسوب الزيادات المتغيرة الرقمية" . تشير بعض المصادر خطأً إلى أن هذا من تصميم جيه إم باريني .)
  • أندرسون، ستانلي ف.؛ إيرل، جون ج.؛ غولدشميت، روبرت إليوت؛ باورز، دون م. (1 نوفمبر 1965). "وحدة تنفيذ العمليات الحسابية ذات الفاصلة العائمة في نظام IBM System/360 موديل 91" (ملف PDF) . مجلة IBM للبحوث والتطوير . 11 (1). ريفرتون، نيو جيرسي، الولايات المتحدة الأمريكية (نُشرت في يناير 1967): 34-53 . doi : 10.1147/rd.111.0034 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 5 مارس 2016. تاريخ الاسترجاع: 2 يناير 2016 .
  • ليكاردو، مايكل أ. (سبتمبر 1968). معالج الربط البيني مع التركيز على تشغيل وضع CORDIC (رسالة ماجستير). بيركلي، كاليفورنيا، الولايات المتحدة الأمريكية: جامعة كاليفورنيا، بيركلي ، قسم الهندسة الكهربائية. OCLC 500565168 . 
  • براءة الاختراع الأمريكية رقم 3576983A ، كوكران، ديفيد س.، "نظام آلة حاسبة رقمية لحساب الجذور التربيعية"، نُشرت في 4 مايو 1971، وصدرت في 4 مايو 1971، وتم تخصيصها لشركة هيوليت-باكارد  .)
  • تشين، تيان تشي (يوليو 1972). "الحساب الآلي للأسس واللوغاريتمات والنسب والجذور التربيعية" (ملف PDF) . مجلة IBM للبحوث والتطوير . 16 (4): 380-388 . doi : 10.1147/rd.164.0380 . ISSN 0018-8646 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 12 أغسطس 2016. تاريخ الاسترجاع : 2 يناير 2016 . 
  • إيغبرت، ويليام إي. (مايو 1977). "خوارزميات الآلة الحاسبة الشخصية 1: الجذور التربيعية" (ملف PDF) . مجلة هيوليت-باكارد . 28 (9). بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية: هيوليت-باكارد : 22-24 . مؤرشف من الأصل (ملف PDF) بتاريخ 18 ديسمبر 2015. تم الاطلاع عليه بتاريخ 2 يناير 2016 .()
  • إيغبرت، ويليام إي. (يونيو 1977). "خوارزميات الآلة الحاسبة الشخصية II: الدوال المثلثية" (ملف PDF) . مجلة هيوليت-باكارد . 28 (10). بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية: هيوليت-باكارد : 17-20 . مؤرشف من الأصل (ملف PDF) بتاريخ 4 مارس 2016. تم الاطلاع عليه بتاريخ 2 يناير 2016 .()
  • إيغبرت، ويليام إي. (نوفمبر 1977). "خوارزميات الآلة الحاسبة الشخصية III: الدوال المثلثية العكسية" (ملف PDF) . مجلة هيوليت-باكارد . 29 (3). بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية: هيوليت-باكارد : 22-23 . مؤرشف من الأصل (ملف PDF) بتاريخ 4 مارس 2016. تم الاطلاع عليه بتاريخ 2 يناير 2016 .()
  • إيغبرت، ويليام إي. (أبريل 1978). "خوارزميات الآلة الحاسبة الشخصية 4: الدوال اللوغاريتمية" (ملف PDF) . مجلة هيوليت-باكارد . 29 (8). بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية: هيوليت-باكارد : 29-32 . مؤرشف من الأصل (ملف PDF) بتاريخ 4 مارس 2016. تم الاطلاع عليه بتاريخ 2 يناير 2016 .()
  • سينزيغ، دون (1975). "خوارزميات الآلة الحاسبة". ملخص قراء مؤتمر IEEE Compcon . IEEE : 139-141 . رقم كتالوج IEEE: 75 CH 0920-9C.
  • بايكوف، فلاديمير د. (1972)،أسئلة مطروحة حول إعادة صياغة الوظيفة الأساسية لطريقة "التشفير بالشفرة"[ مشكلات تقييم الدوال الأولية باستخدام تقنية CORDIC رقمًا برقم ] (أطروحة دكتوراه) (باللغة الروسية)، جامعة لينينغراد الحكومية للهندسة الكهربائية
  • بايكوف، فلاديمير د.؛ سمولوف، فلاديمير ب. (1975). Apparaturnaja realizatsija elementarnikh funktsij v CVMأداة تحقيق الوظيفة الأساسية في CVM[ التنفيذ المادي للوظائف الأساسية في الحواسيب ] (باللغة الروسية). جامعة لينينغراد الحكومية. مؤرشف من الأصل بتاريخ 2019-03-02 . تم الاطلاع عليه بتاريخ 2019-03-02 .
  • بايكوف، فلاديمير د.؛ سيلجوتين، SA (1982). أحدث العناصر الوظيفية في EKBM[ تقييم الوظائف الأولية في الآلات الحاسبة الدقيقة ] (بالروسية). موسكو: راديو i svjaz (Радио и связь).
  • بايكوف، فلاديمير د.؛ سمولوف، فلاديمير ب. (1985).المعالجات المتخصصة: الخوارزميات والهياكل التكرارية[ معالجات ذات أغراض خاصة: الخوارزميات والهياكل التكرارية ] (بالروسية). موسكو: راديو i svjaz (Радио и связь).
  • كوبنز، توماس، محرر. (يناير 1980). "ثوابت CORDIC في ذاكرة القراءة فقط TI 58/59". نشرة تبادل برامج تكساس إنسترومنتس . 2 (2). كابيلين، بلجيكا: TISOFT.
  • كوبنز، توماس، محرر. (أبريل - يونيو 1980). "مخطط حساب اللوغاريتم الطبيعي / مخطط حساب e x / مخطط حساب 1/x". نشرة تبادل برامج تكساس إنسترومنتس . 2 (3). كابيلين، بلجيكا: تيسوفت.(حول CORDIC في TI-58 / TI-59 )
  • فريق منتجات الرسومات في شركة تكساس إنسترومنتس (1995) [1993]. "خوارزميات الدوال المتسامية" . دالاس، تكساس، الولايات المتحدة الأمريكية: تكساس إنسترومنتس ، قسم المنتجات الاستهلاكية. مؤرشف من الأصل بتاريخ 17 مارس 2016. تم الاطلاع عليه بتاريخ 2 مارس 2019 .
  • يورك، غونتر؛ لامب، برنهارد. نوربرت وينجل (1989). Arithmetische Algorithmen der Mikrorechentechnik (بالألمانية) (1  ed.). برلين، ألمانيا: VEB Verlag Technik . ص  219، 261، 271– 296. ISBN 3341005153EAN 9783341005156. MPN 5539165. رقم الترخيص 201.370/4/89 . تاريخ الاسترجاع 2015-12-01 . 
  • زيشميستر، م. (2021). "حل معادلة كبلر بتكرارات CORDIC المزدوجة" . الإشعارات الشهرية للجمعية الفلكية الملكية . 500 (1). غوتنغن، ألمانيا: معهد الفيزياء الفلكية، جامعة جورج أغسطس: 109–117 . أرخايف : 2008.02894 . دوى : 10.1093/mnras/staa2441 .
  • Frerking, Marvin E. (1994). معالجة الإشارات الرقمية في أنظمة الاتصالات (  الطبعة الأولى).
  • كانتابوترا، فيتيت (1996). "حول الأجهزة لحساب الدوال الأسية والمثلثية". معاملات IEEE في الحوسبة . 45 (3): 328-339 . Bibcode : 1996ITCmp..45..328K . doi : 10.1109/12.485571 .
  • يوهانسون، كيني (2008). "6.5 دوال الجيب وجيب التمام". حسابات منخفضة الطاقة ومنخفضة التعقيد تعتمد على الإزاحة والجمع (ملف PDF) (أطروحة دكتوراه). دراسات لينشوبينغ في العلوم والتكنولوجيا (  الطبعة الأولى). لينشوبينغ، السويد: قسم الهندسة الكهربائية، جامعة لينشوبينغ . الصفحات 244-250 . ISBN  978-91-7393-836-5ISSN 0345-7524 . العدد 1201. مؤرشف (PDF) من الأصل بتاريخ 13 أغسطس 2017. تم الاطلاع عليه بتاريخ 23 أغسطس 2021 . (x+268 صفحة)
  • بانيرجي، أيان (2001). "تنفيذ معالج FFT قائم على CORDIC باستخدام FPGA لمعالجة الإشارات الطبية الحيوية". المعالجات الدقيقة والأنظمة الدقيقة . 25 (3). خاراجبور، غرب البنغال، الهند: 131-142 . doi : 10.1016/S0141-9331(01)00106-5 .
  • كاهان، ويليام مورتون (20 مايو 2002). "خوارزميات القسمة الزائفة للوغاريتمات والأُسِّيات ذات الفاصلة العائمة" (ملف PDF) . بيركلي، كاليفورنيا، الولايات المتحدة الأمريكية: جامعة كاليفورنيا . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 25 ديسمبر 2015. تاريخ الاسترجاع: 15 يناير 2016 .
  • كوكروم، كريس ك. (خريف 2008). "تنفيذ خوارزمية CORDIC في محول رقمي تنازلي" (PDF) .
  • لاكشمي، بوبانا؛ دار، أنينديا سوندار (2009-10-06). "بنى CORDIC: دراسة استقصائية" . تصميم VLSI . 2010. خاراجبور، غرب البنغال، الهند: قسم هندسة الإلكترونيات والاتصالات الكهربائية، المعهد الهندي للتكنولوجيا (نُشر في 2010-10-10): 1-19 . doi : 10.1155/2010/794891.794891 .
  • سافارد، جون جي جي (2018) [2006]. "تقنيات حسابية متقدمة" . كوادريبلوك . مؤرشف من الأصل بتاريخ 3 يوليو 2018. تم الاطلاع عليه بتاريخ 16 يوليو 2018 .