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

در این مسئله می خواهیم دو چندجمله ای از درجه‌های  و  که به فرم ضابطه‌ای با ضرایب هر توانی از 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
R[i+j] += P[i]*Q[j]
return R

الگوریتم استراسن ( الگوریتم کاراتسوبا) برای ضرب چندجمله ای‌ها

با این الگوریتم می‌توان حاصل ضرب دو چندجمله‌ای را با سرعت بیشتری نسبت به الگوریتم بدیهی ضرب یافت. ایدهٔ اصلی این الگوریتم این است که از آن جایی که عمل جمع در رایانه‌ها بسیار سریع تر از عمل ضرب انجام پذیر است، می‌توان در الگوریتم بدیهی ضرب که همان طور که قبلاً بررسی شد در آن به تعداد  عمل ضرب نیاز است، تعداد اعمال ضرب را کم تر کرد و به ازای آن کمی به تعداد اعمال جمع افزود که روند دقیق کار در ادامه توضیح داده خواهد شد. به این ترتیب می‌توان زمان اجرای کلی ضرب دو چندجمله‌ای را بهبود بخشید.

برای سادگی فرض کنید می خواهیم دو چندجمله‌ای از درجهٔ  را در هم ضرب کنیم. می نویسیم:

یعنی هر چندجمله‌ای را دو بخش کردیم. واضح است که برای ضرب داریم:
ایدهٔ اصلی این است که اگر تعریف کنیم:
با جایگذاری در معادلهٔ اولیهٔ ضرب خواهیم داشت:
پس همان طور که نشان داده شد، می‌توان با سه عمل ضرب (برای محاسبهٔ A و B و C) با اندازهٔ نصف و سپس محاسبهٔ رابطهٔ بالا جواب مسئله را پیدا کرد.
تحلیل زمانی: در این الگوریتم در اصل به جای هر چهار عمل ضرب در الگوریتم بدیهی ضرب، تنها سه تا ضرب انجام می‌شود. چنین استفادهٔ هوشمندانه‌ای از تکراری بودن بخشی از محاسبات بسیار شبیه الگوریتم استراسن برای ضرب ماتریس هاست. اثبات می‌شود که این الگوریتم ازΘ(nlg3) است. زیرا اگر زمان اجرای الگوریتم با اندازه ورودی n را T(n) بنامیم، می‌توان به رابطهٔ بازگشتی زیر رسید:

که با یکی از روش‌های حل معادله بازگشتی مانند قضیهٔ اساسی می‌توان دید که:

نکات پیاده‌سازی

برای زمان‌هایی که درجهٔ چندجمله‌ای توانی از دو نباشد می‌توان دقیقاً همین الگوریتم را با تغییرات جزیی اعمال کرد، به این ترتیب که هر دو چندجمله‌ای را به دو بخش تقریباً مساوی تقسیم کرد و از روابط آمده در بالا استفاده کرد. و حتی می‌توان برای دوری از این جزییات آن قدر به سمت چپ چندجمله‌ای جملات با ضریب صفر افزود تا تعداد جملات توانی از دو شوند. البته این گونه پیاده‌سازی کمی‌کند تر از حالت اصلی عمل خواهد کرد زیرا ممکن است این عمل بارها تکرار شود.
ضمناً در عمل، یک مقدار آستانه تعیین می‌شود که برای اندازه ورودی‌های کوچک‌تر از آن، به جای بازگشت از الگوریتم معمولی ضرب استفاده می‌شود. با تعیین درست مقدار آستانه می‌توان به سرعت بهتری در اجرای کلی الگوریتم دست یافت.

تعمیم

همان طور که می‌توان حدس زد، می‌توان به جای این که چندجمله ای‌ها را در ابتدا به دو بخش تقسیم کرد، آن‌ها را به تعداد بیشتری بخش تقسیم کرد. با این کار هرچند تعداد ضرب‌ها کاهش می یابد ولی تعداد اعمال جمع لازم افزایش می یایند در نتیجه از حدی به بعد دیگر بهبود چندانی حاصل نمی‌شود. در کل استفاده از روش روش‌های دیگر مانند تبدیل‌های فوریه کاراتر و آسان تر از تعمیم این روش می‌باشد.

تعریف فرم فوریه

برای نمایش تابع راه‌های گوناگونی وجود دارد، به‌طور مثال می‌توان یک تابع را با مجموعه اعضا (برای توابع با دامنهٔ محدود)، ضابطهٔ کلی تابع، یک سری مانند بسط تیلور یا بسط فوریه و ... نمایش داد.
یک فرم که در انجام محاسبات بسیار کاراست، را در این جا توضیح می دهیم. می دانیم که در صفحه می‌توان هرچندجمله‌ای از درجه n را با دقیقاً n+1 نقطه از آن به‌طور یکتا مشخص کرد. مثلاً هر خط راست را می‌توان با دو نقطه از آن به‌طور یکتا مشخص کرد و برعکس. یا این که هر سه نقطه یک سهمی را به‌طور یکتا تعیین می‌کنند. پس یک روش نمایش چندجمله ای‌های درجه n، نگهداری n+1 نقطهٔ آن است. دقت کنید که این نقاط به دلخواه از دامنهٔ تابع انتخاب می‌شوند. به‌طور دقیق تر:

ویژگی‌های فرم فوریه

نکتهٔ جالب در مورد فرم فوریه برای نمایش چندجمله‌ای ها، سادگی انجام برخی محاسبات روی آن است. به‌طور مثال اگر بخواهیم دو چندجمله‌ای را جمع/ضرب کنیم، کافی است آن دو را با یک سری مقادیر x یکسان به فرم فوریه تبدیل کنیم و سپس مقادیر متناظر هر نقطه از آن دو تابع را با هم جمع/ضرب کنیم. دیده می‌شود که در این فرم اعمالی مانند ضرب یا تقسیم بسیار آسان تر از صورت ضابطه‌ای قابل انجام‌اند. در حقیقت جمع و تفریق و ضرب و تقسیم چندجمله‌های به این فرم با  امکان‌پذیر است. در ادامه به بررسی جزییات پیاده‌سازی ضرب چندجمله ای‌ها می پردازیم.

ضرب چندجمله‌ای با تبدیل سریع فوریه

می توان دید که اگر دو چندجمله‌ای داشته باشیم می‌توان ابتدا آن‌ها را در تعدادی نقطهٔ مشترک مقداریابی کرد و پس از آن فرم فوریهٔ ضرب آن‌ها را از ضرب مؤلفه‌های دوم زوج مرتب‌های بدست آمده پیدا کرد. باید توجه کرد که حاصل ضرب، یعنی  دارای درجه‌ای برابر  است پس باید برای نمایش آن به تعداد  زوج مرتب از آن را داشته باشیم، به همین منظور می‌توان از ابتدا هر دو چندجمله‌ای را به فرم فوریهٔ گسترش یافته با  نقطه تبدیل کرد، و سپس این نقاط را نظیر به نظیر ضرب کرد و حاصل ضرب را در فرم فوریه بدست آورد. برای یافتن جواب کافی است آن را از فرم فوریه به فرم ضابطه‌ای تبدیل کنیم.

برای این که بتوانیم این فرایند را در زمانی سریع تر زمان الگوریتم بدیهی ضرب انجام دهیم از تبدیل فوریه گسسته استفاده می کنیم. در این الگوریتم با انتخاب ریشه‌های n ام واحد (که مختلط هستند) و محاسبهٔ مقدار چندجمله‌ای در این نقاط چندجمله‌ای را به فرم فوریه تبدیل می کنیم. این کار را برای هر دو چندجمله‌ای عمولوند ضرب انجام می دهیم. می‌توان طوری الگوریتم را نوشت که این کار را به سرعت بتوان انجام داد. س÷س دو چندجمله‌ای را که اکنون در فرم فوریه هستند به راحتی در هم ضرب می کنیم و در ÷ایان دوباره حاصل ضرب را از فرم فوریه به فرم ضابطه‌ای متداول تبدیل می کنیم. این فرایند به‌طور طرح وار در شکل زیر آمده‌است:
برای توضیحات دقیق تر و نحوهٔ انجام هر یک از مرحله‌های گفته شده به تبدیل فوریه گسسته رجوع کنید.

تعریف و نمایش

در بسیاری از کاربردها پیش می‌آید که مجبور به نگهداری چندجمله‌ای‌هایی هستیم که با این که درجهٔ بزرگی دارند ولی تعداد بسیاری از ضرایب آن‌ها صفر می‌باشد. که استفاده از فرمت نگهداری فرض شده در ابتدای این نوشته برای چنین چند جمله‌هایی بسیار ناکاراست. به چنین چندجمله‌ای هایی، تنک می گوییم و برای اعمال روی آن‌ها الگوریتم‌های بسیاری پیشنهد شده که از ارزش بالایی هم برخوردارند. یک مثال از چنین چندجمله‌ای‌هایی در زیر آمده‌است:
به همین دلیل به جای استفاده از آرایه برای نمایش این چندجمله‌ای‌ها از لیست پیوندی استفاده می‌شود. به این صورت که هر تک جمله را با یک واحد زبان برنامه نویسی که شامل درجه و ضریب آن باشد نمایش می دهیم و به آن گره می گوییم (مثلاً یک struct یا record) و این گره‌ها را در یک لیست پیوندی که به ترتیب درجه آن‌ها ار کوچک به بزرگ مرتب شده‌است، نگه می داریم. برای مثال بالا، استفاده از آرایه به حدود 101 واحد حافظه نیاز دارد در حالی با نمایش اخیر می‌توان آن را با تنها 16 واحد حافظه (حداکثر) نمایش داد زیرا که هر گره در لیست پیوندی اگر شامل توان و ضریب و دو اشاره جلو و عقب باشد به اندازهٔ 4 واحد فضا مصرف می‌کند و با سه گره نیز چندجمله‌ای فوق قابل نمایش است به علاوهٔ یک گره احتمالی برای سرلیست.

الگوریتم‌های چندجمله ای‌های تنک

در مورد این طرز نمایش چندجمله ای، نمی توان الکوریتم‌های معمول را به کار برد زیرا بسیاری از الگوریتم‌ها فرض می‌کنند که دسترسی تصادفی سریع به هر یک از ضرایب دارند. مثلاً نمی توان از تبدیل فوریه آن طور که اینجا مطرح شد برای ضرب چندجمله ای‌های تنک استفاده کنیم.

با این حال الکوریتم استراسن که در بالا بحث شد را می‌توان با تغییر جزیی برای چنین نمایشی نیز به کار برد زیرا در طی آن تنها نیاز است که با یک بار عبور از روی چندجمله ای، وسط آن را پیدا کرد و سپس آن را به دو بخش تقسیم کرد و الگوریتم را به‌طور بازگشتی ادامه داد. واضح است که چنین تقسیمی به زمان اجرای الگوریتم نمی‌افزاید (از لحاظ تحلیل مجانبی) ولی برخی مسائل جدید در پیاده‌سازی را پیش می کشد مانند حالات تهی یا نصف تهی. که در بدترین حالت با افزودن تعداد ثابتی گره با ضریب صفر و اضاه کردن حالات پایه برای زمانی که چلیست پیوندی نمایش دهندهٔ چندجمله‌ای تهی است، به راحتی می‌توان این الگوریتم را روی چندجمله ای‌های تنک نیز اجرا کرد.

الگوریتم‌های پیشرفته تر برای ضرب چندجمله‌های تنک که سریع تر نیز عمل می‌کنند و مثلاً در برخی از آن‌ها از داده ساختار هیپ برای نگهداری چندجمله ای‌ها و نمایش آن‌ها استفاده می‌شود، نیز وجود دارند ولی در این جا به جزییات بیشتری از آن‌ها نمی‌پردازیم.