newRPL - build 1255 released! [updated to 1299]

[The Shadow]

Thank you so much for not including the unit as a factor! That has always frustrated me in OldRPL. Not factoring negative numbers is an acceptable compromise.

I personally would have preferred two lists (of prime factors and their exponents) and then the unit, but this is more compatible with old programs.

Either the polynomial factoring isn't working right or I'm not understanding it, though. First I tried 'X^2-2*X+1' and it said it wanted a vector of numbers. So I tried [1 -2 1]... And got [1 0 -1 2] as a response, which I can't make heads nor tails of.

[Claudio L.]

Devel ROM at hpgcc3.org was updated to 1090.

Not factoring negatives is NOT an acceptable compromise, try it now.

Regarding FACTORS: The polynomials are not accepted yet in symbolic form, more symbolic work will come in the future. As you correctly guessed (since it's not documented) you can provide polynomials the same way you do for all other polynomial functions. The answer you got is a BUG, fixed in 1090, that happened for roots with multiplicity.
Now it should provide the correct answer, in the same form as for real numbers: a pair of numbers representing the factor A and multiplicity N in (x+A)^N

Thanks for testing and reporting!

[Claudio L.]

ROMs updated to 1092 now.

I added a ROOT command with a bisection root finder. Arguments are similar to NUMINT (a function, an interval and a tolerance), it returns a root, or it throws an error "No root found".

The algorithm is a bisection with some improvements (heavily inspired on Namir's posts, thanks!!) that reduce the number of evaluation roughly by 30%.
Next I'll implement Brent and compare them, if it is really faster I'll switch to Brent, otherwise I like simpler methods.
I'm planning to introduce a new command CROOT using Muller, to be able to get complex roots as well. Since complex roots are not so commonly used, I think it's best to have a faster algorithm for real roots, then only if the user needs complex roots he can choose to use the slower algorithm.

As usual, keep testing and report any issues.

[The Shadow]

Okay, so FACTORS now makes the first prime factor negative if the original number was negative. I assume this is just a marker, because otherwise it's flat-out wrong. (ie, it says that -180 factors as (-2)^2*3^2*5.)

Of course, this means that -1, 1, and 0 have the same factorization! Since they have no prime factors at all.

Two possible options:

1) Bite the bullet and give two outputs, one the list and the other of the unit. So -180 would give:

{ 2 2 3 2 5 1 }
-1,

and -1 would give:

{ }
-1

2) Or, go all OldRPL and include the unit, but be consistent and do it every time, not just for negatives. So +180 would give:

{ 1 1 2 2 3 2 5 1 }

I dislike this option but if it's always there it's much easier to manage. Likewise, the factorization of 0 would be:

{ 0 1 }

(EDIT: There's also option 3: Once tagged objects are in, tag the list of factors with the unit.)

FACTORS also chokes on some non-integer inputs without throwing an error. For example, 1.5 gives:

{ 1.5 1 -1 0 }

which is more than a little odd. Other times it seems to round off first. OldRPL would actually factor rational numbers, so 1.5 (well, '3/2', but the difference isn't as important in NewRPL) would give:

{ 2 -1 3 1 }

which strikes me as much more desirable.

The polynomial factorization is still a little odd. It throws an error when the polynomial has complex roots, but still manages to calculate them. I think it's more sensible to have a flag to just not break up factors irreducible in the reals. Of course, this gives headaches in the output syntax, as the vector notation breaks down. You'd need something like this for [1 0 0 1]:

{ [ 1 1 ] 1 [1 -1 1] 1 }

EDIT: I think this is desirable anyway, since currently the input and output are both vectors, but vectors interpreted in entirely different ways.

[Claudio L.]

Quote:The Shadow wrote:
Okay, so FACTORS now makes the first prime factor negative if the original number was negative. I assume this is just a marker, because otherwise it's flat-out wrong. (ie, it says that -180 factors as (-2)^2*3^2*5.)

Ouch, and I thought I had accomplished a lot in the 5 minutes I had available. Of course the negative sign doesn't work with even multiplicity. So I guess having -1 1 at the beginning is the only real solution.

Quote:The Shadow wrote:
Of course, this means that -1, 1, and 0 have the same factorization! Since they have no prime factors at all.

Two possible options:

1) Bite the bullet and give two outputs, one the list and the other of the unit. So -180 would give:

{ 2 2 3 2 5 1 }
-1,

and -1 would give:

{ }
-1

I'm liking this idea. While it will break compatibility, I think it goes a long way to make the result more usable.
Actually, once you break compatibility we can completely break it and output:
* A unity factor (or sign actually), which would allow the quantity being factored to even have a physical unit attached to it.
* A list of factors
* A list of multiplicity

Arguments returned in this order allow the original number to be reconstructed simply by:

Code:


^  ΠLIST *

For example factoring 180_m would output:
1_m
{2 3 5}
{2 2 1}

The "unity" contains the sign, and any other strange "features" in the original number.

Quote:The Shadow wrote:
2) Or, go all OldRPL and include the unit, but be consistent and do it every time, not just for negatives. So +180 would give:

{ 1 1 2 2 3 2 5 1 }

I dislike this option but if it's always there it's much easier to manage. Likewise, the factorization of 0 would be:

{ 0 1 }

(EDIT: There's also option 3: Once tagged objects are in, tag the list of factors with the unit.)

I think it would be cleaner to do the above.
Then 1 would be:
1
{ }
{ }
(the only catch is that ΠLIST errors on empty lists, so this case needs to be trapped separately)

or we could actually do:
1
{ 1 }
{ 1 }

to make it more manageable by programs

zero would factor as:
1
{ 0 }
{ 1 }

Quote:The Shadow wrote:
FACTORS also chokes on some non-integer inputs without throwing an error. For example, 1.5 gives:

{ 1.5 1 -1 0 }

which is more than a little odd. Other times it seems to round off first. OldRPL would actually factor rational numbers, so 1.5 (well, '3/2', but the difference isn't as important in NewRPL) would give:

{ 2 -1 3 1 }

which strikes me as much more desirable.

I thought there was a trap for integers only, but I like the factorization of the fraction!
For example 0.15 should be factored as 15 (*10^-2), then it's almost trivial to find all '2's and '5's in the list (or add them) then subtract 2 from their exponent.

Quote:The Shadow wrote:
The polynomial factorization is still a little odd. It throws an error when the polynomial has complex roots, but still manages to calculate them.

It's on purpose, (same as a square root) it throws an error if the result is complex and you are not in complex mode, other than that the results should be good, and if you set the complex mode flag the error will quietly vanish

Quote:The Shadow wrote:
I think it's more sensible to have a flag to just not break up factors irreducible in the reals. Of course, this gives headaches in the output syntax, as the vector notation breaks down. You'd need something like this for [1 0 0 1]:

{ [ 1 1 ] 1 [1 -1 1] 1 }

EDIT: I think this is desirable anyway, since currently the input and output are both vectors, but vectors interpreted in entirely different ways.

I think the output should be the same as I proposed above for reals. Forget the vectors and use lists, after all the result is a list of factors, not another polynomial.
So, we would leave the leading factor, then a list of factors (or perhaps we should change the signs and output the roots?) and then a list of multiplicities.
For example for 4*x^2-8*x+4 the output would be:
4
{ -1}
{2}

(we could also use +1 in the middle list and define the factors as (x-an) rather than (x+an) )

Then the factored polynomial equation can be easily obtained by:

Code:

 'X' ROT + SWAP ^ ΠLIST *

[ijabbott]

Claudio L. Wrote:

The Shadow Wrote:Okay, so FACTORS now makes the first prime factor negative if the original number was negative. I assume this is just a marker, because otherwise it's flat-out wrong. (ie, it says that -180 factors as (-2)^2*3^2*5.)

Ouch, and I thought I had accomplished a lot in the 5 minutes I had available. Of course the negative sign doesn't work with even multiplicity. So I guess having -1 1 at the beginning is the only real solution.

How about { -2 1 2 1 3 2 5 1 }? I.e. extract just one power of the first factor and make it negative. This would only need to be done if there is an even power of the first factor.

[Claudio L.]

Quote:ijabbot wrote:
How about { -2 1 2 1 3 2 5 1 }? I.e. extract just one power of the first factor and make it negative. This would only need to be done if there is an even power of the first factor.

Clever! Although I'm currently leaning towards breaking compatibility and splitting the list as discussed. It seems to make much more sense in newRPL, especially since the operators work as expected on lists. It just takes much less effort to use the results.
It also allows consistency between FACTORS of a number and of a poly, which is a nice-to-have feature.

[The Shadow]

Claudio L. Wrote:I'm liking this idea. While it will break compatibility, I think it goes a long way to make the result more usable.
Actually, once you break compatibility we can completely break it and output:
* A unity factor (or sign actually), which would allow the quantity being factored to even have a physical unit attached to it.
* A list of factors
* A list of multiplicity

I vastly prefer this solution, but didn't realize it was on the table. By all means, do this!

EDIT: The reason why I strongly prefer it is that to actually USE the factorization for anything, you have to separate the multiplicities from the primes anyway. It's an extra loop (or extra caution on a single loop) in every single program that uses prime factors, and it shouldn't be necessary.

I hadn't thought of your idea of being able to give the unit well, units. That's very cool.

Quote:I think it would be cleaner to do the above.
Then 1 would be:
1
{ }
{ }
(the only catch is that ΠLIST errors on empty lists, so this case needs to be trapped separately)

or we could actually do:
1
{ 1 }
{ 1 }

to make it more manageable by programs

I can live with the latter, as long as 1 never shows up as a factor in anything but 1, -1, or 0.

(I actually wouldn't have a problem error-trapping on empty lists, but I see your point.)

Quote:zero would factor as:
1
{ 0 }
{ 1 }

Bad idea. You're basically defining zero as positive. Better to do:

0
{ 1 }
{ 1 }

Yes, technically zero is not a unit... but it just makes more sense this way.

Quote:So, we would leave the leading factor, then a list of factors (or perhaps we should change the signs and output the roots?) and then a list of multiplicities.
For example for 4*x^2-8*x+4 the output would be:
4
{ -1}
{2}

(we could also use +1 in the middle list and define the factors as (x-an) rather than (x+an) )

Looks good. (x-an) is more traditional in the math community, because x-an=0 yields an rather than -an.

If you decide to let FACTORS handle rational numbers (please do!) don't forget to let it also handle rational functions. Just allow for negative exponents on polynomial factors.

[The Shadow]

Oh, and now that we're getting factoring stuff, can I throw in a request for FXND? I use it constantly.

[The Shadow]

I've been mulling over FACTORS some more, and I think the special cases of 1, -1, and 0 should have this form:

1 (or -1 or 0)
{ 1 }
{ 0 }

My reasoning is as follows: 1 is *not* a prime factor, and hence should contribute nothing to the sum of prime factors. By having the multiplicity be 1, many equations are messed up - the sum-of-divisors function, to name just one.

[Claudio L.]

(08-03-2018 03:39 AM)The Shadow Wrote:  I've been mulling over FACTORS some more, and I think the special cases of 1, -1, and 0 should have this form:

1 (or -1 or 0)
{ 1 }
{ 0 }

My reasoning is as follows: 1 is *not* a prime factor, and hence should contribute nothing to the sum of prime factors. By having the multiplicity be 1, many equations are messed up - the sum-of-divisors function, to name just one.

While you are of course correct, I don't think you'll get much information from the sum of divisors of 1, -1 or 0.

Check out build 1093 (I updated it), it works now per your previous post. The fractional numbers is not as good as it could be, because of course a real that cannot be represented exactly like 1/3 converts to a fraction 3333333333333.../1000000000000... instead of 1/3. I guess I could improve it by calling ->Q before and then factoring numerator and denominator independently.

Regarding the polynomials with negative exponents, I don't know how to handle this case, can you elaborate?

PS: Finally, the forum quoting function is back again!

[The Shadow]

(08-03-2018 02:15 PM)Claudio L. Wrote:  While you are of course correct, I don't think you'll get much information from the sum of divisors of 1, -1 or 0.

Of course not, but that's another bit of error trapping that isn't necessary.

Quote: I guess I could improve it by calling ->Q before and then factoring numerator and denominator independently.

Sounds like a good idea.

Quote:Regarding the polynomials with negative exponents, I don't know how to handle this case, can you elaborate?

Basically just factor the numerator and denominator, and make the latter multiplicities negative.

[Claudio L.]

(08-03-2018 04:59 PM)The Shadow Wrote:  

(08-03-2018 02:15 PM)Claudio L. Wrote:  Regarding the polynomials with negative exponents, I don't know how to handle this case, can you elaborate?

Basically just factor the numerator and denominator, and make the latter multiplicities negative.

No, really. I don't understand and need you to elaborate! Are you talking about a single polynomial in which some of the terms have negative exponents? Or a rational expression where the numerator and denominator are polynomials?

The first case can easily by transformed by multiplying by x^n, with n being the lowest exponent in the polynomial, right? Then FACTORS will find a factor 0 with multiplicity n that wasn't there in the original. Am I even going in the right direction?
The second case is more problematic, since FACTORS accepts only a vector for now, how do you express the rational as a vector? It's best left as 2 vectors, then you can use FACTORS independently.

[Claudio L.]

All unofficial ROMs updated to 1099.

The main change is the addition of the multiple non-linear equation solver (command MSOLVE).

It works like this:
Arguments:
* List with equations in the stack (any number of equations, at least one of course)
* List with variable names (the variables that will be used as variables in the search)
* Initial guess range: List with minimum values for each of the names
* Initial guess range: List with maximum values for each of the names
* A real number with the desired tolerance

The main difference with ROOT is that equations don't need to be in the form 'F(X)=expression'. Since this is a more general solver, expressions can be of any type, mainly:
'expression' which will be interpreted as 'expression=0' when searching for roots
'expression=expression' your typical equation
'expression<expression' All kinds of inequalities accepted (>, <, <=, >=)

The list of variable names can have any number of variables. Any other variables in the equations need to be defined elsewhere (as globals or locals) and will remain constant during the analysis.

The initial guess is a range of values where the algorithm will begin the search. This is not a bracketed method, so it may converge to roots outside this range, this is only an initial guess.
The range of variables can be constrained by adding inequalities like 'X>-5' to the list of equations.

Finally, the tolerance is up to your own patience. Always start with 2 or 3 digits (0.001), and if it finds a root, then run it again with tighter tolerance.

The solver uses an optimization method, so it actually minimizes the sum of the squares of the equations (*). This means it may find local minimums instead of actual roots.
Also, the method only works properly with real numbers, so don't even try it in the complex plane. Make sure all equations return real values. Division by zero or any kind of infinity needs flag -22 to be set so your equations don't error but return +/-Inf, which the solver can handle, no problem.
Also, the solver is derivative-free, so functions don't need to be continuous.

To distinguish between them, MSOLVE returns:
* A list of values for each of the variables in the list
* A list of the value of each equation after replacing the solution found, so the user can see whether the equations are satisfied by this solution or not.

(*) For inequalities, when an inequality is True, it adds no value to the sum. When it is false, it turns the result of the sum into +Inf, making it the worst choice of solution, hence the algorithm will turn away from areas that don't satisfy inequalities. In other words, regular equations are "minimized", while inequalities are "enforced".

This needs HEAVY testing. Please help test it thoroughly and report any anomalies (like looping forever, crashing, etc.).

[rprosperi]

(08-09-2018 03:47 PM)Claudio L. Wrote:  The main change is the addition of the multiple non-linear equation solver (command MSOLVE).

It works like this:
Arguments:
* List with equations in the stack (any number of equations, at least one of course)
* List with variable names (the variables that will be used as variables in the search)
* Initial guess range: List with minimum values for each of the names
* Initial guess range: List with maximum values for each of the names
* A real number with the desired tolerance
...

This needs HEAVY testing. Please help test it thoroughly and report any anomalies (like looping forever, crashing, etc.).

Claudio - Suggest you provide 2 examples, one trivial and one non-trivial, to illustrate the exact syntax of the arguments; this avoids time wasted figuring out what your explanations do/don't mean. I'm not suggesting the wording is poor, simply that for such use, interpretation can vary. For example is the list with variable names like { A B C } or {'A' 'B' 'C'}, etc.

[Claudio L.]

(08-09-2018 03:57 PM)rprosperi Wrote:  Claudio - Suggest you provide 2 examples, one trivial and one non-trivial, to illustrate the exact syntax of the arguments; this avoids time wasted figuring out what your explanations do/don't mean. I'm not suggesting the wording is poor, simply that for such use, interpretation can vary. For example is the list with variable names like { A B C } or {'A' 'B' 'C'}, etc.

Fair enough. Here's the trivial one: get the roots of x^2=4

Code:


{ 'X^2=4' }  @ List of equations
{ 'X' } @ List of variables (quoted/unquoted doesn't matter)
{ 1 } @ Initial guess range: left point
{ 10 } @ Initial guess range: right point (can be anything as long as all variables are different from the left point)
0.0001 @ TOLERANCE

MSOLVE

It will return:

Code:


{ -2.000022888184 } @ List of values for each of the variables
{ 0.000091553258. } @ List of residuals for each expression (same as storing the result and ->NUM on the equations)

In this case it converged to the negative. If we want the positive there's 2 options:
a) Try a different initial guess range, for example { 0 } { 1 } does the trick.
b) Coerce the system with a constraint: change the list of equations to:

Code:

{ 'X^2=4' 'X>0' }

And sure enough, you'll get the positive root.

A less trivial example:

To test the Beale function from here:

Code:


{ '1.5-X+X*Y' '2.25-X+X*Y^2' '2.625-X+X*Y^3' } @ We input them as 3 separate expressions
{ 'X' 'Y' }    @ 2 Variables
{ -4.5 -4.5 }  @ Same range as in Wikipedia
{ 4.5 4.5 }    @ Same range as in Wikipedia
0.0001    @ Tolerance

The results are this:

Code:


{ -317914.438741247053. 1.000003117366. } @Values
{ 0.508944245104. 0.267885400724. -0.348176533149. } @ Residues

And from the residues we can see the algorithm didn't find a root, the value of X diverged to the negative side while Y converged to 1. Not what we expected, let's try inverting the range:

Code:


{ '1.5-X+X*Y' '2.25-X+X*Y^2' '2.625-X+X*Y^3' } @ We input them as 3 separate expressions
{ 'X' 'Y' }    @ 2 Variables
{ 4.5 4.5 }  @ Same range as in Wikipedia
{ -4.5 -4.5 }    @ Same range as in Wikipedia
0.0001    @ Tolerance

And now we get:

Code:


{ 2.99999918766. 0.50000000274. }
{ 0.000000414389. 0.000000617475. 0.000000716962. }

And now the algorithm went the other way (towards the positive side of X), converging to the proper root.

EDIT: By the way, you could also force a constraint by adding 'X>-4.5' to the list of equations.

[Claudio L.]

I forgot to mention, MSOLVE also accepts a program instead of a list of equations. The program must take N arguments from the stack (N=number of variables provided in the list of variable names) and return a single real number. The algorithm will try to minimize the result of the program.
A program that does the sums of the squares of various expressions would be equivalent to providing the list of expressions directly.

[pier4r]

Claudio really good work. I admire all of you (Claudio, the WP team, Thomas, of course HP, Casio, etc.., Scary, Aricalculator, HRASTprogrammer, the guys making emulators, etc... ) that go coding calculator functions because I feel already the experience is worth plenty for refreshing math and learning a more concepts and tools.

I see this activity as a great one but I have not yet started (even with limited scope, say: bc libraries http://www.hpmuseum.org/forum/thread-10132.html ).

[The Shadow]

I'm getting a persistent crash when trying to enter functions. Typing most letters after a single quote crashes NewRPL. One of the few exceptions is N.

So I tried to type 'N(X)=X^2-4', but this time it crashed when I entered the second X. Indeed, entering anything after an equals sign seems to cause the crash.

EDIT: Entering any number seems to crash NewRPL, in fact. I have reinstalled the update and get the same issue.

P.S. Forget what I said about rational functions, I wasn't thinking things through.

[The Shadow]

I tried downgrading to 1089, but I'm getting the same crash. I think I see the problem - one of my libraries has become corrupted, and appears as DIRObj in the Libraries menu.

I'm not sure how to fix the problem, though, since in the absence of being able to enter letters or numbers, I can't revert to one of my backups.

EDIT: I managed to wipe the memory by taking the batteries out, then using SDRESTORE.

Incidentally, the option under ON-A-F to wipe the memory doesn't seem to work.