On 7/24/13, Fred lunnon <fred.lunnon@gmail.com> wrote:
Why should that process be "efficient", in the sense of minimising the denominator for given error bound?
WFL
On 7/24/13, James Propp <jamespropp@gmail.com> wrote:
If an algebraic number is a Salem number, or a Pisot number, or something like that, then it's the principal eigenvalue of some integer matrix. And you can efficiently raise a matrix to a high power by repeated squaring. So this should give an efficient way to approximate such a number by rational numbers.
Jim Propp
On Wed, Jul 24, 2013 at 11:08 AM, Simon Plouffe <simon.plouffe@gmail.com>wrote:
Yes, and no.
Yes the problem can be done with HSG (high speed guessing) easily on a computer using linear programming techniques or equivalent. BUT : the current LLL-PSLQ algorithms do have a long history: The first versions of PSLQ was based on one article of a certain Ferguson ( et al ?) at the time the cost of computation was of the order of n^8 , nowaday, this is far better.
Some of the readers of this group are experts in this domain. I recall that the PSLQ integer relation algorithm was based on 1 famous algorithm of linear algebra not trivial at all from a certain Dongarra and a lot of work was made on it to finaly come up with something that can attack simple questions concerning real numbers like :
Is the Madelung Constant (the NACL constant) is made of simple numbers, like log(2), log(Pi) , etc.
Is gamma , exp(1) and Pi linearly independant ?
Is there a simple integer relation between the first non-trivial zeros of the Zeta function ? (I tested that one, does not work apparently).
Best regards.
Simon plouffe _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun