ABA


"חידה קטנה, פענוח אלגוריתם"
גירסת הדפסה        
קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #6761 מנהל    סגן המנהל    מפקח   Winner    צל"ש   מומחה  
אשכול מספר 6761
dryice

   12:12   14.08.03   
אל הפורום  
  חידה קטנה, פענוח אלגוריתם  
 
   ערכתי לאחרונה בתאריך 15.08.03 בשעה 19:08 בברכה, dryice
 
נתונה פונקציה בC, מה היא עושה ואיך?

float foo( float number ) {
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
return y;
}

עבור אלו שלא בקיאים בC הסברים קטנים:
הפעולה << היא פעולת shift right והשורות עם* long ו* float
זה פשוט להפוך משתנה נקודה צפה למשתנה שלם עם אותו מבנה ביטים
ולהיפך. האות F אחרי מספר מציינת שהמספר הוא מסוג נקודה
צפה ב32 ביט.

רמז: 754 854

DRYICE


                                שתף        
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

  האשכול     מחבר     תאריך כתיבה     מספר  
  בשתי מילים - איזה פחד liranr 14.08.03 12:27 1
     רמזים עבים יותר: dryice 14.08.03 18:49 2
         מה עושה הפונקציה נראה לי שאני יודע liranr 14.08.03 20:02 3
             הדיוק לא משהוא, אפשר אם שינוי קל, לשפר אותו dryice 15.08.03 11:36 4
                 קראתי liranr 15.08.03 14:23 5
                     מה שאני הבנתי בינתיים: dryice 15.08.03 17:04 6
                         WOW liranr 15.08.03 17:35 7

       
liranr

   12:27   14.08.03   
אל הפורום  
  1. בשתי מילים - איזה פחד  
בתגובה להודעה מספר 0
 
   ברור לי שלב החידה אלה השורות
i = * ( long * ) &y;
y = * ( float * ) &i;

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
dryice

   18:49   14.08.03   
אל הפורום  
  2. רמזים עבים יותר:  
בתגובה להודעה מספר 1
 
   הפואנטה היא להבין את השורה
i = 0x5f3759df - ( i >> 1 );

כאשר מדובר במשתני נקודה צפה.
את החלק הראשון, מה עושה הפונקציהף אפשר להבין בקלות ע"י
black box testing.

DRYICE


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
liranr

   20:02   14.08.03   
אל הפורום  
  3. מה עושה הפונקציה נראה לי שאני יודע  
בתגובה להודעה מספר 2
 
   כמו שאמרת עם black box testing נראה לי שגיליתי מה היא מחזירה
(אם אני צודק אז הדיוק שלה לא משהו...)
לגבי השורה הזאת, אני מודה שאני טועה באפילה.
הפכתי את המספר 0x5f3759df לדצימלי, בינארי, אוקטלי, ובשום בסיס הוא
לא נראה הגיוני - אלא שרירותי לגמרי.
אני יעבוד על זה מחר אם החידה לא תפתר עד אז.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
dryice

   11:36   15.08.03   
אל הפורום  
  4. הדיוק לא משהוא, אפשר אם שינוי קל, לשפר אותו  
בתגובה להודעה מספר 3
 
   המספר מאוד מוזר, אבל יש לו חשיבות אדירה.
קראת כבר איך בנוי floating point?


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
liranr

   14:23   15.08.03   
אל הפורום  
  5. קראתי  
בתגובה להודעה מספר 4
 
   ביט ראשון לסימן, אחריו 8 לאקספוננט (עם תוספת קבועה של 127) ואחר
כך 23 לבסיס (כאשר אנחנו מניחים 1 מוביל ולא מציינים אותו)

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
dryice

   17:04   15.08.03   
אל הפורום  
  6. מה שאני הבנתי בינתיים:  
בתגובה להודעה מספר 5
 
   במספר הקסום, אם ניקח את האקספוננט המספר הוא 190,
עכשיו הshift הוא למעשה חלוקה ב2 של האקספוננט, ואז אנו מחשבים
190-E/2 אם נתייחס לכך ש הe האמיתי הוא E=e+127 אז נקבל
NewE=190-63-e/2=127-e/2
ואז Newe=-e/2
כלומר אם זה היה השינוי היחיד, היינו מקבלים קירוב טוב, לחישוב 1 חלקי שורש המספר,
פשוט על ידי שינוי ה exponent.

השינוי במנטיסה הוא יותר מסובך. הסיבית התחתונה של האקספוננט נכנסת למנטיסה,
החלק של המספר הקסום הוא 0.43 וקצת אז המנטיסה החדשה(במקרה וסיבית האקספוננט 0)
f2=1.43 - (f-1)/2
כאשר המספר המקורי היה: v=f*2^e
בהחלט יתכן שהחלק התחתון נבחר כך שהמנטיסה תתעוות כמה שפחות. עבור מנטיסה 1.3 השינוי
כמעט שלא קיים. ניתוח ממש של מה שקורה במנטיסה אין לי, אבל וודאי שהוא פחות חשוב
שכן אנחנו בשלב זה רק צריכים קירוב טוב, והמנטיסה וודאי יש לה ערך של בין 1 ל 2.


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

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

נקבל:


float M_sqrt( float number ) {
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; /* evil floating point bit level hacking*/
i = 0x5f3759df - ( i >> 1 ); // turn E to -E/2. and F to
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); /* 1st iteration*/
y = y * ( threehalfs - ( x2 * y * y ) ); /* 2nd iteration*/
y = y * ( threehalfs - ( x2 * y * y ) ); /* 3rd iteration*/
return 1/y;
}


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
liranr

   17:35   15.08.03   
אל הפורום  
  7. WOW  
בתגובה להודעה מספר 6
 
   טוב, לפחות צדקתי בזה שידעתי מה הקוד עושה, כי היה לוקח לי שנה
להבין איך הוא עושה את זה

עדיין אני צריך לעבור על כל החישובים, אבל בגדול הרעיון מובן.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

תגובה מהירה  למכתב מספר: 
 
___________________________________________________________________

___________________________________________________________________
למנהלים:  נעל | תייק בארכיון | מחק | העבר לפורום אחר | מחק תגובות | עגן אשכול
       



© כל הזכויות שמורות ל-רוטר.נט בע"מ rotter.net