התפוח הנופל חלוקה

[פול קרטיס] לעבר Segger יש סדרה מעניינת של פוסטים על חישוב חלוקת. זה היה אמור להיות נושא חם, אך כיום רבים מחשבים או שפות מחשב יש תמיכה כפל וחילוק מובנה. מעבדים אבל כמה חסרים את ההוראות וספרייה לעשות זה עשוי להיות פחות אידיאלי. לדעת איך לגלגל משלך עשוי לאפשר לך לבצע אופטימיזציה עבור מהירות או בחלל. מכסה בתשלומים שוטפים באמצעות האלגוריתם של ניוטון לעשות חלוקה.

סטיב מרטין היה קצת מפורסם על איך להיות מליונר ולא משלמים מסים. הוא התחיל בזה שהוא אומר, “קודם … לקבל מיליון דולר. ואז …” שיטה זו היא קצת כמו שמאז צריך קודם כל לדעת כיצד להכפיל לפני שתוכל לחלק. ההנחה הבסיסית היא כפול: שיטת ניוטון מאפשרת לך לחדד אומדן של גומלין ידי כפל רצוף ולאחר מכן הכפלת מספר גומלין זהה חלוק. במילים אחרות, אם אנחנו צריכים לחלק 34 על ידי 6, אתה יכול לשכתב 34/6 ל 34 * 1/6 והתשובה היא אותה.

הקירוב של ניוטון עבור reciprocals מאפשר לך לקחת ניחוש התשובה ולאחר מכן לחדד אותה באמצעות סדרה של פעולות כפל. כפל כל יוצר דיוק טוב יותר. אתה יכול להשתמש בזה כדי לבצע תחלופה מהירה / מרחב קלסי. לדוגמה, בואו פשוט נניח שאנו רוצים למצוא את הגומלין של שני בתים (כנראה בייט נקודה קבועה). שולחן נראה- up של 256 אלמנטים יספק דיוק מושלם יהיה מהיר מאוד. אין יותר מתמטיקה היא הכרחית. אבל מה עם 32 סיביות? עכשיו השולחן הוא פשוט גדול מדי. אבל אתה יכול להסתכל למעלה, אומר, 8 הסיביות הראשונות של המספר 32 הסיבי. או יותר. או פחות. תלוי מה חשוב לך.

אז עכשיו יש לך הערכה לקויה של הגומלין שלך. סר אייזיק יכול לעשות את זה טוב יותר. במשך מספר כלשהו, אתה לקחת את הערכתך (x) ו להכפיל אותם יחד. פחת מספר כי מן 2 ויש לך גורם להתרבות האומדן הישן שלך על ידי כדי לקבל אומדן חדש. הדילוג קדימה, ברור אם הערכתך צדק, את הכפל ייתן לך 1 שלא ישתנה האומדן הישן בכלל. אם האומדן כבויה, ותקבל גורם קנה מידה.

כנוסחה זה נראה כך:

x = x * (2-A * x);
אז אם אתה מחליט הגומלין של 22 יכול להיות 0.02, לעבור את הראשון ייתן לך:

0.02 * (2-22 * 0.02) = 0.0312

.0312 * (2-22 * 0.0312) = 0.0410

.0410 * (2-22 * 0.0410) = 0.0450
התשובה הנכונה היא שבר מחזורי 0.0454545 ואם אתה ממשיך הלאה, תוכל להגיע לשם.

כמובן, אז אתה צריך להכפיל עוד פעם אחת לעשות את החלוקה.

אהבנו כי שהפוסט כולל יישום נקודה קבועה ולאחר מכן בוחן את קוד הרכבה וכתוצאה עבור ARM, RISC-V, ו dsPIC30. ובכן שווה לקרוא.

אנחנו אוהבים טריקים במתמטיקה נוכל להשתמש בשפת הרכבה. אם אתה עובד על הרסיבר ו נקודה צפה, אל תחמיצו בשיטה זו.