Page 1 of 1

Polynomial Factoring(Self - made)

Posted: Tue Dec 10, 2013 4:20 pm
by Fm Jakaria
Is it possible to fully factor any polynomial with arbitrary non-negative degree and integer coefficients to polynomials with integer coefficients?

Input : Degree of the polynomial; then respective coefficients.
Output: If the polynomial is irreducible, we'll get the message of irreducibility. Else we'll get the list of all polynomials which appear when the given polynomial is fully factored; with the numbers of times these appear. A polynomial is listed means mentioning the respective coefficients.
Respective coefficients indicates starting from the zero degree coefficient.

Example:
1) Input:
3.
0.
1.
2.
1.
Output:
0,1. 1 times.
1,2,1. 2 times.

2)Input:
1.
1.
1.
Output:
This is irreducible.

Note: In the first example, x^3 + 2x^2 + x = x((x+1)^2). In the second, x+1 is mentioned.

Re: Polynomial Factoring(Self - made)

Posted: Thu Dec 19, 2013 11:07 pm
by *Mahi*
For degree less than or equal to 5, yes.
For degree more than 5, no. As there is no general formula for generating the solutions of a polynomial of degree more than five(and there can't be) the only solution is searching, which is not possible in normal computing time.

Re: Polynomial Factoring(Self - made)

Posted: Tue Jan 07, 2014 1:02 pm
by Masum
এই সমস্যার কোন সাধারণ সমাধান আমার জানা মতে নাই, তবে থাকলে সেটা খুবই অসাধারণ কিছু একটা হবে। আর হয়তো কোন সমস্যাতে কিছু একটা বলা থাকতে পারে যাতে বাইনারী সার্চ অথবা টারনারী সার্চ অথবা রেগুলার কিছু ব্যবহার করে করা যেতে পারে। তবে এর সাধারণ কিছু যে নাই সেটা আমি মোটামুটি সিওর। কারণ, যে কোন পলিনোমিয়াল তো দূরের কথা, $x^n-1$ এর ফ্যাক্টোরিং করতে গেলেই Cyclotomic Polynomial এর সঙ্গে ডিপি লাগে(আমি করছিলাম, তাই পেইনটা কোন মাত্রার জানি :( ) আর কোডিংটা কি অসাধারণ পেইন দিছে সেটা আর নাই বললাম! এবং শুধু এইটা সমাধান করতে গিয়েই Cyclotomic Polynomial এর বেশ কিছু জিনিস লাগে।
মাহি, করে ফেলতো $x^n-1$ এর ফ্যাক্টোরাইজেশনের কোডটা, কোন ব্যাপার না। ;) আর আগে থেকেই শিখে রাখ, কারণ আমি প্রব্লেম সেট করতে গেলে এইটা সরাসরি অথবা অন্য একটা প্রব্লেমের সাবপ্রব্লেম হিসেবে দিতে পারি। তাই কইরা টীম নোটবুকে রাইখা দে । 8-)