MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: PSLQ implementation?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg34225] Re: [mg34206] PSLQ implementation?
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Fri, 10 May 2002 03:05:08 -0400 (EDT)
  • References: <200205090916.FAA12650@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Ronald Bruck wrote:
> 
> Is there an implementation of the PSLQ algorithm in Mathematica?  For
> my purposes, it would be enough to be able to find the minimal
> polynomial of a decimal approximation r of an algebraic number z, to
> within a given degree d.  (That is, to find the polynomial p(x) of
> smallest degree <= d with integer coefficients for which |p(r)| is
> smallest.)

I once wrote a crude implementation of PSLQ in Mathematica. It is not
terribly fast compared to, say David Bailey's (his makes far better use
of machine arithmetic). Even worse, mine was never fully debugged.

For finding minimal polynomials you might instead use the standard
add-on package function NumberTheory`Recognize. Here is an example I am
quite certain you will, well, recognize.

<<NumberTheory`Recognize`

In[9]:= InputForm[Recognize[N[Cos[2*Pi/13], 25], 12, t]]
Out[9]//InputForm= 1 - 6*t - 24*t^2 + 32*t^3 + 80*t^4 - 32*t^5 - 64*t^6

This function is not quite as well suited for the particular task at
hand as is PSLQ but it generally does a reasonable job.


>Best of all would be a special-purpose implementation using the Gnu
>Multiprecision Library, or equivalent.  It would be interesting to
>compare the speed to that of a Mathematica implementation.

I think Bailey's uses his multiprecision library:

http://www.nersc.gov/~dhbailey/mpdist/mpdist.html


Daniel Lichtblau
Wolfram Research



  • Prev by Date: FindRoot starting values
  • Next by Date: Re: Sequence and Or
  • Previous by thread: PSLQ implementation?
  • Next by thread: Re: PSLQ implementation?