[Date Index]
[Thread Index]
[Author Index]
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**
| |