Re: question on recovering a rational number from its decimal value

[Aurel Page <aurel.page@normalesup.org>]

Dear Randall,

What are you looking for: speed or reliability? Under what hypothesis on 
the input?

As you surely know, it is sometimes better to look at other convergents 
than the last one. For instance:
? \pb 512
? a = 7557322358563246340/14991082624209354397;
? b = precision(precision(1.*a,256),512);
? bestappr(b)
% = 
6759160041226234361291080973374592586473124091525792010155731448234242519586648364735933282365563921311185600471934451359158339058237455806791025351888667/13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
? cf = contfrac(b)
% = [0, 1, 1, 60, 6, 5, 1, 36, 1, 2, 6, 1, 1, 7, 1, 9, 1, 4, 1, 3, 2, 2, 
2, 1, 12, 1, 7, 4, 1, 2, 1, 4, 12, 111, 1, 3, 
1717457819187026092531695031638440685671213830020926310944305298982676749703398199886410856458289035726278001792883872, 
1, 1, 23, 8, 12, 9, 1, 2, 43, 6, 2, 1, 3, 1, 5, 1, 5, 2, 1, 2, 6, 45, 7, 
1, 66, 1, 3, 1, 3]

It is clear that we should truncate the continued fraction before the 
very large value.

? vecmax(cf,&i);
? contfracpnqn(cf[1..i-1])
% =
[ 7557322358563246340 1893554184859258427]
[14991082624209354397 3756148790778748428]

Cheers,
Aurel

On 05/06/2025 07:08, American Citizen wrote:
> The situation of recovering a rational from a decimal value is one 
> where I found the best performance was given by using 
> contfracpnqn(contfrac(decimal_value)) to recover the rational number. 
> But I will bring up bestappr and algdep also and provide a simple 
> example.
>
> For example:
>
>  \p38
>    realprecision = 38 significant digits
> ? a = 7557322358563246340/14991082624209354397
> ? b=1.0*a
> %182 = 0.50412118644178492341805370212027471167
> ? bestappr(b)
> %183 = 
> 79189105149167506491695797085942154095/157083469766673122582441828941171667778
> ? bestappr(b,10^20)
> %184 = 7557322358563246340/14991082624209354397
>
> I am trying to recover a, not some rational with many more digits to 
> both the numerator and denominator for a which is what bestappr(b) did 
> without a denominator size restriction.
>
> Let's look at c= contfracpnqn(contfrac(b))
>
> %185 =
> [ 7557322358563246340 1893554184859258427]
>
> [14991082624209354397 3756148790778748428]
> and c[1,1]/c[2,1] recovers a quite nicely.
>
> I found this method quite reliable for nailing the "correct" rational 
> given its decimal.
>
> Would using algdep(b,1) work well too?
>
> ? algdep(b,1)
> %190 = 579338739897539*x - 292056932908836
>
> this is in error, by increasing precision to 57 digits I can 
> successfully recover a
>
> ? \p57
>    realprecision = 57 significant digits
> ? b=1.0*a
> %192 = 0.504121186441784923418053702120274711673751913427062758309
> ? algdep(b,1)
> %193 = 14991082624209354397*x - 7557322358563246340
>
> so apparently we have to increase the precision by 1.5x before doing 
> the algdep command as it seems to me.
>
> What is the timing trade off when doings hundreds of thousands of 
> rational number recoveries from their decimal value? Is algdep(b,1) 
> more costly in time than bestappr(b) and is contfracpnqn(contfrac(b)) 
> faster than bestappr?
>
> Randall