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

در این مسئله می خواهیم دو چندجمله ای از درجه‌های $m$ و $n$ که به فرم ضابطه ای با ضرایب هر توانی از x آن‌ها مشخص شده اند را در هم ضرب کنیم و ضابطهٔ چندجمله ای حاصل را بدست آوریم. در ابتدا فرض می کنیم که برای نمایش چندجمله ای‌ها در فرم ضابطه ای یک آرایه به طول درجهٔ چندجمله ای به علاوهٔ یک می گیریم و در خانهٔ i ام ضریب $x^i$ را ذحیره می کنیم. نمایش متداول دیگر این است که تنها ضرایب ناصفر را در یک لیست پیوندی نگهداری کنیم.

الگوریتم بدیهی ضرب چندجمله ای

اگر دو چند جمله ای داشته باشیم که هر کدام با ضرایب توان‌های متغیرشان نمایش داده شوند، الگوریتم بسیار ساده ای برای محاسبهٔ حاصا ضرب آن‌ها در زمان $\Theta \left ( m \cdot n \right )$ وجود دارد ($m$ و $n$ درجه‌های چندجمله ایها هستند). در حقیقت این الگوریتم، همان روشی است که در محاسبات روزانه به کار می بریم و شبه کد آن در زیر آمده است. همان طور که گفته شد برای سادگی فرض می کنیم که هر ضرایب هر چندجمله ای از درجهٔ $k$ در آرایه ای به طول $k+1$ به روش

ذخیره شود.

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[i]

return R

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

با این الگوریتم می توان حاصل ضرب دو چندجمله ای را با سرعت بیش تری نسبت به الگوریتم بدیهی ضرب یافت. ایدهٔ اصلی این الگوریتم این است که از آن جایی که عمل جمع در رایانه‌ها بسیار سریع تر از عمل ضرب انجام پذیر است، می توان در الگوریتم بدیهی ضرب که همان طور که قبلا بررسی شد در آن به تعداد $\Theta \left ( m \cdot n \right )$ عمل ضرب نیاز است، تعداد اعمال ضرب را کم تر کرد و به ازای آن کمی به تعداد اعمال جمع افزود که روند دقیق کار در ادامه توضیح داده خواهد شد. به این ترتیب می توان زمان اجرای کلی ضرب دو چندجمله ای را بهبود بخشید.
برای سادگی فرض کنید می خواهیم دو چندجمله ای از درجهٔ $n=2^{k+1}-1$ را در هم ضرب کنیم. می نویسیم:

$P\left ( x \right ) = P_1\left ( x \right ) + x^{2^{k}} \cdot P_2\left ( x \right )$

$Q\left ( x \right ) = Q_1\left ( x \right ) + x^{2^{k}} \cdot Q_2\left ( x \right )$

یعنی هر چندجمله ای را دو بخش کردیم. واضح است که برای ضرب داریم:

$P \cdot Q = P_1 \cdot Q_1 + x ^ {2^k} \left ( P_1 \cdot Q_2 + P_2 \cdot Q_1 \right ) + x ^ {2^{k+1}} P_2 \cdot Q_2$

ایدهٔ اصلی این است که اگر تعریف کنیم:

$A = P_1 \cdot Q_1$

$B = P_2 \cdot Q_2$

$C = \left ( P_1 + P_2 \right ) \cdot \left ( Q_1 + Q_2 \right )$

با جایگذاری در معادلهٔ اولیهٔ ضرب خواهیم داشت:

$P \cdot Q = A + x ^ {2^k} \cdot \left ( C - A - B \right ) + x ^ {2 ^ {k + 1}} \cdot B$

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

$T\left ( n \right ) = 3T\left ( \frac{n}{2} \right ) + \Theta \left ( n \right )$

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

$T\left ( n \right ) = \Theta \left ( n \cdot lg \left ( n \right ) \right )$

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

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

تعمیم

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

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

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

برای نمایش تابع راه‌های گوناگونی وجود دارد، به طور مثال می توان یک تابع را با مجموعه اعضا (برای توابع با دامنهٔ محدود)، ضابطهٔ کلی تابع، یک سری مانند بسط تیلور یا بسط فوریه و ... نمایش داد. یک فرم که در انجام محاسبات بسیار کاراست، را در این جا توضیح می دهیم. می دانیم که در صفحه می توان هرچند جمله ای از درجه 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 یکسان به فرم فوریه تبدیل کنیم و سپس مقادیر متناظر هر نقطه از آن دو تابع را با هم جمع/ضرب کنیم. دیده می‌شود که در این فرم اعمالی مانند ضرب و یا تقسیم بسیار آسان تر از صورت ضابطه ای قابل انجام اند. در حقیقت جمع و تفریق و ضرب و تقسیم چندجمله‌های به این فرم با $\Theta \left (n \right )$ امکان پذیر است. در ادامه به بررسی جزییات پیاده سازی ضرب چندجمله ای‌ها می پردازیم.

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

می توان دید که اگر دو چندجمله ای داشته باشیم می توان ابتدا آن‌ها را در تعدادی نقطهٔ مشترک مقداریابی کرد و پس از آن فرم فوریهٔ ضرب آن‌ها را از ضرب مولفه‌های دوم زوج مرتب‌های بدست آمده پیدا کرد. باید توجه کرد که حاصل ضرب، یعنی $P \cdot Q$ دارای درجه ای برابر $m+n$ است پس باید برای نمایش آن به تعداد $m+n+1$ زوج مرتب از آن را داشته باشیم، به همین منظور می توان از ابتدا هر دو چندجمله ای را به فرم فوریهٔ گسترش یافته با $m+n+1$ نقطه تبدیل کرد، و سپس این نقاط را نظیر به نظیر ضرب کرد و حاصل ضرب را در فرم فوریه بدست آورد. برای یافتن جواب کافی است آن را از فرم فوریه به فرم ضابطه ای تبدیل کنیم.

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

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

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

تعریف و نمایش

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

$x^{100}-x^2+1$

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

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

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

جستارهای وابسته

• تبدیل فوریه گسسته
• الگوریتم
• چندجمله ای
• ضرب
• لیست پیوندی

منابع

• [۱] Strassen+algorithm+for+polynomial+multiplication
• Cormen, Thomas H.; Charles E. Leiserson, Ronald L. Rivest, and کلیفورد استین (2001). "Chapter 30: Polynomials and the FFT". مقدمه‌ای بر الگوریتم‌ها (Second ed.). MIT Press and McGraw-Hill. pp. 822–848. ISBN 0-262-03293-7.  esp. section 30.2: The DFT and FFT, pp. 830–838.

• تبدیل فوریه گسسته