I am designing a software that has to find the roots of polynomials. I have to write this software from scratch as opposed to using an already existing library due to company instructions. I currently know three main methods of finding roots: the Secant method, the Newton-Raphson method and the Interval Bisection method. I will need to implement the most efficient one of these algorithms in my software, so could someone please let me know how these methods compare in terms of speed? Or if anyone knows any different methods that could potentially be more efficient the three mentioned above, could they please mention them too? Thanks.  It is currently my understanding that the Interval-Bisection method is slower than the Newton-Raphson one. However, I also know that the Newton-Raphson method does not always reach the correct answer due to asymptotes. In regards to this, would it be more efficient to mix two, or more, algorithms, for example, loop through the Newton-Raphson method for a set number of times and then switch to the slower Interval Bisection method after that in case the Newton-Raphson method never reaches an answer? If this is the case, which algorithms would be the most efficient to implement together? I do not currently know how the Secant method compares to the other two in terms of efficiency, so any insight on that would be appreciated too.  Thanks very much for your time.  Update  I would be using these methods to find the Internal Rate of Return (IRR). Therefore, I would not necessarily need to find the complex roots as I will be dealing with finance. However, it could be a very large polynomial depending on how many payments there are.
120598
I have built a program that prices financial assets and it does this in part by calculating the IRR. The problem is that it does not run as quickly as I would like it to.   I currently use the Newton-Raphson method of calculating roots of equations, but then switch to the Interval Bisection method after a set number of tries. This is because there is a chance that the Newton-Raphson method cannot find the IRR, for instance, due to asymptotes. My understanding is that the Newton-Raphson method is more efficient for the cases that it actually works with, which is why my system is currently set up like this.  Is there a more efficient formula or algorithm that I can use to calculate the IRR of a financial asset than the ones that I am currently employing? Or, if there is none, is there a way I can change my current order of calculations to make it more efficient?  If you are in need of any of the formulas that I use to actually be written in this question, please let me know. Thank you for your time.  Update  The pricing software that I have designed is a PHP extension written in the C language. This is because it is a web based program. I cannot change languages due to reasons to do with the company that I work for. I didn't mention the languages before as I didn't think that they were too important due to the fact that I was looking for an increase in mathematical efficiency, not computational.  Also, someone has brought to my attention the fact that the Secant method could also be used in the place of the Interval Bisection one or the Newton-Raphson one. Can anyone tell me how the Secant method compares to the other two in regards to efficiency?
117972
I am struggling to use the Euclidean algorithm for polynomials.  Given something like $$GCD(x^5+1, x^3+1)$$  I can easily use it as follows:   $$x^5+1 = x^2(x^3+1) -x^2 +1 \\ x^3+1 = -x(-x^2+1) + x +1 \\ -x^2+1 = (x+1)(-x+1)$$  GCD = x+1  But for something like $$GCD(2x^2+6x+3, 2x+1)$$   I cannot figure out how to do it using the same method. I start like this:  $$2x^2+6x+3 = x(2x+1) + 5x+3\\ 2x+1 = \frac{2}{5}(5x+3) - \frac{1}{5}\\$$  and I am not sure how to continue. Any help would be appreciated, sorry for my poor attempt at using LaTeX.
108087
I would like an efficient algorithm for square root of a positive integer.  Is there a reference that compares various square root algorithms?  Thanks.
49691
I have this problem: given $N$,  $1 \leq N\leq 100$ integers which are roots from a polynomial, calculate the sum of coefficients from that polynomial  for example: given $3$ integers $2$, $2$ and $3$, I can calculate the polynomial $$x^3 - 7x^2 +16x -12,$$ so the sum of coefficients is $-2$  but if I have $100$ integers, I think calculating the polynomial will be enormous, so is there some way to find this sum of coefficients?
49190
Find the minimal polynomial for $\sqrt[3]{2} + \sqrt[3]{4}$ over $\mathbb{Q}$  I havent covered galois theory, this is an exercise from the chapter algebraic extensions in gallian.  I can see that $\sqrt[3]{2} + \sqrt[3]{4}$ $\in \mathbb{Q}(2^{1/3})$, after this I am clueless.  Need hints will finish the proof.
35415
I've googled this and I've seen different types of proofs but they all use notations that I don't understand.  But first of all, I need to understand what quadratic convergence means, I read that it has to   do with the speed of an algorithm. Is this correct?  Ok, so I know that this is the Newton-Raphson method:  $$x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$$  How do I prove that it converges?  Thanks.
16179
Is there a division algorithm for polynomials in R[x], where R is a commutative ring with unity?    All the algebra books I read mention division algorithm for polynomials in F[x], where F is a field. Since the leading coefficient of a non zero polynomial in R[x] is not necessarily invertible, I find it difficult to proceed the same way we do for polynomials in F[x].  Can I get some help?
90684
Question  What is the minimum possible value of $a^{2}+b^{2}$ so that the polynomial $x^{4}+ax^{3}+bx^{2}+ax+1=0$ has at least 1 root?  Attempt  I divided by $x^{2}$ and got $$x^{2}+\frac{1}{x^{2}}+2+a\left(x+\frac{1}{x}\right)+b-2=0$$ by letting $$x+\frac{1}{x}=X$$ the equation becomes: $$X^{2}+aX+(b-2)=0$$ $$\therefore X=\frac{-a\pm \sqrt{a^{2}-4b+8}}{2}$$ but I am not sure how to continue. If the polynomial has 1 root doesn't that is should be a double root? Are we counting multiplicity or not?
24508
What would be the most optimal algorithm (performance-wise) to calculate the number of divisors of a given number?  It'll be great if you could provide pseudocode or a link to some example.  EDIT: All the answers have been very helpful, thank you. I'm implementing the Sieve of Atkin and then I'm going to use something similar to what Jonathan Leffler indicated. The link posted by Justin Bozonier has further information on what I wanted.
92917
I need to prove that the roots $\in \Bbb R$ of $x^3+x+1=0$ aren't rational. Obviously, it's easy to use the rational root theorem to prove that there are not rational solutions to this equation, but i want a different approach. I saw a similar question here, but it didn't provide my "solution".  My try  $x^3+x+1=0$  $x^3+x=-1$  $x(x^2+1)=-1$  Here we have two options (product of two numbers to obtain a negative):  $1.$ $x \gt 0$ $∧$ $x^2+1 \lt 0$ (not possible in $\Bbb R)$  $2.$ $x \lt 0$ $∧$  $x^2+1 \gt 0$   So, we use $2.$ to prove that $x \ne 0$, then:  $x(x^2+1)=-1$  $x^2+1=\frac{-1}{x}$  $x^2=\frac{-1}{x}-1$  $x^2=-(\frac{x+1}{x})$  $x=\pm \sqrt {-(\frac{x+1}{x})}$  Then, $\frac{x+1}{x} \ge 0$ because $x \lt 0$ (the equality occurs when $x=-1$, but this doesn't satisfy the original polynomial equation) but here i'm missing the cases $-1 \lt x \lt 0$ (i don't know how to use this to prove that the root is irrational)  This implies that $2$ of the roots are complex, but there are $3$ roots to a third degree polynomial equation.  And here i'm stuck, because i don't know how to prove that the last solution is irrational.  Any hints?  Is there anyway to prove that the last root is irrational?  Is my proof good so far?
9624
The polynomial $f(x) = x^3 -3x + 1$  is irreducible, and I'm trying to find the splitting field of the polynomial.  We've been given the hint by our lecturer to allow an arbitrary $\alpha$ to be a root and then to check that $\alpha$ is a root, then $2-\alpha^2$ is also root. I've done this with no problem.  My issue is since this is a polynomial of degree $3$, there must be another root that is somehow related to $\alpha$ so that I can create the splitting field and in turn the Galois group of my polynomial but I have no idea what this last root could be.
77029
I got this $$ f=a(x-1)(x-2)...(x-101) $$ knowing a and that $1 ,2 \ldots ,101$ are it's roots ... I need the roots of $f'$ , how should I do it ? More specifc how can I derivate a polynomial like that, is there a formula or something ?
86844
What are the roots of $$f(x) = x^a - a^x$$ for real $a &gt; 0$?   Case 1: For $0 &lt; a &lt; 1$ there is 1 solution, $x=a$. Case 2: For $1\le a &lt; e$ there are 2 solutions: $x=a$ and $[x&gt;a]$. Case 3: For $a &gt; e$ there are 2 solutions: $x=a$ and $[x &lt; a]$.     if we let b = a^(1/a). x = b^^ [use mathematica for tetration] or using the basic operators,  x = b^(b^(b^...))...) for a > e, this solves for the non-simple root &lt; a  but for a &lt; e it solves for  x = a i am looking for a similar solution for a &lt; e
62163
Different publications provide different equations for Newton's method or the Newton-Raphson method. In Giudici, P., Givens, G. H., &amp; Mallick, B. K. (2013). Wiley Series in Computational Statistics. Wiley Online Library, p. 26 the updating equation is given as $$ x^{(t+1)}=x^{(t)}-\frac{g^{\prime}\left(x^{(t)}\right)}{g^{\prime \prime}\left(x^{(t)}\right)} $$ whereas elsewhere on the internet (), it is given as $$ x^{(t+1)}=x^{(t)}-\frac{g\left(x^{(t)}\right)}{g^{\prime}\left(x^{(t)}\right)} $$ Are these equivalent? How can I make sense of the difference?
39841
How to use the  method?  Say I want to find number of combinations I can get with $x_1+x_2+x_3+x_4=22$,  where $x_i\in\mathbb{N}$.  Is this the correct time to apply the method?  This is being repurposed in an effort to cut down on duplicates, see here:     and here:
5520
I was asked to find the no. of ways to get from (0,0) to (8,8) with the 4 points of the shaded box unpassable, aka I can't use the 4 points namely (3,3)(4,4)(3,4)(4,3) while on my way to (8,8). Right and up movements.  I know it is something like a pascal triangle and worked out the solution of 4050 ways.  May I know if there are any faster means using permutation formula?  Thank you in advance.
58820
I'm having trouble with the procedure to find an inverse of a polynomial in a field. For example, take:     In $\frac{\mathbb{Z}_3[x]}{m(x)}$, where $m(x) = x^3 + 2x +1$, find the inverse of $x^2 + 1$.   My understanding is that one needs to use the (Extended?) Euclidean Algorithm and Bezout's Identity. Here's what I currently have:  Proceeding with Euclid's algorithm:  $$ x^3 + 2x + 1  =(x^2 + 1)(x) + (x + 1) \\\\   x^2 + 1 = (x + 1)(2 + x) + 2$$  We stop here because 2 is invertible in $\mathbb{Z}_3[x]$. We rewrite it using a congruence:  $$(x+1)(2+x) \equiv 2 \mod{(x^2+1)}$$  I don't understand the high level concepts sufficiently well and I'm lost from here. Thoughts?  Wikipedia has a page on this we a , but it's still not clear in my mind.  Note that  has almost the same title, but it's a level of abstraction higher. It doesn't help me, as I don't understand the basic concepts.  Thanks.