أين يمكنني أن أجد خوارزميات ناعمة وقسمة؟
-
24-09-2019 - |
سؤال
أنا أعمل على السيطرة الصغيرة دون مضاعفة الأجهزة وتقسيمها. أحتاج إلى طهي خوارزميات البرامج لهذه العمليات الأساسية التي تعد توازنًا رائعًا بين الحجم والكفاءة المدمجة. سيستخدم منفذ برنامج التحويل البرمجي C هذه الجفاف ، وليس مطوري C أنفسهم.
إن Google-FU الخاص بي يظهر في الغالب ضوضاء في هذا الموضوع.
هل يمكن لأي شخص أن يوجهني إلى شيء مفيد؟ يمكنني استخدام التعليمات الإضافة/الفرعية وتحويل. قد تعمل الجهاز المستندة إلى الجدول أيضًا ، لكنني قلق بعض الشيء بشأن حشر الكثير في نهاية المترجم ... أم ، إذا جاز التعبير.
المحلول
إليك خوارزمية الضرب البسيطة:
ابدأ مع أقصى اليمين من المضاعف.
إذا كان الشيء في مضاعف 1 ، أضف multiplicand
تحول multiplicand بمقدار 1
انتقل إلى الشيء التالي في المضاعف والعودة إلى الخطوة 2.
وهنا خوارزمية تقسيم:
إذا كان المقسوم أكبر من الأرباح ، توقف.
في حين أن سجل المقساة أقل من سجل الأرباح ، فإن التحول يسار.
سجل القسمة سجل الحق في 1.
قم بطرح سجل المقسوم من سجل الأرباح وقم بتغيير البت إلى 1 في سجل النتيجة في البت الذي يتوافق مع إجمالي عدد التحولات التي تم إجراؤها على سجل المقسوم.
ابدأ من جديد في الخطوة 1 مع سجل المقسوم في الحالة الأصلية.
بالطبع ستحتاج إلى وضع شيك لتقسيمه على 0 ، ولكن يجب أن يعمل.
هذه الخوارزميات ، بالطبع ، هي فقط للأعداد الصحيحة.
نصائح أخرى
مرجعتي المفضلة لأشياء مثل هذه ، متوفرة في شكل الكتاب:
http://www.hackersdelight.org/
كما لا يمكنك أن تخطئ في TAOCP: http://www-cs-faculty.stanford.edu/~uno/taocp.html
هذه خوارزمية تقسيم: http://www.prasannatech.net/2009/01/division-without-division-operator_24.html
أفترض أننا نتحدث عن INTS؟
إذا لم يكن هناك دعم للأجهزة ، فسيتعين عليك تنفيذ استثناء الفجوة الخاصة بك.
(لم يكن لدي حظ كبير بسرعة في العثور على خوارزمية الضرب ، لكنني سأستمر في البحث إذا لم يجد شخص آخر حرفًا).
خوارزمية الضرب البسيطة والأداء إلى حد ما هي الأعداد الصحيحة هي الضرب الفلاح الروسي.
بالنسبة للعقلانية ، يمكنك تجربة ثنائي QUOTE تدوين, ، أي التقسيم أسهل من المعتاد.
اتضح أنه لا يزال لديّ رمز التجميع القديم 68000 للتكاثر الطويل والقسمة الطويلة. 68000 رمز نظيف وبسيط ، لذلك يجب أن يكون من السهل ترجمة الرقائق الخاصة بك.
كان 68000 قد تضاعف وتقسيم تعليمات IIRC - أعتقد أن هذه قد كتبت كتمرين تعليمي.
قررت فقط وضع الرمز هنا. تعليقات إضافية ، وفي هذه العملية ، إصلاح مشكلة.
;
; Purpose : division of longword by longword to give longword
; : all values signed.
; Requires : d0.L == Value to divide
; : d1.L == Value to divide by
; Changes : d0.L == Remainder
; : d2.L == Result
; : corrupts d1, d3, d4
;
section text
ldiv: move #0,d3 ; Convert d0 -ve to +ve - d3 records original sign
tst.l d0
bpl.s lib5a
neg.l d0
not d3
lib5a: tst.l d1 ; Convert d1 -ve to +ve - d3 records result sign
bpl.s lib5b
neg.l d1
not d3
lib5b: tst.l d1 ; Detect division by zero (not really handled well)
bne.s lib3a
rts
lib3a: moveq.l #0,d2 ; Init working result d2
moveq.l #1,d4 ; Init d4
lib3b: cmp.l d0,d1 ; while d0 < d1 {
bhi.s lib3c
asl.l #1,d1 ; double d1 and d4
asl.l #1,d4
bra.s lib3b ; }
lib3c: asr.l #1,d1 ; halve d1 and d4
asr.l #1,d4
bcs.s lib3d ; stop when d4 reaches zero
cmp.l d0,d1 ; do subtraction if appropriate
bhi.s lib3c
or.l d4,d2 ; update result
sub.l d1,d0
bne.s lib3c
lib3d: ; fix the result and remainder signs
; and.l #$7fffffff,d2 ; don't know why this is here
tst d3
beq.s lib3e
neg.l d2
neg.l d0
lib3e: rts
;
; Purpose : Multiply long by long to give long
; Requires : D0.L == Input 1
; : D1.L == Input 2
; Changes : D2.L == Result
; : D3.L is corrupted
;
lmul: move #0,d3 ; d0 -ve to +ve, original sign in d3
tst.l d0
bpl.s lib4c
neg.l d0
not d3
lib4c: tst.l d1 ; d1 -ve to +ve, result sign in d3
bpl.s lib4d
neg.l d1
not d3
lib4d: moveq.l #0,d2 ; init d2 as working result
lib4a: asr.l #1,d0 ; shift d0 right
bcs.s lib4b ; if a bit fell off, update result
asl.l #1,d1 ; either way, shift left d1
tst.l d0
bne.s lib4a ; if d0 non-zero, continue
tst.l d3 ; basically done - apply sign?
beq.s lib4e ; was broken! now fixed
neg.l d2
lib4e: rts
lib4b: add.l d1,d2 ; main loop body - update result
asl.l #1,d1
bra.s lib4a
بالمناسبة - لم أعرف أبدًا ما إذا كان من الضروري تحويل كل شيء إلى إيجابي في البداية. إذا كنت حريصًا على عمليات التحول ، فقد يكون ذلك ممكنًا.
للضرب ، أضف منتجات جزئية من مضاعف النقل إلى تراكم إذا تم تعيين بت المقابلة في المضاعف. Shift Multiplicand و Propister في نهاية الحلقة ، واختبار مضاعف و 1 لمعرفة ما إذا كان ينبغي القيام بالإضافة.
رقائق سلسلة MicroChip Picmicro 16FXXX لا تحتوي على تعليمات مضاعفة أو تقسيم. ربما يمكن نقل بعض روتينات الانقسام الناعمة الناعمة والخلفية إلى MCU.
الموافقة المسبقة عن علم متحكم أساليب الضرب الرياضيات
الموافقة المسبقة عن علم متحكم أساليب قسم الرياضيات
تحقق أيضا "طريقة نيوتن" للقسمة. أعتقد أن هذه الطريقة تعطي أصغر حجم قابل للتنفيذ من أي خوارزمية تقسيم رأيتها على الإطلاق ، على الرغم من أن التفسير يجعله يبدو أكثر تعقيدًا مما هو عليه حقًا. أسمع أن بعض أجهزة الكمبيوتر العملاقة المبكرة استخدموا طريقة نيوتن للتقسيم.