Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

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

Search the Archive

Re: Re: smallest fraction

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: Convert Array to Simple List
  • Previous by thread: Re: Re: smallest fraction
  • Next by thread: Re: Re: Re: Re: smallest