GNOME Bugzilla – Bug 342943
algorithm to avoid overflows when multiplying fractions
Last modified: 2006-06-01 15:56:20 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
yup, see gstvalue.c:3296 in gst_value_fraction_multiply(). could use some optimisations still, though...