WOLFRAM

Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

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

Search the Archive

Re: Re: smallest fraction

One more remark about the quadratic form mentioned below: in the most  
usual approach to the problem of approximating numbers by algebraic  
numbers,  the form looks like this:

a0^2+a1^2+a2^2+ ... + an^2 + M*(a0+a1 z^2+ ...an z^n)^2

where M is some large number (ai are all integers) and z is the number  
we wish to approximate by an algebraic number.  The LLL algorithm  
produces a "short vector"  with respect to this form, which means that  
approximately a0+a1 z^2+ ...an z^n = 0 and (a1,a2,...an) is a "short"  
vector in the usual norm. So, in the case when n =1 this is "similar"  
to "minimizing p^2+q^2", but of course not exactly so.


Andrzej Kozlowksi



On 27 Mar 2008, at 07:39, Andrzej Kozlowski wrote:
> 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: Mathematica SIG (Washington DC Area)
  • Next by Date: Re: Re: smallest fraction
  • Previous by thread: Re: smallest fraction
  • Next by thread: Re: Re: smallest fraction