[Ffmpeg-devel] [PATCH] Optimal av_reduce() implementation

[Uoti Urpala]

The current av_reduce() implementation cuts the continued fraction at
the last position which gives a numerator and denominator below the
given limit. For some inputs it's possible to get a closer match by
including one more term but making it smaller.

This patch implements a version which is optimal in the sense that it
will return the fraction within the limit that has the smallest absolute
difference from the original. If two fractions are equally distant the
one with the lowest terms is returned. Unlike the current version it
always returns valid fractions; for original values >= max+1 it returns
max instead of 1/0.

I don't know whether this gives any practical benefit in the cases where
av_reduce() is currently used in ffmpeg.

Original fraction   1000/1    1/150  31415/10000 3141592653/1000000000
Limit                  100      100           20                100000
Current code           1/0      0/1          3/1               355/113
Patch                  100    1/100         19/6           99733/31746
-------------- next part --------------
A non-text attachment was scrubbed...
Name: av_reduce.diff
Type: text/x-patch
Size: 1044 bytes
Desc: 
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20061129/d879ace1/attachment.bin>