העלאה יעילה של ביטוי בריבוע

[nullity]

העלאה יעילה של ביטוי בריבוע

נאמר ויש לי שני קלאסים -

class 1var { int id; double m; } class 2var { int id1, id2; double m; }​

כאשר 1var מייצג משתנה אחד ו- 2var מייצג מכפלה של שני משתנים. id הוא מס' המשתנה/ים ו-m הוא מס' המכפיל. אני מייצג ביטוי לינארי כוקטור של 1var וביטוי ריבועי כוקטור של 2var. בהינתן ביטוי לינארי אני רוצה להחזיר ביטוי ריבועי שמהווה את הריבוע שלו. האם קיימת דרך יעילה יותר לבצע זאת מאשר הפיתרון הנאיבי (שתי לולאות מקוננות באורך n כל אחת)?

 

[vinney]

קצת הסתבכתי

תוכל לתת דוגמא לחישוב שלך? לא הבנתי את ההסבר שלך לגבי מה המחלקות האלה מייצגות, ומה בדיוק החישוב שאתה עושה...

 

[nullity]

כן, הנה

נגיד אני רוצה לייצג את הביטוי 4x + 6y + 2z. אני מחליט שהמס' של המשתנה x הוא 1, של y הוא 2 ושל z הוא 3. לכן הביטוי הנ"ל יראה כך (וקטור של 1var) -

(<1,4>, <2, 6>, <3, 2>)​

עכשיו אני רוצה להעלות את הביטוי בריבוע, כלומר לקבל 16xx+24xy+8xz+24xy+36yy+12yz+8xz+12zy+4zz הביטוי כמו שהוא מיוצג ע"י וקטור של 2var -

(<1,1,16>, <1,2,24>, <1,3,8>, <2,1,24>, <2,2,36>, <2,3,12>, <3,1,8>, <3,2,12>, <3,3,4>)​

 

[vinney]

מכפלת פולינומים

אפשר לעשות את זה בNLOG N. חפש בקורמן, יש שם את זה בפרק 32. או חפש על התמרות פורייה (FFT), אם אין לך את קורמן.

 

[ה עוד אחד]

טעות.

האלגוריתמם הטוב ביותר הידוע עד היום הוא של Schönhage/Strassen בסיבוכית של (O(n*logn*logn*logn

 

[vinney]

טוב עיגלתי קצת ../images/Emo13.gif אתה צודק, כמובן