Re: Re: smallest fraction

*To*: mathgroup at smc.vnet.net*Subject*: [mg86965] Re: [mg86911] Re: smallest fraction*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Thu, 27 Mar 2008 08:19:43 -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> <8599CE30-9D67-4966-BA80-4CA993FBC944@mimuw.edu.pl>

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

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

**Mathematica SIG (Washington DC Area)**

**Re: Re: smallest fraction**

**Re: smallest fraction**

**Re: Re: smallest fraction**