mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Programming (https://www.mersenneforum.org/forumdisplay.php?f=29)
-   -   Calculator that can factor and find exact roots of polynomials (https://www.mersenneforum.org/showthread.php?t=24932)

 alpertron 2019-11-12 20:32

Calculator that can factor and find exact roots of polynomials

Hello folks,

I have uploaded to [url]https://www.alpertron.com.ar/POLFACT.HTM[/url] a calculator that can factor polynomials over the integers or modulo a power of a prime. It also can find exact roots of polynomials expressed with radical expressions.

At this moment the roots are shown only if the degree of the irreducible factor of the input polynomial is <= 5. It also indicates when the quintic equation cannot be expressed as radical expressions.

Please let me know if there is any error.

 ewmayer 2019-11-12 21:22

I opened a new tab in my FF session, went to your page, enabled JS in NoScript, and, with a view toward poly-factoring x^4-1 as a little test, entered 4-1 and clicked 'factor'. I notice that whether I click 'evaluate' or 'factor', both those buttons go gray together, and "Factoring polynomial..." appears. Waited a full minute before killing it ... no result.

 alpertron 2019-11-12 21:31

I started Firefox 70.0.1 on Windows 10, entered .4-1 so it showed x^4-1 in the polynomial box, then I pressed the Factor button. The output with Pretty Print disabled is:

[CODE]
x^4 − 1

Irreducible polynomial factors:

x − 1
x + 1
x^2 + 1

Roots:

x1 = 1
x2 = -1
x3 = - 1 *i
x4 = 1 *i

Time elapsed: 0d 0h 0m 0.0s
[/CODE]

I do not have that NoScript plugin.

 ewmayer 2019-11-12 22:11

[QUOTE=alpertron;530400]I started Firefox 70.0.1 on Windows 10, entered .4-1 so it showed x^4-1 in the polynomial box, then I pressed the Factor button. The output with Pretty Print disabled is:

[CODE]
x^4 − 1

Irreducible polynomial factors:

x − 1
x + 1
x^2 + 1

Roots:

x1 = 1
x2 = -1
x3 = - 1 *i
x4 = 1 *i

Time elapsed: 0d 0h 0m 0.0s
[/CODE]

I do not have that NoScript plugin.[/QUOTE]

Part of it is that missing leading . in my input - suggest you add some kind of basic user-input parsing which indicates unrecognized input format, and only activates the buttons when the input is 'legal'. I retried with .4-1, it indeed auto-filled x^4-1 in the entry field, but clicking 'factor' still gives same as before, both 'evaluate' and 'factor' widgets go gray, and things hang until I click 'stop'. This is FF on Mac - I suspect you have some Windows-only stuff going on in your JS. Do you have ready access to a non-Win machine?

 alpertron 2019-11-12 22:16

[QUOTE=ewmayer;530403]Part of it is that missing leading . in my input - suggest you add some kind of basic user-input parsing which indicates unrecognized input format, and only activates the buttons when the input is 'legal'. I retried with .4-1, it indeed auto-filled x^4-1 in the entry field, but clicking 'factor' still gives same as before, both 'evaluate' and 'factor' widgets go gray, and things hang until I click 'stop'. This is FF on Mac - I suspect you have some Windows-only stuff going on in your JS. Do you have ready access to a non-Win machine?[/QUOTE]
The problem is that 4-1 is legal, because the parser converts that to 3. You can enter any polynomial expression, as explained in the help that you can read by expanding the "accordions". The trick using the dot (coefficient dot exponent) is optional and it makes a lot faster to enter the polynomials especially in mobile devices.

With respect to the second part, my code does not know what operating system is running. It uses Javascript and WebAssembly. Maybe you have not enabled WebAssembly in your plugin.

 alpertron 2019-11-13 11:32

I installed the NoScript extension to Firefox on Windows 10, and the Javascript was disabled when I loaded the calculator. After selecting "Temp TRUSTED" for my Web site, it worked OK and I could see the responses from the application.

 Dr Sardonicus 2019-11-13 17:02

I tried the minimum polynomial for $$2\cos(\frac{2\pi}{11})$$,

x^5 + x^4 - 4*x^3 - 3*x^2 + 3*x+ 1

and the answer was a bit hard to read. I'm not sure whether it was right.

 ewmayer 2019-11-13 20:13

[QUOTE=alpertron;530448]I installed the NoScript extension to Firefox on Windows 10, and the Javascript was disabled when I loaded the calculator. After selecting "Temp TRUSTED" for my Web site, it worked OK and I could see the responses from the application.[/QUOTE]

Exactly what I did using both FF and PaleMoon on my Mac. My next thought was that perhaps the versions of those browsers I'm running on that older legacy system (which has OS X frozen at 10.6.8 because my code-build flow is set up for that, and upgrading would break stuff) can't handle something in your JS, but retrying under Ubuntu 19 running on my Intel NUC, which is 4-5 years old gives the same failure. Oh, well.

 alpertron 2019-11-13 20:15

[QUOTE=Dr Sardonicus;530489]I tried the minimum polynomial for $$2\cos(\frac{2\pi}{11})$$,

x^5 + x^4 - 4*x^3 - 3*x^2 + 3*x+ 1

and the answer was a bit hard to read. I'm not sure whether it was right.[/QUOTE]

The answer shown by the application is wrong. I unchecked Pretty Print, copied the output to Notepad++, deleted all (xxx digits) and spaces, replaced i by I and finally copied that to gp. All five roots shown are non-real, so something is not good.

Another error is that the digits in group is not working. The program always shows groups of 6 digits.

I will work on that.

 alpertron 2019-11-13 20:17

[QUOTE=ewmayer;530508]Exactly what I did using both FF and PaleMoon on my Mac. My next thought was that perhaps the versions of those browsers I'm running on that older legacy system (which has OS X frozen at 10.6.8 because my code-build flow is set up for that, and upgrading would break stuff) can't handle something in your JS, but retrying under Ubuntu 19 running on my Intel NUC, which is 4-5 years old gives the same failure. Oh, well.[/QUOTE]
Those old browsers do not support WebAssembly. This was added on Firefox version 52, dated March 7, 2017.

 Dr Sardonicus 2019-11-13 22:48

[QUOTE=alpertron;530510]The answer shown by the application is wrong. I unchecked Pretty Print, copied the output to Notepad++, deleted all (xxx digits) and spaces, replaced i by I and finally copied that to gp. All five roots shown are non-real, so something is not good.

Another error is that the digits in group is not working. The program always shows groups of 6 digits.

I will work on that.[/QUOTE]I think that $$2\cos(\frac{2\pi}{11})$$ and its conjugates are about as good as it gets for expressing the roots of this polynomial. There is no expression in terms of "real radicals."

It is somewhat similar to the minimum polynomial x^3 - 3*x - 1 for $$2\cos(\frac{\pi}{3})$$, which the calculator expresses in terms of cosines. Obviously, it "knows" the trigonometric solution for the [i]casus irreducibilis[/i] of the cubic.

 alpertron 2019-11-15 02:40

I've fixed several errors, including the number of digits in groups, a fix on biquadratic equations, now it works on Web browsers that do not support WebAssembly and other minor errors.

With respect to the equation mentioned by Dr Sardonicus, I fixed a few errors, but the support from the application is incomplete when the Galois group has order 5. I will continue working on this.

 ewmayer 2019-11-15 20:13

Thanks, Dario! That works even on my old FF-for-Mac-OS-10.6.8.

Was it much work to remove the WebAs dependence? I always say, if you can gain a lot of portability without having to expend inordinate effort, it's worth doing. But then again, I'm an old-timer - I realize much of the New Economy is based on domain fragmentation, getting folks to pay multiple times for what is basically the same thing. :)

 alpertron 2019-11-15 21:07

[QUOTE=ewmayer;530692]Thanks, Dario! That works even on my old FF-for-Mac-OS-10.6.8.

Was it much work to remove the WebAs dependence? I always say, if you can gain a lot of portability without having to expend inordinate effort, it's worth doing. But then again, I'm an old-timer - I realize much of the New Economy is based on domain fragmentation, getting folks to pay multiple times for what is basically the same thing. :)[/QUOTE]

Thanks for testing. Actually, it detects whether the Web browser supports WebAssembly or not, so in the second case it uses asm.js (which is a subset of JavaScript that can be executed efficiently in the Web browser).

All my Web applications use WebAssembly because it runs 2 to 3 times faster than asm.js. This is important when you try to factor a big polynomial (or big number in [URL]https://www.alpertron.com.ar/ECM.HTM[/URL]).

 alpertron 2020-09-27 22:47

Hello folks,

I have added more features to this calculator at [url]https://www.alpertron.com.ar/POLFACT.HTM[/url]

Now it quickly factors integer polynomials with degree up to 1000 using Van Hoeij algorithm (which includes LLL), but notice that with some big polynomials it is possible to get an out of memory bounds so the factorization cannot complete.

Then it shows the roots of polynomials with degree up to 5 with radicals and trigonometric functions. Notice that the roots of most fifth-degree polynomials cannot be expressed with radicals or trigonometric functions. It also shows the roots of cyclotomic polynomials (x^n - 1 and their divisors) and polynomials of the form ax^n + b and ax^(2n) + bx + c.

For example, one of the roots of x^51 - 1 found by this calculator is:

x44 = cos(80*pi/51) + i * sin(80*pi/51) = -(1/32)*(-1+17^(1/2)-(34-2*17^(1/2))^(1/2)+2*(17+3*17^(1/2)+(170+38*17^(1/2))^(1/2))^(1/2)) + (1/16)*(3)^(1/2)*(34-2*17^(1/2)-2*(34-2*17^(1/2))^(1/2)+4*(17+3*17^(1/2)-(170+38*17^(1/2))^(1/2))^(1/2))^(1/2)-(i/32)*(3)^(1/2)*(-1+17^(1/2)-(34-2*17^(1/2))^(1/2)+2*(17+3*17^(1/2)+(170+38*17^(1/2))^(1/2))^(1/2))-(i/16)*(34-2*17^(1/2)-2*(34-2*17^(1/2))^(1/2)+4*(17+3*17^(1/2)-(170+38*17^(1/2))^(1/2))^(1/2))^(1/2)

I have also added compatibility with screen readers so more people can access it. I tested it with NVDA and Narrator on Windows and Talkback on Android.

Please let me know if you find some error.

 Dr Sardonicus 2020-09-29 16:02

[QUOTE=alpertron;558053]
Please let me know if you find some error.[/QUOTE]
Try factoring the polynomial x^5 - 5.

 alpertron 2020-09-30 02:53

The values found by the solver are correct as you can see by unsetting pretty print, and then factoring it again.

This is the output of the calculator.

[code]
R1 = 0
R2 = (15625)^(1/5)
R3 = 0
R4 = 0
S1 = (-1+5^(1/2))*(R1 + R4) + (-1-5^(1/2))*(R2 + R3)
S2 = (-1+5^(1/2))*(R2 + R3) + (-1-5^(1/2))*(R1 + R4)
T1 = (10 + 2 * 5^(1/2))^(1/2)*(R4 - R1) + (10 - 2 * 5^(1/2))^(1/2)*(R3 - R2)
T2 = (10 + 2 * 5^(1/2))^(1/2)*(R3 - R2) + (10 - 2 * 5^(1/2))^(1/2)*(R4 - R1)
x1 = (R1 + R2 + R3 + R4) / 5
x2 = (S1 + i * T1) / 20
x3 = (S1 - i * T1) / 20
x4 = (S2 + i * T2) / 20
x5 = (S2 - i * T2) / 20
[/code]

Using Pari, we get:

[code]
%1 = I
(23:47) gp > R1 = 0
%2 = 0
(23:47) gp > R2 = (15625)^(1/5)
%3 = 6.8986483073060741619503173210800884643
(23:47) gp > R3 = 0
%4 = 0
(23:47) gp > R4 = 0
%5 = 0
(23:47) gp > S1 = (-1+5^(1/2))*(R1 + R4) + (-1-5^(1/2))*(R2 + R3)
%6 = -22.324494875306315076216696369277540320
(23:47) gp > S2 = (-1+5^(1/2))*(R2 + R3) + (-1-5^(1/2))*(R1 + R4)
%7 = 8.5271982606941667523160617271173633913
<^(1/2))^(1/2)*(R4 - R1) + (10 - 2 * 5^(1/2))^(1/2)*(R3 - R2)
%8 = -16.219694943147773999539440789223925778
<^(1/2))^(1/2)*(R3 - R2) + (10 - 2 * 5^(1/2))^(1/2)*(R4 - R1)
%9 = -26.244017705167891715114016211195788877
(23:47) gp > x1 = (R1 + R2 + R3 + R4) / 5
%10 = 1.3797296614612148323900634642160176929
(23:47) gp > x2 = (S1 + i * T1) / 20
%11 = -1.1162247437653157538108348184638770160 - 0.81098474715738869997697203946119628889*I
(23:47) gp > x3 = (S1 - i * T1) / 20
%12 = -1.1162247437653157538108348184638770160 + 0.81098474715738869997697203946119628889*I
(23:47) gp > x4 = (S2 + i * T2) / 20
%13 = 0.42635991303470833761580308635586816957 - 1.3122008852583945857557008105597894439*I
(23:47) gp > x5 = (S2 - i * T2) / 20
%14 = 0.42635991303470833761580308635586816957 + 1.3122008852583945857557008105597894439*I
(23:47) gp > f(x)=x^5-5
%15 = (x)->x^5-5
(23:48) gp > f(%11)
%16 = -2.350988701644575016 E-38 + 4.701977403289150032 E-38*I
(23:48) gp > f(%12)
%17 = -2.350988701644575016 E-38 - 4.701977403289150032 E-38*I
(23:48) gp > f(%13)
%18 = 2.350988701644575016 E-38 - 2.938735877055718770 E-38*I
(23:48) gp > f(%14)
%19 = 2.350988701644575016 E-38 + 2.938735877055718770 E-38*I
(23:48) gp > f(%10)
%20 = 4.701977403289150032 E-38
[/code]

It is clear the some optimization is required in the program to delete the extra zeros so the output is reduced.

 alpertron 2020-09-30 03:40

Now the response of the Web application is shorter for polynomials of the form x[sup]5[/sup]+n (n = integer).

 Dr Sardonicus 2020-10-01 12:39

[QUOTE=alpertron;558301]The values found by the solver are correct as you can see by unsetting pretty print, and then factoring it again.
<snip>
It is clear the some optimization is required in the program to delete the extra zeros so the output is reduced.[/QUOTE]
My mistake, I was merely having trouble reading the output. New version with sine/cosine renderings of roots of unity is much easier on my dim old eyes, thanks!

 jwaltos 2020-10-01 12:59

[QUOTE=alpertron;558312]Now the response of the Web application is shorter for polynomials of the form x[sup]5[/sup]+n (n = integer).[/QUOTE]

Cheers.

 R. Gerbicz 2020-10-01 15:24

[QUOTE=alpertron;558053]I have added more features to this calculator at [url]https://www.alpertron.com.ar/POLFACT.HTM[/url]

Now it quickly factors integer polynomials with degree up to 1000 using Van Hoeij algorithm (which includes LLL), but notice that with some big polynomials it is possible to get an out of memory bounds so the factorization cannot complete.

..

Please let me know if you find some error.[/QUOTE]

There is a bug even in the polynom evaluation part, try for: x*(x+1)-(x+1)
it shows:
−1
Clearly wrong.

 alpertron 2020-10-01 18:32

[QUOTE=R. Gerbicz;558495]There is a bug even in the polynom evaluation part, try for: x*(x+1)-(x+1)
it shows:
−1
Clearly wrong.[/QUOTE]
I've just fixed this error. Please refresh the page so the Web page is dated 1 October 2020 and try again.

 R. Gerbicz 2020-10-01 20:46

Thanks. More examples:
polynom: x^5 - 1615*x^4 + 861790*x^3 - 174419170*x^2 + 14998420705*x - 465948627343

Irreducible polynomial factors
The 4 factors are:
x − 653
(x − 103)2
x2 − 756⁢x + 67259
Roots
The 5 roots are:
x1 = 653
x2 = x3 = 103
x4 = 103
x5 = 653

What is wrong x2-756+67259 is reducible. The correct answer should be as the roots are displayed:
(x-653)^2*(x-103)^3 . But you haven't grouped even correctly the roots in that section.

For evaluation part:

polynom: (x+1)/x*(x+1)
x + 1

This is wrong.

polynom: x/2*2

This could be still ok, if you require that all subresults should be in Z[x].

 alpertron 2020-10-02 01:18

[QUOTE=R. Gerbicz;558540]Thanks. More examples:
polynom: x^5 - 1615*x^4 + 861790*x^3 - 174419170*x^2 + 14998420705*x - 465948627343

Irreducible polynomial factors
The 4 factors are:
x − 653
(x − 103)2
x2 − 756⁢x + 67259
Roots
The 5 roots are:
x1 = 653
x2 = x3 = 103
x4 = 103
x5 = 653

What is wrong x2-756+67259 is reducible. The correct answer should be as the roots are displayed:
(x-653)^2*(x-103)^3 . But you haven't grouped even correctly the roots in that section.
[/QUOTE]
I fixed this error. Please refresh the page and retry.

[QUOTE]For evaluation part:

polynom: (x+1)/x*(x+1)
x + 1

This is wrong.

[/QUOTE]
Since the application works with integer polynomials, the slash operator performs the division disregarding the remainder.

This means that when you enter (x+1)/x*(x+1), parsing left to right, the program calculates (x+1)/x = 1 (the remainder 1 of the polynomial division is discarded) and then the program multiplies the previous result 1 by x+1, so the result is x+1.

[QUOTE]polynom: x/2*2

This could be still ok, if you require that all subresults should be in Z[x].[/QUOTE]
Again, the expression is parsed from left to right, and x/2 is not an integer polynomial, so it shows the error.

 R. Gerbicz 2020-10-02 16:23

OK, more inputs:

(3*x^2)/(2*x+1)
3x2

Clearly wrong. Following your way it would mean that 3*x^2=(2*x+1)*3*x^2+R(x) and in this case the remainder would be 3rd degree? Meaningless.

x^5 - 4161938199135571*x^4 + 6750425908270471236962285227630*x^3 - 5309242550166291213723686988859597734543042314*x^2 + 2016699400841707878060752590276325131391118358776183137438993*x - 295975920745818133920126480489914719398004640082403818556796416884133107491

Irreducible polynomial factors
The polynomial is irreducible

Roots
The 5 roots are:
The quintic equation cannot be expressed with radicands.

Wrong, because p(x)=(x-505340926559057)^2*(x-1050418782005819)^3

Other such polynoms where you find the roots but display the wrong factors and grouping problems:
x^5 - 569676319*x^4 + 105098371422759466*x^3 - 7011576352652045449773950*x^2 + 195375348220798308339573946630661*x - 1952243687462206905824707435700917386803

and

x^5 - 2876590967309*x^4 + 3229067054667107663190970*x^3 - 1768676572192568691887072530348224746*x^2 + 473795689206607977454622626698064450356613773013*x - 49793205560537089066888851381785438595315265096906181547929

 alpertron 2020-10-02 19:42

All these examples are working now. Thanks for finding the errors.

Please refresh the page to get the current version.

 alpertron 2020-10-04 21:20

When the irreducible polynomial has degree >= 5, now my code performs the factorization of this polynomials with prime modulus up to 100.

If the conditions of Keith Conrad's paper that you can read at [url]https://kconrad.math.uconn.edu/blurbs/galoistheory/galoisSnAn.pdf[/url] are true, the Galois group is A[sub]n[/sub] or S[sub]n[/sub], so my application indicates that the roots of the polynomial cannot be expressed as radical expressions along with the conditions found.

Example of new output from [url]https://www.alpertron.com.ar/POLFACT.HTM[/url]

x[SUP]12[/SUP] + 45⁢x[SUP]7[/SUP] − 23

Irreducible polynomial factors
The polynomial is irreducible

Roots
The 12 roots are:
x1 to x12 : The roots of the polynomial cannot be expressed by radicals. The degrees of the factors of polynomial modulo 7 are 1, 2 and 9 (the Galois group contains a cycle of length 2) and the degrees of the factors of polynomial modulo 17 are 1 and 11 (the Galois group contains a cycle of prime length greater than half the degree of polynomial)

 alpertron 2020-11-28 23:13

I fixed the LLL routine and optimized the Hensel Lifting. Now the factorization of polynomials of degree less than 1000 with small coefficients can be done in seconds.

 All times are UTC. The time now is 23:34.