## Polynomials: I’ve just made a text-based UI, slightly user-friendlier.

One of the facts which I’ve written about before was, that I had written a C++ program which finds numerical approximations to the roots of polynomials, preferably difficult polynomials to which there can be no exact solution. And one of the facts about my program, which I was never completely satisfied with, had less to do with the actual algorithm that gets closer and closer to each root, but has more to do with how my code could be inaccessible to those readers, who do not already know how to use a compiler.

Specifically, I had written a version of the program which somebody executes from ‘the Command Prompt’, as it’s called under Windows, because under Linux, power-users access features with one-line commands often. Yet, if a user was not such a power-user, then what they might do under Windows could be, just to double-click on the .EXE-File (the Application icon), observe that a console window briefly appears, and then watch it disappear again. There could be users who do not know how to navigate their Command Prompt windows to the folder into which they unzipped the program, and then execute that program from within their Command Prompt / Terminal Window.

And so, even though I kept the code roughly the same – it’s still text-based – I changed it subtly, to help out potential readers who may have had that problem. You may try it and see if you like it. The compressed files can be found at the following location:

https://dirkmittler.homeip.net/binaries/

And, within the table of contents which gets displayed there, the reader would either be interested in the file ‘Roots_Dirk_Mittler.tar.gz‘, or the file ‘Roots_Dirk_Mittler.zip‘ – in either case, the file-name that begins with a single ‘R’.

Enjoy,

Dirk

## A Basic Weakness, in my Polynomial Roots Finder (Resolved).

One of the subjects which I’ve written about often is that, in the past, I wrote a program which approximates the roots of polynomials, and more recently, that I wrote a version of the same program, that has a (Qt5-based) GUI – a Graphical User Interface. AFAICT, both versions of the program seem to work fine. The GUI version additionally displays a plot of the polynomial.

Note: Polynomials of a degree greater than 4 generally don’t have exact, algebraic solutions – with some exceptions – so that their roots are usually best found by numerical approximation.

Because I’ve published all the recent versions of this program on my blog, I also retest it thoroughly, with polynomials that I know will give it some difficulty each time. And what I have found was that presently, the simplified plotting window has a behaviour that is not false, but that may be difficult for the user to understand. This is less than ideal, because the purpose of that plotting window is, to make the polynomial which the user entered easier to understand, and not harder.

The problem manifests, if the user enters a polynomial that has exactly one root, or that has the same root with some multiplicity. In that situation, my plotting window will assume that the interval on the X-axis to be displayed, deviates from that root by ±0.25, which is also the smallest interval its internal logic allows it to display. While what it displays is not wrong, the very narrow range can make it hard to read:

Here, I’ve used an established Computer Algebra System, to construct a polynomial that has a root of (0.5), with a multiplicity of 8. It’s a polynomial of the 8th degree. Its behaviour near (x=0.5) is the same as what the behaviour would be, of x8, near (x=0.0). In other words, the Y-values never get big, because, to raise some small fraction (x <= 0.25) to the power of 8, will always produce some even-smaller fraction.

But what the plot does non-ideally, is, to centre at (x=0.5) in this case, and only to cover the interval from (x=-0.25) to (x=0.75), as described above. The user must then read from the bottom of the plotting window, that the X-Tick-Interval is only (0.05), and must recognize that the plot is indeed centred at (x=0.5), 4 ticks after the labelled tick at (x=0.3). In this example, it’s easier to read the text-form of the solution.

The reason why my program does this, is the fact that its auto-determined interval spans the range of roots, adds some small fraction to that positively and negatively, but that in this case the spread between the roots is zero, because there is only one. And, I refuse to make the minimum span ±1.0, because some polynomials may in fact have roots closer together than that, which might also need to be plotted…

This program can be found at the following repository on my site:

https://dirkmittler.homeip.net/binaries/

The source code can be found in the files:

• Dirk_Roots_GUI_1.tar.gz
• Dirk_Roots_GUI_1.zip

And an AppImage can be found in the file:

• Dirk_Roots_GUI_1-x86_64.AppImage

(Updated 9/04/2020, 15h40… )

## I have now created a GUI version of my polynomial roots approximation program.

One of the facts which I had blogged about some time ago, was that I had developed a program that approximates the roots of polynomials, the intention being that it be used on polynomials of a very high degree, by entirely numerical means. And I did this with the knowledge that polynomials with a degree greater than 4 have no exact, analytical solutions, except for certain special cases.

I think that maybe, one reason why some readers were disinterested in that program, could have been the fact that it was entirely command-line driven. So, what I have now done was,

• To convert the core program into a truly object-oriented format, so that it could act as a module within some other program, and no longer have its own ‘main()’ function, And
• Applied what I’ve taught myself about the Qt5 GUI Library, to design a minimalistic GUI for it…
• One of the things the GUI now does, in addition to just listing the roots as text, is also to provide a rudimentary plot of the polynomial each time.
• One thing which the GUI version can no longer do, is to accept complex coefficients from the user. The command-line version was able to do that. But the GUI version can still find all the complex roots, given some luck.

The AppImage can be found at this repository on my site:

https://dirkmittler.homeip.net/binaries/

The relevant file is named ‘Dirk_Roots_GUI_1-x86_64.AppImage‘. It will only run under Linux, unfortunately.

Dirk

## One weakness of my algorithm, regarding polynomials.

Several months ago, I wrote a C++ program (with C coding-style) that computes numerical approximations, of the roots of an arbitrary polynomial. Even though I changed the code slightly since March, mainly to improve the chances that it will compile on other people’s computers, the basic algorithm hasn’t changed. Yet, because I wrote the algorithm, I know that it has certain weaknesses, and I’m about to divulge one of those…

The main search algorithm isn’t able to determine whether (x) is sufficiently close to a root. It’s really only able to determine whether (y) is sufficiently close to zero. And so an idea that an implementer could have about this would be, to name the maximum allowable error in (x) ‘epsilon’, to compute the derivative of the polynomial for the given value of (x), and then to multiply ‘epsilon’ by this derivative, perhaps naming the derived, allowable error in (y) ‘epsilond’. But I consciously chose not to go that route because:

• Computing the real derivative of the polynomial each time, though certainly doable, would have made my code complex beyond what I was willing to tolerate,
• Even had I done so, certain polynomials will have a uselessly low derivative near one of their roots. This can happen because of a doubled root, or simply because of two roots that are too close together. ‘epsilon’ is as small as what would be practical, given the number of bits the variables have to work with, that were, a 52-bit significand.

So my program, instead, computes a ‘notional derivative’ of the polynomial, near (x), that is really just the derivative of the highest exponent by itself. This little detail could actually make it difficult for some observers to understand my code. At the same time, my program limits the lower extent of this derivative, to an arbitrary, modest fraction, just so that (x) won’t need to be impossibly precise, just to satisfy the computation of how precise (y) would need to be.

But then, a predictable problem becomes, that the real derivative of a given polynomial might be much smaller than just, the derivative of this highest exponent. And if it is, then satisfying … for (y) will no longer satisfy … for (x).

The following output illustrates an example of this behaviour:


"Maxima" Preparation:

(%i1) expand((x-100)*(x-101)*(x-102));
(%o1) x^3-303*x^2+30602*x-1030200

(%i2) expand((x-100)*(x-110)*(x-120));
(%o2) x^3-330*x^2+36200*x-1320000

(%i3) expand((x-100)*(x-101));
(%o3) x^2-201*x+10100

Approximations from Program:

dirk@Phosphene:~$poly_solve 1 -303 30602 -1030200 101.00000000013 + 0I 99.999999999938 + 0I 101.99999999993 + 0I dirk@Phosphene:~$ poly_solve 1 -330 36200 -1320000

100  +  0I
110  +  0I
120  +  0I

dirk@Phosphene:~$poly_solve 1 -201 10100 100 + 0I 101 + 0I dirk@Phosphene:~$




(Updated 9/22/2019, 5h40 … )