After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 342943 - algorithm to avoid overflows when multiplying fractions
algorithm to avoid overflows when multiplying fractions
Status: RESOLVED NOTABUG
Product: GStreamer
Classification: Platform
Component: gstreamer (core)
git master
Other All
: Normal enhancement
: git master
Assigned To: GStreamer Maintainers
GStreamer Maintainers
Depends on:
Blocks:
 
 
Reported: 2006-05-25 18:25 UTC by Vincent Torri
Modified: 2006-06-01 15:56 UTC
See Also:
GNOME target: ---
GNOME version: ---



Description Vincent Torri 2006-05-25 18:25:32 UTC
as requested by Thomas, i post here a simple algorithm that try to avoid some overflows when multiplying fractions. It's only maths, no computer science.

To compute a fraction from a numerator num and a denominator den, first compute the gcd d of num and den with the Euclid algorithm. Then the resulting "simplified" fraction is (num / d, den / d).


if r1=(num1, den1) and r2=(num2, den2) are 2 fractions. I suppose that they are already simplified.

a) compute the rational r3=(num1, den2) using the simplification above
b) compute the rational r4=(num2, den1) using the simplification above
c) the result of r1 * r2 is the rational r5=(r3.num * r4.num, r3.den * r4.den) and it's no need to simplify this fraction. It's already simplified.

another way to say that : 

a) d1 = gcd(num1, den2)
b) d2 = gcd(num2, den1)
c) r1 * r2 is the fraction ( (num1 / d1) * (num2 / d2), (den1 / d2) * (den2 / d1) )

they is another algo if the fraction is multiplied by an integer only.

I don't know if multiplications of fractions are handled this way in gstreamer. Nevertheless, I hope this helps

Vincent
Comment 1 Wim Taymans 2006-06-01 15:56:20 UTC
yup, see gstvalue.c:3296 in gst_value_fraction_multiply(). could use some optimisations still, though...