PSLQ

11292017, 08:12 PM
(This post was last modified: 12052017 06:58 PM by Han.)
Post: #1




PSLQ
PSLQ (Partial Sums LQ Decomposition) can be used to determine if there exists a set of integer coefficients \( \mathbf{a} = (a_1, a_2, \dotsm, a_n) \) for a given vector \( \mathbf{x} = (x_1, x_2, \dotsm, x_n) \) such that their dot product is 0 (i.e. \( \sum a_i x_i = 0 \) ).
Please note that this is beta; I have not implemented a full set of exit conditions! Code: NINT(x) This can be used to solve a number of interesting "algebraic form" problems. For example, the number 3.96811878507 is the decimal approximation of \( x=\sqrt{3} + \sqrt{5} \). The value \( x \) is a root of the polynomial \( x^4  16x^2 + 4 \). Moreover, numbers of the form \( \sqrt{a} + \sqrt{b} \) are roots of \( x^4  2(a+b)x^2 + (ab)^2 \). We can use PSLQ on the vector \( ( x^4, x^3, x^2, x, 1 ) \) to obtain the result: \( ( 1, 0, 16, 0, 4 ) \). Additionally solving \( 2(a+b) = 16 \) and \( (ab)^2=4 \) simultaneously results in the values a=3 and b=5. Code:
Another example may be to rewrite \( x \approx 7.09439510239 \) in the preferred form \( 2\pi/3 + 5 \). Notice that \( x \) satisfies: \( 0 = 2\pi 3x + 15 \). So if we apply PLSQ to the vector \( (\pi, 7.09439510239, 1 ) \) we get the vector \( (2,3,15) \) Code:
Also, if we have a number of the form \( x= r_1 + \sqrt{r_2} \) where the \( r_i \)'s are rational numbers, then simply apply PSLQ to \( ( x^2, x, 1) \) since such numbers are roots of some quadratic polynomial. The result from PSLQ  \( ( a,b,c ) \)  are the coefficient of the quadratic polynomial, and can then be used to rewrite \( x\) into a nice algebraic form using \( x = \frac{b \pm \sqrt{b^24ac}}{2a} \) Code:
Graph 3D  QPI  SolveSys 

11292017, 08:42 PM
Post: #2




RE: PSLQ
Code for identifying \( x = \sqrt{a} + \sqrt{b} \):
Code:
Requires PSLQ above. Example: Code: X:=SQRT(3)+SQRT(5); Graph 3D  QPI  SolveSys 

11292017, 08:52 PM
(This post was last modified: 11292017 09:32 PM by Han.)
Post: #3




RE: PSLQ
Code for identifying \( x = p_1/q_1 + \sqrt{p_2/q_2} \):
Code: EXPORT QROOT(x) Graph 3D  QPI  SolveSys 

11292017, 08:58 PM
Post: #4




RE: PSLQ
Thank you!
very interesting, a great algorithm. ∫aL√0mic (IT9CLU), HP Prime, 50g, 41CX, 42s, 15C, 12C, DM42 :: Prime Soft. Lib 

11292017, 09:28 PM
(This post was last modified: 11292017 09:30 PM by salvomic.)
Post: #5




RE: PSLQ
(11292017 08:52 PM)Han Wrote: ... ∫aL√0mic (IT9CLU), HP Prime, 50g, 41CX, 42s, 15C, 12C, DM42 :: Prime Soft. Lib 

11292017, 09:33 PM
(This post was last modified: 11292017 09:33 PM by Han.)
Post: #6




RE: PSLQ
(11292017 09:28 PM)salvomic Wrote: Han, I must have copied the wrong version of the code (one on calc vs one typed out onto notepad). Should be correct now. Graph 3D  QPI  SolveSys 

11292017, 09:35 PM
Post: #7




RE: PSLQ
(11292017 09:33 PM)Han Wrote: I must have copied the wrong version of the code (one on calc vs one typed out onto notepad). Should be correct now. yes, it is! now it's ok. ∫aL√0mic (IT9CLU), HP Prime, 50g, 41CX, 42s, 15C, 12C, DM42 :: Prime Soft. Lib 

11302017, 02:16 AM
Post: #8




RE: PSLQ
I like the irony, or if you like: paradox, of these functions. So sorry, if you are not interested, for the caveat rant for those expecting silver bullets wherever they go.
The motivation for PSLQ (and QPI) seems to be that "arbitrary numbers" are likely to be of a special type: rational, semirational (in QPI sense), or algebraic (or in the same field extension of Q as some other numbers). This is also illustrated by the various naming suggestions for QPI, especially those involving the word "exact" or otherwise suggesting that you are (always, usually?) getting a "better" representation of a number. And in situations where that is actually the case these functions are of course very useful. But, as a sanity check, from a mathematical perspective these special types of numbers have measure zero, i.e. the probability that a randomly picked real number (within a given range, say between 0 and 1) belongs to one of these special types is 0, rather than close to 1. So mathematically your expectation that these functions will be useful when working with arbirtrary numbers should be 0 too. And at the other end of the scale, i.e. when you take into account that machine numbers are not "arbitrary (real) numbers" to begin with: all machine floats are already rational, so why bother about finding "better" (?) rational, semirational or algebraic representations? This is borderline pseudoscience, depending on the context. And on top of this it is all relative as well. "3.141592653" coming out of a long calculation on the Prime may be "better" represented as pi, whereas coming out of a similar calculation using Free32 it is extremely unlikely that pi is a better representation (unless there is an issue with the calculation itself). Who is going to check whether the accuracy justifies or invalidates the "better" representation (not your average student, I would expect)? So it seems that we are dealing with some shadowy area between Q and R, representing it all with just a subset of Q in a way that actually seems to make some sense. But only as long as you know what you are doing. 

11302017, 03:14 AM
(This post was last modified: 11302017 03:14 AM by Han.)
Post: #9




RE: PSLQ
(11302017 02:16 AM)AlexFekken Wrote: [b]But, as a sanity check, from a mathematical perspective these special types of numbers have measure zero, i.e. the probability that a randomly picked real number (within a given range, say between 0 and 1) belongs to one of these special types is 0, rather than close to 1. So mathematically your expectation that these functions will be useful when working with arbirtrary numbers should be 0 too. I suppose it depends on whether you are looking at pure measure, or "relative measure"  in the sense that most students are given problems in which the answers are generally not from the set of reals, but instead from the set of algebraic numbers. (I.e. they are guaranteed with probability 1.) But even for folks such as physicists are interested in these "nice" numbers because they show up as constants in various "important" physics equations. In fact, there is an entire field of study devoted to finding the "identity" of various constants all due to the advent of more efficient algorithms for integer coefficients such as PSLQ. http://www2.lbl.gov/ScienceArticles/Arc...rithm.html Graph 3D  QPI  SolveSys 

11302017, 03:56 AM
Post: #10




RE: PSLQ
(11302017 03:14 AM)Han Wrote: I suppose it depends on whether you are looking at pure measure, or "relative measure"  in the sense that most students are given problems in which the answers are generally not from the set of reals, but instead from the set of algebraic numbers. (I.e. they are guaranteed with probability 1.)It has been a long time since I was a student and I agree that this was certainly the case in "my days". Really sad if this is still the case though. It also begs the question of why you would allow the use of calculators for such problems (or why you would give them such problems when you allow the use of calculators)... (11302017 03:14 AM)Han Wrote: But even for folks such as physicists are interested in these "nice" numbers because they show up as constants in various "important" physics equations. In fact, there is an entire field of study devoted to finding the "identity" of various constants all due to the advent of more efficient algorithms for integer coefficients such as PSLQ.I am sure there is value in that in certain areas of physics. But as the article points out: "Very high precision arithmetic is needed by PSLQ, or else nonsense results are obtained" which, if you add the obvious requirement that you need to relate that to the accuracy of your input, is sort of the main point that I was trying to make. Better finish by saying that I do appreciate your efforts in implementating these algorithms. Just worried about some of the people who will use them with their eyes closed :) 

11302017, 11:05 AM
Post: #11




RE: PSLQ
Hello Han,
Really amazing, as usual from you !!! Only a question, Instead getting {1,0,16,0,4}, I get here this [1 0 −16 0 4] AmI wrong ? Thanks. Gérard. 

11302017, 12:19 PM
Post: #12




RE: PSLQ
(11302017 11:05 AM)ggauny@live.fr Wrote: Hello Han, No, I just typed with the wrong symbols ({} vs. []) Graph 3D  QPI  SolveSys 

11302017, 12:29 PM
Post: #13




RE: PSLQ
Thanks.
Gérard. 

11302017, 11:10 PM
Post: #14




RE: PSLQ
(11302017 02:16 AM)AlexFekken Wrote: But, as a sanity check, from a mathematical perspective these special types of numbers have measure zero [...] This is very true. However, there are good, nonmathematical reasons for having such a function: I refer you to this excellent post from Valentin Albillo in which he determines the underlying cause of an HP35S ROM bug by analysing the faulty values returned. 

12022017, 11:55 PM
Post: #15




RE: PSLQ
(11302017 11:10 PM)BruceH Wrote: However, there are good, nonmathematical reasons for having such a function: I refer you to this excellent post from Valentin Albillo in which he determines the underlying cause of an HP35S ROM bug by analysing the faulty values returned. Nice reference, thanks for that. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)