בתשובה לשועל, 27/01/04 20:51
 |
|
 |
||
|
||||
 |
מכיוון שאתה לומד מדעי המחשב, אציין ששימוש מאוד לא מקובל לקונבולוציות הוא להכפיל מספרים גדולים זה בזה. שים לב שכשאנחנו מכפילים בכפל "ארוך", אנחנו נוהגים להכפיל את מוכפל הראשון באחת מהספרות של המוכפל השני, ואז מוסיפים את התוצאות אחת לשניה ( בהזזה לפי מיכום הספרה הכופלת). זוהי בדיוק קונבולוציה. ולמה זה טוב? אם תרצה פעם להכפיל שני מספרים גדולים (נגיד למטרות הצפנה), ותדע שזה קונבולוציה, תוכל לייעל את התהליך באמצעות התמרות פורייה ( אבל זה כבר בשנה ב או ג). ותודה ל NUMERICAL RECIPES המופלא1, שהביאני עד הלום. לא שמן כמו מלחמה ושלום, אבל עם פחות מסות הסטוריות. |
 |
 |
 |
|
|
|
||
|
||||
|
לא מקובל? נהפוך הוא, מקובל מאוד עכש"י. ויש גם ב-Knuth מיודענו. | |
|
|
|
|
|
||
|
||||
|
אולי אצל מתמטיקאים. כשאני ראיתי זאת לראשונה (ולא כל כך מזמן), הרגשתי שהקשקשים נפלו מעיני. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שזה מאד מקובל, לפחות בקרב מתכנתים. לראשונה נתקלתי ברעיון ב-Introduction To Algorithms של Cormen, ספר מאד בסיסי (ושימושי), שכמדומני נלמד בשנה א' בפקולטה הרלוונטית. הפעם הראשונה בה נתקלתי בשימוש שלו הייתה בבניית תוכנית שמחשבת מספרי פיבונצ'י גדולים במהירות, ואחת הגרסאות הלא-סופיות שלה התבססו על נוסחת ביינה, והתמרת פורייה מהירה לביצוע המכפלות. היא נכשלה מכיוון שמהר-מהרצוי נדרש נפח זיכרון עצום, וה-CPU נאלץ להקדיש את רוב זמנו לניהול ה-Virtual memory במקום לחישובים (מחשבים זה רע). הגרסה המנצחת התבססה על העלה בחזקה של מטריצה. אגב, אולי יש למישהו רעיון מוצלח יותר? |
|
|
|
|
|
|
||
|
||||
|
יותר מוצלח למה- לכפל או לחישוב מספרי פיבונאצי? (לא שיש לי רעיון לזה או לזה). |
|
|
|
|
|
|
||
|
||||
|
אותו knuth מאלגוריתם KMP? (וכמדומני גם מ- LATEX) | |
|
|
|
|
|
||
|
||||
|
כן, ומעוד הרבה דברים אחרים. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |