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