Sign in to follow this  
Nice Coder

Factorising quadratic trinomials where the coefficient of X^2 is not 1

Recommended Posts

Nice Coder    366
Ok, i'm factorising quadratic trinomials, and i want to find a really fast way to do it. (i would also like to know how to do it without using guess and check.) What i want to know, is what is the fastest way to do this? From, Nice coder [Edited by - Nice Coder on July 23, 2005 10:41:21 PM]

Share this post


Link to post
Share on other sites
Nice Coder    366

Private Sub Form_Load()
Dim t As Integer
Dim u As Integer
tim = Timer
Open "C:\Q.txt" For Input As #1
Open "C:\A.txt" For Output As #2
Do Until EOF(1)
Input #1, t
Input #1, u

Print #2, "=X^2 " & IIf(t >= 0, "+ ", "- ") & IIf(Abs(t) <> 1, Abs(t), "") & "X " & IIf(u >= 0, "+ ", "- ") & Abs(u)

lim = 10
Do
For x = -lim To lim
For y = -lim To lim
s = x + y
p = x * y
DoEvents
If s = t And p = u Then
Print #2, "=(X " & IIf(x >= 0, "+ ", "- ") & Abs(x) & ")(X " & IIf(y >= 0, "+ ", "- ") & Abs(y) & ")"
GoTo nextnum:
End If
Next y
Next x
lim = lim * 2
Loop
nextnum:
Print #2, ""
Loop
Close #1
Print #2, "Time required: " & Timer - tim
Close #2
End
End Sub



Thats my code so far.
Its now currently at 0.0032552083 seconds per node. (Which is fast, but we can do better!)

From,
Nice coder

Share this post


Link to post
Share on other sites
Nice Coder    366
Hmm, yes.

But is there anything faster? (ie. for the algorithm?)

Also, if the coefficient of X^2 is not 1, how would i factorise them?

From,
NIce coder

[Edited by - Nice Coder on July 23, 2005 10:13:08 PM]

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by Nice Coder
Hmm, yes.

But is there anything faster? (ie. for the algorithm?)


Actually use the quadratic formula perhaps? (which would be a hell of a lot more general, too)

Quote:
Also, if the coefficient of X^2 is not 1, how would i factorise them?


Just divide through by said coefficient first (and list it as a separate constant factor in the result); a constant factor will not affect where the roots are.

Share this post


Link to post
Share on other sites
smart_idiot    1298
No promises that I didn't screw any of this up.

The math:
(a*x+f)*(x+e)=a*x*x+b*x+c
e=b/a/2+sqrt(b*b-(4*a*c))/a/2
f=c/e


A program:

#include <iostream>
#include <complex>
#include <string>
#include <sstream>

std::string comp(const std::complex<double> &var)
{
std::stringstream stream;

if(var.real() && var.imag())
{
stream << "(" << var.real();

if(var.imag() >= 0)
stream << '+' << var.imag() << "i)";
else stream << var.imag() << "i)";
}
else if(var.imag())
{
if(var.imag() >= 0)
stream << var.imag() << "i";
else stream << var.imag() << "i";
}
else if(var.real())
stream << var.real();

return stream.str();
}

std::string mult(const std::string &a, const std::string &b)
{
if(a.empty())
return a;
else if(a == "1")
return b;
else return a + "*" + b;
}

std::string add(const std::string &a, const std::string &b)
{
if(a.empty())
{
if(b.empty())
return "0";
else return b;
}
else if(b.empty())
return a;
else if(b[0] == '-')
return a+"-"+(b.c_str()+1);
else return a + "+" + b;
}

int main()
{
std::complex<double> a, b, c;

std::cout << "a*x^2+b*x+c\na=";
std::cin >> a;
std::cout << "b=";
std::cin >> b;
std::cout << "c=";
std::cin >> c;

std::complex<double>
e=(0.5*b/a)+(0.5*std::sqrt(b*b-(4.0*a*c))/a),
f=c/e;

// (a*x+f)*(x+e)
std::cout << "("<<add(mult(comp(a),"x"),comp(f))<<")*("<<add("x",comp(e))<<")" << std::endl;
}




Sample run:
a*x^2+b*x+c
a=2
b=13
c=15
(2*x+3)*(x+5)


[Edited by - smart_idiot on July 24, 2005 3:58:52 AM]

Share this post


Link to post
Share on other sites
Nice Coder    366
Many thanks to you smart_idiot!

(i would rate++ you, but i've already rated you fully.)

Um, smart idiot, when i try
a = -2
b = -13
c = -15

It spits back an answer of
(-2X + 1.5)(X - 10)

Yet, for X = 17:
-2 * x ^ 2 - (13 * x) - 15 = -814
(-2 * x + 1.5) * (x - 10) = 227.5

From,
Nice coder

Share this post


Link to post
Share on other sites
Nice Coder    366
ok, it works now.

Should it be producing whole numbers? (ie. shouldn't factorisation require all of the numbers to remain integers?)

From,
Nice coder

Share this post


Link to post
Share on other sites
smart_idiot    1298
I don't think it's a requirement. If you don't like that, you'll hate the result of x2+2x+3.

Also, note the square root. Since there's two results for it, there's actually two possible answers. For your example -2x2-13x-15, the two possible answers are (-2*x-10)*(x+1.5) and (-2*x-3)*(x+5). If you don't like one answer, feel free to try the other.

[Edited by - smart_idiot on July 24, 2005 3:32:54 AM]

Share this post


Link to post
Share on other sites
smart_idiot    1298
Just calculate it twice, using the positive and negative roots, i.e., change e=b/a/2+sqrt(b*b-(4*a*c))/a/2 to e=b/a/2-sqrt(b*b-(4*a*c))/a/2 for the second time.

Share this post


Link to post
Share on other sites
Nice Coder    366
Ok, good.

I've got it working now.

But a small problem.
for "-2X^2 + 13X + 25"

The answer it spits back is (-2X + 16.1046863561493)(X + 1.55234317807464)

Which isn't very right.

It does produce the right answer "(-2X - 3)(X + 5)" to your equasion "-2x^2 - 13x - 15" tho.

From,
Nice coder

Share this post


Link to post
Share on other sites
smart_idiot    1298
Maxima gives me this:


(%i1) expand((-2*X+16.1046863561493)*(X+1.55234317807464));

2
(%o1) - 2 X + 13.00000000000002 X + 25.0000000000001


Looks like -2X^2 + 13X + 25 to me.

Share this post


Link to post
Share on other sites
Zahlman    1682
You could tell it to output square root values symbolically rather than actually evaluating them... you might want to make a class like so:


// very not tested!
class squareRootFraction {
// represents sqrt(num/denom).
int num, denom;
void reduce() {
int div = gcd(num, denom); // todo: implement
num /= div; denom /= div;
}
public:
squareRootFraction(int num, int denom = 1) : num(num), denom(denom) {
reduce();
}
squareRootFraction& operator /= (int x) {
denom *= x*x; reduce(); return *this;
}
squareRootFraction& operator *= (int x) {
num *= x*x; reduce(); return *this;
}
friend ostream& operator<<(ostream& os, const squareRootFraction& me) {
os << "sqrt(" << me.num << "/" me.denom << ")";
return os;
}
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this