Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

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

Search the Archive

Re: Re: Re: smallest fraction

On 27 Mar 2008, at 15:59, Daniel Lichtblau wrote:
> 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
>
>
>


I realize now (I think I noticed this already one a long time ago but  
forgot) that this way of using LLL seems rather different from the one  
I once learned and tried to (roughly ) describe in this thread. In  
particular, the approach to "recognizing algebraics" you describe only  
uses lattice reduction for the standard euclidean inner product (or  
the standard norm) whereas the approach that I had in mind (described,  
for example, in Henri Cohen's "Course in Computational Number Theory",  
page 100),  uses lattice reduction for a specially constructed  
positive definite quadratic form. The two approaches appear to be  
equivalent but I can't at this time clarify the relationship between  
them. Is there something obvious that I am missing?

Furthermore, I have notice that

  Developer`SystemOptions["LatticeReduceOptions"]
{"LatticeReduceOptions" ->
      {"LatticeReduceArithmetic" -> Integers,
        "LatticeReduceInnerProduct" -> Automatic,
        "LatticeReduceRatioParameter" -> Automatic}}

makes it possible to use a non-standard inner product in  
LatticeReduction. Presumably a custom inner product should be  
specified as a pure function?
I guess that should make it possible to implement the alternative  
approach described in Cohen's book?. (Of course if they are clearly  
equivalent there would be not much point doing this but if is not  
obvious it might be interesting to compare the answers one gets from  
each of them).

Andrzej Kozlowski
  • Prev by Date: Re: Problems with differentiating Piecewise functions
  • Next by Date: Re: Re: Re: changing style of vertices
  • Previous by thread: Re: Re: Re: smallest fraction
  • Next by thread: Re: Re: Re: Re: smallest fraction