Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

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

Search the Archive

Re: Re: Re: smallest fraction

Andrzej Kozlowski wrote:
> I note however that:
> 
> a = RootApproximant[Pi, 1]
> 80143857/25510582
> 
> and
> 
>   Rationalize[Pi, 10^(-15)]
> 80143857/25510582
> 
> which are exactly the same. As far as I know Rationalize does not use  
> lattice reduction (?) but a different algorithm, related to the way  
> one obtains a continuous fraction expansion of Pi (at least I blieve  
> that this is what Rationalze does). I am not sure if the fact that the  
> same answer is returned by the above is a coincidence or it means that  
> in fact the two algorithms amount to the same thing in this particular  
> case ?
> 
> Andrzej Kozlowski
> [...]

They are different. The LLL (or PSLQ) based aproach is sometimes 
regarded as a higher dimensional analog to continued fraction 
approximation. I believe tehre is a way of casting it that shows a 
relation between the methods. But I am not even certain of this, let 
alone know how to show it myself.

The operation of the LLL approach, in the degree one case, is this. We 
pick some digit size, say 16 (so as to be around $MachinePrecision, just 
for illustration purposes). We multiply our goal, Pi, by that number, 
and round off. Call this goal. We then form the lattice lat=

{{1,0,goal},
{ 0,1,10^16}}

We reduce this to reducedlat, and look at the shortest vector, call it 
{a,b,c}. The identity matrix at the left of 'lat' has in effect recorded 
row operations needed to form this vector. In nice cases, c will be 
small, indicating that we obtain an approximate zero as a*goal+b*10^16. 
But this simply means that goal is approximately -b*10^16/a, hence Pi is 
approximately -b/a.

In this example:

In[101]:= InputForm[-redlat[[1,2]]/redlat[[1,1]]]
Out[101]//InputForm= 80143857/25510582

It is reasonable to ask whether this approach, if used at the same 
precision/#digits as Rationalize, will always give the same result. I do 
not know. But I would expect them to be close, and usually identical. 
Reason being, both tend to find a result with small numerator and 
denominator, with "small" typically being around half the number of 
digits we use in our approximation. There are not likely to be too many 
contenders.

Daniel Lichtblau
Wolfram Research
  • Prev by Date: Re: FindMinimum[Print[]]
  • Next by Date: Mathematica notebooks the best method for technical communications (Was: Another stylesheet question)
  • Previous by thread: Re: Re: smallest fraction
  • Next by thread: Re: Re: Re: smallest fraction