| Author |
Message |
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
 Posted: 01 Sep 2009 09:04:12 am Post subject: |
|
|
Okay, so I was googling (verb?) how to find the factors for N degree polynomials. Well, I found a page about Newton's method, and looked it up in wikipedia, and... I couldn't understand it. What I have, is a simple N degree polynomial.
There are four examples that I am trying to use (So I can test this method), that I want to get it down to at least a quadratic. Oh, btw, this is for a programming solution, with large numbers, so guess/check is out of the question.
Here are the test polynomials:
3X2+4X+1
2X2+2X+1
1X2+8X+y
3X3+0X2+0X+7
There is one that has a degree of 3. The reason, is that I am not sure If I can factor a binomial without guessing/checking, so I want to know if those can be reduced.
The basic idea, or at least, what I think would work in my head, is to find some value, and take that out of the polynomial, in order to simplify it. eg, we had a N=3 polynomial, now we have a N=2 polynomial. (N is the highest power.)
I do not understand all the derivatives, and all of that, but I think it would be easier to see a programming example, and learn from that.
thanks!! 
Last edited by Guest on 01 Sep 2009 09:06:55 am; edited 1 time in total |
|
| Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
| Posted: 01 Sep 2009 09:50:16 pm Post subject: |
|
|
Ok, I will redo the question, since if I find the derivative, I should be able to do the rest.
The question is, how do I find the derivative?
Last edited by Guest on 01 Sep 2009 09:50:54 pm; edited 1 time in total |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 01 Sep 2009 09:59:56 pm Post subject: |
|
|
Graphmastur wrote: Ok, I will redo the question, since if I find the derivative, I should be able to do the rest.
The question is, how do I find the derivative?
... the usual formula: d(xn) == n*xn-1 dx
"The basic idea, or at least, what I think would work in my head, is to find some value, and take that out of the polynomial, in order to simplify it. eg, we had a N=3 polynomial, now we have a N=2 polynomial. (N is the highest power.)"
You're thinking of "polynomial deflation". I suggest you try looking for the book "Numerical Methods That Work" by F.S. Acton; it'll go a long way towards enlightenment...
thornahawk |
|
| Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
| Posted: 01 Sep 2009 10:09:56 pm Post subject: |
|
|
Okay, now I get eleverything but limits.
I can't find the book at my local library. |
|
| Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
| Posted: 02 Sep 2009 01:54:08 pm Post subject: |
|
|
Okay, so how do I solve for zero now? I have a java polynomial class. Basically, if I find one factor, I can simplify, and find the rest now.
So. How do I find a factor for it, now? |
|
| Back to top |
|
|
simplethinker
snjwffl
Active Member
Joined: 25 Jul 2006
Posts: 700
|
| Posted: 02 Sep 2009 02:21:50 pm Post subject: |
|
|
Graphmastur wrote: Okay, so how do I solve for zero now? I have a java polynomial class. Basically, if I find one factor, I can simplify, and find the rest now.
So. How do I find a factor for it, now?
Do you mean how to use Newton's method to find the zero? First of all, the Newton-Raphson method will most likely not give you an exact root in a reasonable number of iterations, only to a certain degree of accuracy (which you can choose).
Now, for finding roots: The value of a function f(x+h) can be approximated by f(x) + f'(x)*h if h is small (f' = derivative of f). Given an 'x', we want to find an 'h' such that f(x+h)=0. Solving for 'h' in f(x+h) = 0 = f(x) + f'(x)*h gives h = -f(x)/f'(x). So the new approximation to the root is x+h = x - f(x)/f'(x). Initially, you just pick a value of x to start with. Plugging the new x+h in for x recursively gives a better and better approximation to the root each time. If you want to be accurate to N places, repeat until h ≤ 10N.
When trying to find the roots of a polynomial P(x), just use P(x) in place of f(x) from above.
Last edited by Guest on 05 Jul 2010 08:09:01 am; edited 1 time in total |
|
| Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
| Posted: 02 Sep 2009 02:53:59 pm Post subject: |
|
|
In my program, I have a list of coefficients. (not calc list. Starts with zero. Wherever it is in the list is x to that power.). That is how it is stored.
How do I find the derivative?
(thanks, for explaining it.)
So, if I can get the derivative, and implement the division, would that mean that I would take the output of that function, stated above, and put it back in as x? |
|
| Back to top |
|
|
simplethinker
snjwffl
Active Member
Joined: 25 Jul 2006
Posts: 700
|
| Posted: 02 Sep 2009 03:35:58 pm Post subject: |
|
|
Graphmastur wrote: In my program, I have a list of coefficients. (not calc list. Starts with zero. Wherever it is in the list is x to that power.). That is how it is stored.
How do I find the derivative?
Here I put D() to mean differentiate (with respect to x), but it's just to ease typing it here. Two things:
1) A property of differentiation is that D(f + g) = D(f) + D(g) (where f, g are functions of x), and D( A*f ) = A * D(f) (where f is a function of x and A is a constant).
2) D(xn) = nxn-1 (and D(1)=0 since a constant doesn't change with x)
Now, a polynomial can be written as P(x) = a+bx+cx2+dx3+.... It's derivative is P'(x) = D(a+bx+cx2+...) = a*D(1)+b*D(x)+c*D(x2)+... = 0+b+2cx+3dx2+.... If the coefficients are {a, b, c, d, e, ...} (where 'a' is constant term, 'b' is the coefficent of x, ...), the derivative would be {b, 2c, 3d, 4e, ...} (note that the 'a' is gone, and now 'b' is the constant term, '2c' is the coefficient of x, ...). Here's a simple BASIC program (I don't know what language you're using and I'm pretty sure you can understand BASIC ) that will find the derivative of a polynomial (coefficients are in L1):
Code:
:seq(N*L1(N+1),N,1,dim(L1)-1
It starts at the second element since the first one is constant and so will be ignored (it becomes zero). The L1(N+1) is because list indices start at one instead of zero.
Quote: So, if I can get the derivative, and implement the division, would that mean that I would take the output of that function, stated above, and put it back in as x?
Yes. In BASIC, if Y1 holds the function, Y2 is its derivative, and N is the desired accuracy:
Code:
:Repeat abs(H)≤10^N
:Y1(X)/Y2(X)→H
:X-H→X
:End
will give the answer in X
Last edited by Guest on 05 Jul 2010 08:09:24 am; edited 1 time in total |
|
| Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
| Posted: 02 Sep 2009 03:48:53 pm Post subject: |
|
|
so if:
f(x)=3X^2 + 4X + 1
f'(X)=6X + 4
Is that correct?
I know the factors of f are (X+1)(3X+1). What is this 6X+4? |
|
| Back to top |
|
|
simplethinker
snjwffl
Active Member
Joined: 25 Jul 2006
Posts: 700
|
| Posted: 02 Sep 2009 03:56:09 pm Post subject: |
|
|
Graphmastur wrote: so if:
f(x)=3X^2 + 4X + 1
f'(X)=6X + 4
Is that correct?
I know the factors of f are (X+1)(3X+1). What is this 6X+4?
6X+4 is the derivative. So for Newton's method each new approximation to the root would be X-(3X2+1+4X)/(6X+4)
Last edited by Guest on 05 Jul 2010 08:08:40 am; edited 1 time in total |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 02 Sep 2009 08:19:11 pm Post subject: |
|
|
Graphmastur wrote: In my program, I have a list of coefficients. (not calc list. Starts with zero. Wherever it is in the list is x to that power.). That is how it is stored.
How do I find the derivative?
In that case, Horner's rule is much more efficient. :)
thornahawk |
|
| Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
| Posted: 04 Sep 2009 07:46:55 pm Post subject: |
|
|
Okay, one more question about this.
Okay, I have X which is the square root of N.
So (X+P)(X-Q)=N. That means X2+PX-QX-PQ=N. Since X is the square root of N, that means that PX-QX-PQ=0.
So that means that -PX+QX+PQ=0. Which means -P+Q+(PQ/X)=0. So (PQ/X)=P-Q. So PQ=X(P-Q). So PQ/(P-Q)=X.
I also know that some number L is true in this fashion (I am pretty sure of this, however X is still the square root.):
XL=X+P
X/L=X-Q
So I don't know L, but I can now do this to the above equation.
(XL)(X/L)=N
(You are probably tired of me saying the word "so", so many times, but so what.... lol, anyway...)
I am not sure how to multiply those numbers. I know it is XL over 1, so if that where true...
X2L is all over L, and the L cancels, so yes, it checks out.
Alright now, since I have (XL)(X/L)=N, how do I foil that out? Remember, I know X, and N.
Thanks!!!!
EDIT: Okay, so I thought of it some more. If L is greater than 1, and less then 2, that means that:
XL=X+P
X/L=X-Q
However, if L is greater than 0, but less than one, that means, (I think), that this is true:
XL=X-Q
X/L=X+P
Either way, what I was thinking, was to go through and guess the first number. EG, try this:
Guess 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9. Okay, so obviously, one of those is going to be starting out as what the actual number is. (It would be 1.12753245253, or something like that.) I am not sure how to test it. Hm...
Okay, so I just tested 1.1 - 1.9, with the factors of 2 and 4.5 to get 9. The square root of 9 is 3. So L is 1.5 in this case. When I tested them, I got this:
1.1 = 2.727272727272727 = 3.3 = 8.999999999999999
1.2 = 2.5 = 3.6 = 9
1.3 = 2.307692307692308 = 3.9 = 9.000000000000001
1.4 = 2.142857142857143 = 4.2 = 9
1.5 = 2 = 4.5 = 9
1.6 = 1.875 = 4.8 = 9
1.7 = 1.764705882352941 = 5.1 = 9
1.8 = 1.666666666666667 = 5.4 = 9.000000000000002
1.9 = 1.578947368421053 = 5.7 = 9.000000000000002
Columns separated by the "=" sign.
The first column is the L. The second one is the 3/L. The third column is 3L. The fourth is (3L)(3/L). So I don't know how I would test that. Maybe if I could find another function of P and Q, or just L, this would be easier.
Last edited by Guest on 04 Sep 2009 08:42:14 pm; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 05 Sep 2009 01:35:28 pm Post subject: |
|
|
| ....what exactly are you trying to compute? Are you trying to find the square root of N? Or something different? |
|
| Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
| Posted: 05 Sep 2009 05:44:13 pm Post subject: |
|
|
DarkerLine wrote: ....what exactly are you trying to compute? Are you trying to find the square root of N? Or something different?
I know that x2=N.
I want to solve for L so that N mod XL=0. |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 05 Sep 2009 06:20:10 pm Post subject: |
|
|
| L=X works. So does L=X/K for any integer K. Although usually you don't talk about mods unless the things being modded are integers, in which case you'd add additional restrictions depending on what you're interested in (e.g. if all you care about is XL being an integer, then try all divisors D of N, which can be expressed as XL where L=D/X). |
|
| Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
| Posted: 05 Sep 2009 06:47:55 pm Post subject: |
|
|
it's rsa. There are only 2 divisors D.
How can I solve for it, and not guess?
(starts googling) |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 05 Sep 2009 08:13:07 pm Post subject: |
|
|
If you knew the first thing about RSA, you'd know that it's not meant to be factored. That's why so much security depends on it. Beyond brute force (which is futile), I don't even know how it's ever accomplished, to be honest. See: One-Way Function
Last edited by Guest on 05 Sep 2009 08:17:43 pm; edited 1 time in total |
|
| Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009
Posts: 360
|
| Posted: 05 Sep 2009 10:07:27 pm Post subject: |
|
|
| True, but I believe it's factorable. We shall see. I just graphed a mod problem, and think I have a good idea how to solve it. |
|
| Back to top |
|
|
|
Math and Science => Technology & Calculator Open Topic
