Re: Re: smallest fraction

*To*: mathgroup at smc.vnet.net*Subject*: [mg86959] Re: [mg86911] Re: smallest fraction*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Thu, 27 Mar 2008 08:18:36 -0500 (EST)*References*: <200803200757.CAA29500@smc.vnet.net> <200803210653.BAA18315@smc.vnet.net> <200803220554.AAA00496@smc.vnet.net> <200803230600.BAA25688@smc.vnet.net> <47E65E16.4010608@wolfram.com> <200803240645.BAA17083@smc.vnet.net> <200803250613.BAA10410@smc.vnet.net> <200803260952.EAA09438@smc.vnet.net> <C1C00C86-39C6-4A42-9556-9F63A4E0A6F6@mimuw.edu.pl>

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 >>> >>> >>> >>> >> >

**References**:**smallest fraction***From:*masmoudi <mas_atef@yahoo.fr>

**Re: smallest fraction***From:*Curtis Osterhoudt <cfo@lanl.gov>

**Re: Re: smallest fraction***From:*Artur <grafix@csl.pl>

**Re: Re: Re: smallest fraction***From:*Artur <grafix@csl.pl>

**Re: Re: Re: Re: smallest***From:*Carl Woll <carlw@wolfram.com>

**Re: Re: Re: Re: Re: smallest***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>

**Re: smallest fraction***From:*Artur <grafix@csl.pl>

**Re: Re: smallest fraction**

**Re: Re: smallest fraction**

**Re: Re: Re: Re: smallest fraction**

**Re: Re: smallest fraction**