ضرب چندجمله‌ای

در این مسئله می‌خواهیم دو چندجمله‌ای از درجه‌های و که به فرم ضابطه‌ای با ضرایب هر توانی از x آن‌ها مشخص شده‌اند را در هم ضرب کنیم و ضابطه چندجمله‌ای حاصل را بدست آوریم. در ابتدا فرض می‌کنیم که برای نمایش چندجمله ای‌ها در فرم ضابطه‌ای یک آرایه به طول درجه چندجمله‌ای به علاوه یک می‌گیریم و در خانه i ام ضریب را ذحیره می‌کنیم. نمایش متداول دیگر این است که تنها ضرایب ناصفر را در یک لیست پیوندی نگهداری کنیم.
الگوریتم بدیهی ضرب چندجمله‌ای
اگر دو چندجمله‌ای داشته باشیم که هر کدام با ضرایب توان‌های متغیرشان نمایش داده شوند، الگوریتم بسیار ساده‌ای برای محاسبه حاصا ضرب آن‌ها در زمان وجود دارد ( و درجه‌های چندجمله ایها هستند). در حقیقت این الگوریتم، همان روشی است که در محاسبات روزانه به کار می‌بریم و شبه کد آن در زیر آمده‌است. همان طور که گفته شد برای سادگی فرض می‌کنیم که هر ضرایب هر چندجمله‌ای از درجه در آرایه‌ای به طول به روش
ذخیره شود.
Multiply(P, n, Q, m)
define R as a polynomial with degree n+m
for (i=0 to n) do
for (j=0 to m) do
Ri+j += Pi*Qj
return R
الگوریتم استراسن ( الگوریتم کاراتسوبا) برای ضرب چندجمله ای‌ها
با این الگوریتم می‌توان حاصل ضرب دو چندجمله‌ای را با سرعت بیشتری نسبت به الگوریتم بدیهی ضرب یافت. ایده اصلی این الگوریتم این است که از آن جایی که عمل جمع در رایانه‌ها بسیار سریع‌تر از عمل ضرب انجام پذیر است، می‌توان در الگوریتم بدیهی ضرب که همان طور که قبلا بررسی شد در آن به تعداد عمل ضرب نیاز است، تعداد اعمال ضرب را کم‌تر کرد و به ازای آن کمی به تعداد اعمال جمع افزود که روند دقیق کار در ادامه توضیح داده خواهد شد. به این ترتیب می‌توان زمان اجرای کلی ضرب دو چندجمله‌ای را بهبود بخشید.
برای سادگی فرض کنید می‌خواهیم دو چندجمله‌ای از درجه را در هم ضرب کنیم. می‌نویسیم:
یعنی هر چندجمله‌ای را دو بخش کردیم. واضح است که برای ضرب داریم:
ایده اصلی این است که اگر تعریف کنیم:
با جایگذاری در معادله اولیه ضرب خواهیم داشت:
پس همان طور که نشان داده شد، می‌توان با سه عمل ضرب (برای محاسبه A و B و C) با اندازه نصف و سپس محاسبه رابطه بالا جواب مسئله را پیدا کرد.
تحلیل زمانی: در این الگوریتم در اصل به جای هر چهار عمل ضرب در الگوریتم بدیهی ضرب، تنها سه تا ضرب انجام می‌شود. چنین استفاده هوشمندانه‌ای از تکراری بودن بخشی از محاسبات بسیار شبیه الگوریتم استراسن برای ضرب ماتریس هاست. اثبات می‌شود که این الگوریتم از(nlg3) است. زیرا اگر زمان اجرای الگوریتم با اندازه ورودی n را T(n) بنامیم، می‌توان به رابطه بازگشتی زیر رسید:
که با یکی از روش‌های حل معادله بازگشتی مانند قضیه اساسی می‌توان دید که:
نکات پیاده‌سازی
برای زمان‌هایی که درجه چندجمله‌ای توانی از دو نباشد می‌توان دقیقا همین الگوریتم را با تغییرات جزیی اعمال کرد، به این ترتیب که هر دو چندجمله‌ای را به دو بخش تقریبا مساوی تقسیم کرد و از روابط آمده در بالا استفاده کرد. و حتی می‌توان برای دوری از این جزییات آن قدر به سمت چپ چندجمله‌ای جملات با ضریب صفر افزود تا تعداد جملات توانی از دو شوند. البته این گونه پیاده‌سازی کمی کند‌تر از حالت اصلی عمل خواهد کرد زیرا ممکن است این عمل بارها تکرار شود.
ضمنا در عمل، یک مقدار آستانه تعیین می‌شود که برای اندازه ورودی‌های کوچک‌تر از آن، به جای بازگشت از الگوریتم معمولی ضرب استفاده می‌شود. با تعیین درست مقدار آستانه می‌توان به سرعت بهتری در اجرای کلی الگوریتم دست یافت.
تعمیم
همان طور که می‌توان حدس زد، می‌توان به جای این که چندجمله ای‌ها را در ابتدا به دو بخش تقسیم کرد، آن‌ها را به تعداد بیشتری بخش تقسیم کرد. با این کار هرچند تعداد ضرب‌ها کاهش می‌یابد ولی تعداد اعمال جمع لازم افزایش می‌یایند در نتیجه از حدی به بعد دیگر بهبود چندانی حاصل نمی‌شود. در کل استفاده از روش روش‌های دیگر مانند تبدیل‌های فوریه کاراتر و آسان‌تر از تعمیم این روش می‌باشد.
ضرب چندجمله‌ای با استفاده از تبدیل فوریه
تعریف فرم فوریه
برای نمایش تابع راه‌های گوناگونی وجود دارد، به‌طور مثال می‌توان یک تابع را با مجموعه اعضا (برای توابع با دامنه محدود)، ضابطه کلی تابع، یک سری مانند بسط تیلور یا بسط فوریه و … نمایش داد.
یک فرم که در انجام محاسبات بسیار کاراست، را در این جا توضیح می‌دهیم. می‌دانیم که در صفحه می‌توان هرچندجمله‌ای از درجه n را با دقیقا n+1 نقطه از آن به‌طور یکتا مشخص کرد. مثلا هر خط راست را می‌توان با دو نقطه از آن به‌طور یکتا مشخص کرد و برعکس. یا این که هر سه نقطه یک سهمی را به‌طور یکتا تعیین می‌کنند. پس یک روش نمایش چندجمله ای‌های درجه n، نگهداری n+1 نقطه آن است. دقت کنید که این نقاط به دلخواه از دامنه تابع انتخاب می‌شوند. به‌طور دقیق‌تر:
FFT\left ( P_n \right ) = \left \{ \left ( x_i, P_n\left ( x_i \right ) \right ) | x_i \in \mathbb{C , \forall i\neq j : x_i\neq x_j \right \
ویژگی‌های فرم فوریه
نکته جالب در مورد فرم فوریه برای نمایش چندجمله‌ای‌ها، سادگی انجام برخی محاسبات روی آن است. به‌طور مثال اگر بخواهیم دو چندجمله‌ای را جمع/ضرب کنیم، کافی است آن دو را با یک سری مقادیر x یکسان به فرم فوریه تبدیل کنیم و سپس مقادیر متناظر هر نقطه از آن دو تابع را با هم جمع/ضرب کنیم. دیده می‌شود که در این فرم اعمالی مانند ضرب یا تقسیم بسیار آسان‌تر از صورت ضابطه‌ای قابل انجام‌اند. در حقیقت جمع و تفریق و ضرب و تقسیم چندجمله‌های به این فرم با امکان پذیر است. در ادامه به بررسی جزییات پیاده‌سازی ضرب چندجمله ای‌ها می‌پردازیم.
ضرب چندجمله‌ای با تبدیل سریع فوریه
می‌توان دید که اگر دو چندجمله‌ای داشته باشیم می‌توان ابتدا آن‌ها را در تعدادی نقطه مشترک مقداریابی کرد و پس از آن فرم فوریه ضرب آن‌ها را از ضرب مولفه‌های دوم زوج مرتب‌های بدست آمده پیدا کرد. باید توجه کرد که حاصل ضرب، یعنی دارای درجه‌ای برابر است پس باید برای نمایش آن به تعداد زوج مرتب از آن را داشته باشیم، به همین منظور می‌توان از ابتدا هر دو چندجمله‌ای را به فرم فوریه گسترش یافته با نقطه تبدیل کرد، و سپس این نقاط را نظیر به نظیر ضرب کرد و حاصل ضرب را در فرم فوریه بدست آورد. برای یافتن جواب کافی است آن را از فرم فوریه به فرم ضابطه‌ای تبدیل کنیم.
برای این که بتوانیم این فرایند را در زمانی سریع‌تر زمان الگوریتم بدیهی ضرب انجام دهیم از تبدیل فوریه گسسته استفاده می‌کنیم. در این الگوریتم با انتخاب ریشه‌های n ام واحد (که مختلط هستند) و محاسبه مقدار چندجمله‌ای در این نقاط چندجمله‌ای را به فرم فوریه تبدیل می‌کنیم. این کار را برای هر دو چندجمله‌ای عمولوند ضرب انجام می‌دهیم. می‌توان طوری الگوریتم را نوشت که این کار را به سرعت بتوان انجام داد. س÷س دو چندجمله‌ای را که اکنون در فرم فوریه هستند به راحتی در هم ضرب می‌کنیم و در ÷ایان دوباره حاصل ضرب را از فرم فوریه به فرم ضابطه‌ای متداول تبدیل می‌کنیم. این فرایند به‌طور طرح وار در شکل زیر آمده‌است:
پرونده:FFT_Multiply.gif
برای توضیحات دقیق‌تر و نحوه انجام هر یک از مرحله‌های گفته شده به تبدیل فوریه گسسته رجوع کنید.
ضرب چندجمله ای‌های تنک
تعریف و نمایش
در بسیاری از کاربردها پیش می‌آید که مجبور به نگهداری چندجمله‌ای‌هایی هستیم که با این که درجه بزرگی دارند ولی تعداد بسیاری از ضرایب آن‌ها صفر می‌باشد. که استفاده از فرمت نگهداری فرض شده در ابتدای این نوشته برای چنین چند جمله‌هایی بسیار ناکاراست. به چنین چندجمله‌ای‌هایی، تنک می‌گوییم و برای اعمال روی آن‌ها الگوریتم‌های بسیاری پیشنهد شده که از ارزش بالایی هم برخوردارند. یک مثال از چنین چندجمله‌ای‌هایی در زیر آمده‌است:
x^{100-x^2+1
به همین دلیل به جای استفاده از آرایه برای نمایش این چندجمله‌ای‌ها از لیست پیوندی استفاده می‌شود. به این صورت که هر تک جمله را با یک واحد زبان برنامه نویسی که شامل درجه و ضریب آن باشد نمایش می‌دهیم و به آن گره می‌گوییم (مثلا یک struct یا record) و این گره‌ها را در یک لیست پیوندی که به ترتیب درجه آن‌ها ار کوچک به بزرگ مرتب شده است، نگه می‌داریم. برای مثال بالا، استفاده از آرایه به حدود 101 واحد حافظه نیاز دارد در حالی با نمایش اخیر می‌توان آن را با تنها 16 واحد حافظه (حداکثر) نمایش داد زیرا که هر گره در لیست پیوندی اگر شامل توان و ضریب و دو اشاره جلو و عقب باشد به اندازه 4 واحد فضا مصرف می‌کند و با سه گره نیز چندجمله‌ای فوق قابل نمایش است به علاوه یک گره احتمالی برای سرلیست.
الگوریتم‌های چندجمله ای‌های تنک
در مورد این طرز نمایش چندجمله‌ای، نمی‌توان الکوریتم‌های معمول را به کار برد زیرا بسیاری از الگوریتم‌ها فرض می‌کنند که دسترسی تصادفی سریع به هر یک از ضرایب دارند. مثلا نمی‌توان از تبدیل فوریه آن طور که اینجا مطرح شد برای ضرب چندجمله ای‌های تنک استفاده کنیم.
با این حال الکوریتم استراسن که در بالا بحث شد را می‌توان با تغییر جزیی برای چنین نمایشی نیز به کار برد زیرا در طی آن تنها نیاز است که با یک بار عبور از روی چندجمله‌ای، وسط آن را پیدا کرد و سپس آن را به دو بخش تقسیم کرد و الگوریتم را به‌طور بازگشتی ادامه داد. واضح است که چنین تقسیمی به زمان اجرای الگوریتم نمی‌افزاید (از لحاظ تحلیل مجانبی) ولی برخی مسائل جدید در پیاده‌سازی را پیش می‌کشد مانند حالات تهی یا نصف تهی. که در بدترین حالت با افزودن تعداد ثابتی گره با ضریب صفر و اضاه کردن حالات پایه برای زمانی که چلیست پیوندی نمایش دهنده چندجمله‌ای تهی است، به راحتی می‌توان این الگوریتم را روی چندجمله ای‌های تنک نیز اجرا کرد.
الگوریتم‌های پیشرفته‌تر برای ضرب چندجمله‌های تنک که سریع‌تر نیز عمل می‌کنند و مثلا در برخی از آن‌ها از داده ساختار هیپ برای نگهداری چندجمله ای‌ها و نمایش آن‌ها استفاده می‌شود، نیز وجود دارند ولی در این جا به جزییات بیشتری از آن‌ها نمی‌پردازیم.
تبدیل فوریه گسسته
الگوریتم
چندجمله‌ای
ضرب
لیست پیوندی