Polynomial Factoring(Self - made)

Discuss Computer Science and Programming related problems

Moderators:Labib, bristy1588

User avatar
Fm Jakaria
Posts:79
Joined:Thu Feb 28, 2013 11:49 pm
Polynomial Factoring(Self - made)

Unread post by Fm Jakaria » Tue Dec 10, 2013 4:20 pm

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.
You cannot say if I fail to recite-
the umpteenth digit of PI,
Whether I'll live - or
whether I may, drown in tub and die.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Polynomial Factoring(Self - made)

Unread post by *Mahi* » Thu Dec 19, 2013 11:07 pm

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.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Polynomial Factoring(Self - made)

Unread post by Masum » Tue Jan 07, 2014 1:02 pm

এই সমস্যার কোন সাধারণ সমাধান আমার জানা মতে নাই, তবে থাকলে সেটা খুবই অসাধারণ কিছু একটা হবে। আর হয়তো কোন সমস্যাতে কিছু একটা বলা থাকতে পারে যাতে বাইনারী সার্চ অথবা টারনারী সার্চ অথবা রেগুলার কিছু ব্যবহার করে করা যেতে পারে। তবে এর সাধারণ কিছু যে নাই সেটা আমি মোটামুটি সিওর। কারণ, যে কোন পলিনোমিয়াল তো দূরের কথা, $x^n-1$ এর ফ্যাক্টোরিং করতে গেলেই Cyclotomic Polynomial এর সঙ্গে ডিপি লাগে(আমি করছিলাম, তাই পেইনটা কোন মাত্রার জানি :( ) আর কোডিংটা কি অসাধারণ পেইন দিছে সেটা আর নাই বললাম! এবং শুধু এইটা সমাধান করতে গিয়েই Cyclotomic Polynomial এর বেশ কিছু জিনিস লাগে।
মাহি, করে ফেলতো $x^n-1$ এর ফ্যাক্টোরাইজেশনের কোডটা, কোন ব্যাপার না। ;) আর আগে থেকেই শিখে রাখ, কারণ আমি প্রব্লেম সেট করতে গেলে এইটা সরাসরি অথবা অন্য একটা প্রব্লেমের সাবপ্রব্লেম হিসেবে দিতে পারি। তাই কইরা টীম নোটবুকে রাইখা দে । 8-)
One one thing is neutral in the universe, that is $0$.

Post Reply