שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2022 - הפרד ומשול

נתונים שני מספרים מרוכבים $x=a+bi$ ו-$y=c+di$ ($a,b,c,d$ ממשיים). חישוב ישיר של $x\cdot y=(ac-bd)+(ad+bc)i$ דורש 4 כפלים של מספרים ממשיים. הסבירו כיצד לחשב את $x\cdot y$ תוך ביצוע **3 כפלים בלבד** של מספרים ממשיים.

רמז: חשבו $(a+b)(c+d)$, $ac$ ו-$bd$. שלושת אלו מספיקים לשחזר את $ac-bd$ ואת $ad+bc$ באמצעות חיבורים וחיסורים בלבד.

פתרון: נבצע שלושה כפלים בלבד (טריק גאוס): 1. $P_1=(a+b)\cdot(c+d)$ 2. $P_2=a\cdot c$ 3. $P_3=b\cdot d$ אזי: - **החלק הממשי:** $ac-bd=P_2-P_3$. - **החלק המדומה:** $ad+bc=P_1-P_2-P_3$ (שכן $P_1=ac+ad+bc+bd$, ובחיסור $P_2$ ו-$P_3$ נותר $ad+bc$). חיבור וחיסור הם פעולות ליניאריות שאינן נספרות ככפלים, ולכן סה"כ **3 כפלים** של מספרים ממשיים. $\blacksquare$