Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

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

Search the Archive

Re: Re: smallest fraction

I only realized the point of the question the day after I posted the  
reply below.
I see now it is only concerned with what happens here:

RootApproximant[Pi, 1]
80143857/25510582

that with the special case when we approximate a real number by an  
algebraic number of degree 1, i.e. a rational. Of course  
RootApproximant is not principally intended for finding rational  
approximations, but I am sure that some version of the LLL algorithm  
is still used. I think it means that some quadratic form in (a,b)  
(where a and b are the numerator and the denominator of the rational  
approximation) is (in effect) minimized but what this form is, is not  
clear to me and I think it depends on the details of the implementation.

Andrzej Kozlowski


On 26 Mar 2008, at 19:54, Andrzej Kozlowski wrote:
> It's rather more complicated than that. It goes roughly like this:  
> given some complex number z, we want to find a polynomial f(x)= a0 +  
> a1 x + a2 x^2 + ... an x^n, where ai are all integers, such that z  
> is an approximate root of f. To do so we construct a certian  
> quadratic form in (a0,a1,..an) involving f(z) and then use the so  
> called "lattice reduction algorithm" of Lenstra,Lenstra and Lovasz  
> (LLL) to find a vector with integral coordinates which is  
> "short" (in some well defined sense) for this lattice. Once we have  
> that we can find the required f(x), which is an approximate and, in  
> favourable cases, the exact minimal polynomial of z.
>
> I think that it might be, in priciple, possible to do this using  
> Minimize or NMinimize but I don't think it would be competitive in  
> terms of performance in the former case or accuracy in the latter.
>
> Andrzej Kozlowski
>
>
> On 26 Mar 2008, at 10:52, Artur wrote:
>>
>> Who know which is minimalize function is used by Mathematica in
>> following approximation function by rational fractions:
>>
>> << NumberTheory`Recognize`   (*In Mathematica 6 RootApproximant[]
>> inspite Recognize[]*)
>>
>> k = Recognize[N[Pi, 6], 1, x];Solve[k==0,x]
>>
>> if we have rational fraction p/q (where p,q are both integers)
>> is minimalize function: p+q, p*q, p^2+q^2 or other ?
>>
>> ARTUR JASINSKI
>>
>>
>>
>>
>> Andrzej Kozlowski pisze:
>>> Somehow I never saw any of this discussion so could not respond  
>>> earlier.
>>>
>>> The reason why my procedure using Reduce does not work in this
>>> particular case, is that I forgot that Reduce will not list a finite
>>> set of solutions when it is larger than a certain bound. So, for
>>> example:
>>>
>>> cond[a_, b_] :=
>>> Reduce[a < p/q < b && (p - 1)/q < a && p/(q - 1) > b && p >= 1 && q
>>>> = 1, {p,
>>>    q}, Integers]
>>>
>>> cond[23/26, 29/30]
>>> Out[5]= (p == 8 && q == 9) || (p == 9 && q == 10) ||
>>>   (p == 10 && q == 11) || (p == 11 && q == 12) ||
>>>   (p == 12 && q == 13) || (p == 13 && q == 14) ||
>>>   (p == 14 && q == 15) || (p == 15 && q == 16) ||
>>>   (p == 16 && q == 17)
>>> (the first element gives the solution), but with a larger number of
>>> solutions:
>>>
>>> cond[113/355, 106/333]
>>> Out[6]= Element[p | q, Integers] &&
>>>   ((1 <= p <= 11978 && (333*p)/106 < q <
>>>           (355*p)/113) || (11979 <= p <= 37630 &&
>>>         (333*p)/106 < q < (1/106)*(333*p + 106)) ||
>>>      (37631 <= p <= 49607 && (1/113)*(355*p - 355) < q <
>>>           (1/106)*(333*p + 106)))
>>>
>>> However, the bound can be user controlled, as follows:
>>>
>>> Developer`SetSystemOptions[
>>> "ReduceOptions" -> ("DiscreteSolutionBound" -> 10^3)]
>>>
>>> And then:
>>>
>>> First[cond[113/355, 106/333]]
>>> p == 219 && q == 688
>>>
>>>
>>> Of course I never recommended this method, which is much slower than
>>> using Minimize. It can however find complete solutions with  
>>> situations
>>> when the solution is not unique, for example if we tried to minimize
>>> the difference of squares between the denominator and the  
>>> numerator etc.
>>>
>>> Andrzej Kozlowski
>>>
>>>
>>> On 24 Mar 2008, at 07:45, Carl Woll wrote:
>>>
>>>> Carl Woll wrote:
>>>>
>>>>
>>>>> Artur wrote:
>>>>>
>>>>>
>>>>>> If we want to find rational fraction f =p/q such that
>>>>>> 113/355<f<106/333 and sum p+q is minimal
>>>>>> anyone procedure proposed  up to now doesn't work
>>>>>> good result should be
>>>>>> {137563,{p->13215,q->104348}}
>>>>>> but isn't
>>>>>>
>>>>>>
>>>>>>
>>>>> Your good result isn't so good, consider:
>>>>>
>>>>> In[36]:= 113/355 < 219/688 < 106/333
>>>>>
>>>>> Out[36]= True
>>>>>
>>>>> One idea (similar to your Recognize approach) is to use  
>>>>> Rationalize
>>>>> or
>>>>> RootApproximant with SetPrecision:
>>>>>
>>>>> In[71]:= Rationalize[SetPrecision[(106/333 + 113/355)/2, 6], 0]
>>>>>
>>>>> Out[71]= 219/688
>>>>>
>>>>> In[72]:= RootApproximant[SetPrecision[(106/333 + 113/355)/2, 6],  
>>>>> 1]
>>>>>
>>>>> Out[72]= 219/688
>>>>>
>>>>> I'm not sure of the correct method to determine the precision to  
>>>>> use.
>>>>> It could be something like:
>>>>>
>>>>> Choose largest prec such that:
>>>>>
>>>>> IntervalMemberQ[Interval[{lo, hi}], SetPrecision[midpoint, prec]]
>>>>>
>>>>> is still True.
>>>>>
>>>>> Carl Woll
>>>>> Wolfram Research
>>>>>
>>>> I should add that Daniel Lichtblau's minFraction just needs to be
>>>> tweaked a bit to find this result:
>>>>
>>>> minFraction[lo_Rational, hi_Rational] /; 0 < lo < hi :=
>>>> Minimize[{p + q, {Denominator[lo]*p - Numerator[lo]*q > 0,
>>>> Denominator[hi]*p - Numerator[hi]*q < 0, p >= 1, q >= 1}}, {p, q},
>>>> Integers]
>>>>
>>>> In[81]:= minFraction[113/355, 106/333]
>>>>
>>>> Out[81]= {907,{p->219,q->688}}
>>>>
>>>> Carl Woll
>>>> Wolfram Research
>>>>
>>>>
>>>>>> ARTUR
>>>>>>
>>>>>> Artur pisze:
>>>>>>
>>>>>>
>>>>>>
>>>>>>> If value p/q is known
>>>>>>> smallest Abs[p]+Abs[q ] should be
>>>>>>> << NumberTheory`Recognize`
>>>>>>> Recognize[p/q,1,x]
>>>>>>>
>>>>>>> see also
>>>>>>> http://www.research.att.com/~njas/sequences/A138335
>>>>>>>
>>>>>>> Best wishes,
>>>>>>> Artur
>>>>>>>
>>>>>>> Curtis Osterhoudt pisze:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>> I doubt this is in the spirit of the problem, but if p and q
>>>>>>>> (assumed integers) aren't restricted to be _positive_, then  
>>>>>>>> taking
>>>>>>>> them both to be very large negative numbers would both fit  
>>>>>>>> the p/q
>>>>>>>> in I requirement, and p+q as "small" as possible.
>>>>>>>>            C.O.
>>>>>>>>
>>>>>>>> On Thursday 20 March 2008 01:57:30 masmoudi wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>> hi
>>>>>>>>>
>>>>>>>>> suppose that we have an interval  I belong to [0,1]
>>>>>>>>>
>>>>>>>>> I want to know how to calculate a fraction p/q
>>>>>>>>> belong to I and p+q is the smallest possible
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>> __________ NOD32 Informacje 2701 (20071204) __________
>>>>>>>
>>>>>>> Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
>>>>>>> http://www.nod32.com lub http://www.nod32.pl
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>
>>>>
>>>
>>>
>>>
>>> __________ NOD32 Informacje 2701 (20071204) __________
>>>
>>> Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
>>> http://www.nod32.com lub http://www.nod32.pl
>>>
>>>
>>>
>>>
>>
>
  • Prev by Date: Re: Re: smallest fraction
  • Next by Date: Re: Re: smallest fraction
  • Previous by thread: Re: Re: Re: Re: smallest fraction
  • Next by thread: Re: Re: smallest fraction