mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2019-11-12, 20:32   #1
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23·3·5·11 Posts
Default Calculator that can factor and find exact roots of polynomials

Hello folks,

I have uploaded to https://www.alpertron.com.ar/POLFACT.HTM 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.
alpertron is offline   Reply With Quote
Old 2019-11-12, 21:22   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1138910 Posts
Default

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.
ewmayer is online now   Reply With Quote
Old 2019-11-12, 21:31   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

132010 Posts
Default

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
I do not have that NoScript plugin.
alpertron is offline   Reply With Quote
Old 2019-11-12, 22:11   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

261758 Posts
Default

Quote:
Originally Posted by alpertron View Post
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
I do not have that NoScript plugin.
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?
ewmayer is online now   Reply With Quote
Old 2019-11-12, 22:16   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101001010002 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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?
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.

Last fiddled with by alpertron on 2019-11-12 at 22:24
alpertron is offline   Reply With Quote
Old 2019-11-13, 11:32   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23×3×5×11 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2019-11-13, 17:02   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

CF916 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2019-11-13, 20:13   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

7×1,627 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
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.
ewmayer is online now   Reply With Quote
Old 2019-11-13, 20:15   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23×3×5×11 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
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 is offline   Reply With Quote
Old 2019-11-13, 20:17   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23×3×5×11 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
Those old browsers do not support WebAssembly. This was added on Firefox version 52, dated March 7, 2017.
alpertron is offline   Reply With Quote
Old 2019-11-13, 22:48   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

34×41 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
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 casus irreducibilis of the cubic.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where can I find a arbitrary precision Calculator online that can handle this # ONeil Information & Answers 9 2018-04-17 18:18
On polynomials without roots modulo small p fivemack Computer Science & Computational Number Theory 2 2015-09-18 12:54
How to find values of polynomials with nice factorization? Drdmitry Computer Science & Computational Number Theory 18 2015-09-10 12:23
How much ECM does it take to find a given factor? geoff Factoring 5 2004-09-29 20:14
How large a factor can P-1 testing find ? dsouza123 Software 3 2003-12-11 00:48

All times are UTC. The time now is 22:41.

Wed Aug 5 22:41:21 UTC 2020 up 19 days, 18:28, 2 users, load averages: 1.32, 1.63, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.