Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 7:14 PM, Michael Niedermayer wrote: > On Sat, Oct 10, 2015 at 11:32:06PM +0200, Henrik Gramner wrote: >> On Sat, Oct 10, 2015 at 11:06 PM, Ganesh Ajjanagadde >> wrote: >> > This uses Stein's binary GCD algorithm: >> >

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 8:22 PM, Michael Niedermayer wrote: > On Sun, Oct 11, 2015 at 02:13:59AM +0200, Michael Niedermayer wrote: >> On Sat, Oct 10, 2015 at 07:45:17PM -0400, Ganesh Ajjanagadde wrote: >> > On Sat, Oct 10, 2015 at 7:14 PM, Michael Niedermayer >> >

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 6:10 PM, James Darnley wrote: > On 2015-10-10 23:06, Ganesh Ajjanagadde wrote: >> ... > > Is the greatest common denominator (yes, I had to look that up) actually > used anywhere that is slow and needs to be fast? > > All the uses of 'av_gcd' found

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 11:32:06PM +0200, Henrik Gramner wrote: > On Sat, Oct 10, 2015 at 11:06 PM, Ganesh Ajjanagadde > wrote: > > This uses Stein's binary GCD algorithm: > > https://en.wikipedia.org/wiki/Binary_GCD_algorithm > > to get a reported 1.7-2.1x speedup over

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sun, Oct 11, 2015 at 02:13:59AM +0200, Michael Niedermayer wrote: > On Sat, Oct 10, 2015 at 07:45:17PM -0400, Ganesh Ajjanagadde wrote: > > On Sat, Oct 10, 2015 at 7:14 PM, Michael Niedermayer > > wrote: > > > On Sat, Oct 10, 2015 at 11:32:06PM +0200, Henrik Gramner

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 8:13 PM, Michael Niedermayer wrote: > On Sat, Oct 10, 2015 at 07:45:17PM -0400, Ganesh Ajjanagadde wrote: >> On Sat, Oct 10, 2015 at 7:14 PM, Michael Niedermayer >> wrote: >> > On Sat, Oct 10, 2015 at 11:32:06PM +0200,

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 8:37 PM, Ganesh Ajjanagadde wrote: > On Sat, Oct 10, 2015 at 8:34 PM, Ganesh Ajjanagadde wrote: >> On Sat, Oct 10, 2015 at 8:22 PM, Michael Niedermayer >> wrote: >>> On Sun, Oct 11, 2015 at 02:13:59AM +0200,

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

Hi, On Sat, Oct 10, 2015 at 6:07 PM, Ganesh Ajjanagadde wrote: > On Sat, Oct 10, 2015 at 5:45 PM, Ganesh Ajjanagadde > wrote: > > On Sat, Oct 10, 2015 at 5:32 PM, Henrik Gramner > wrote: > >> On Sat, Oct 10, 2015 at 11:06 PM, Ganesh

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 11:32:06PM +0200, Henrik Gramner wrote: > On Sat, Oct 10, 2015 at 11:06 PM, Ganesh Ajjanagadde > wrote: > > This uses Stein's binary GCD algorithm: > > https://en.wikipedia.org/wiki/Binary_GCD_algorithm > > to get a reported 1.7-2.1x speedup over

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 8:34 PM, Ganesh Ajjanagadde wrote: > On Sat, Oct 10, 2015 at 8:22 PM, Michael Niedermayer > wrote: >> On Sun, Oct 11, 2015 at 02:13:59AM +0200, Michael Niedermayer wrote: >>> On Sat, Oct 10, 2015 at 07:45:17PM -0400, Ganesh

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 5:32 PM, Henrik Gramner wrote: > On Sat, Oct 10, 2015 at 11:06 PM, Ganesh Ajjanagadde > wrote: >> This uses Stein's binary GCD algorithm: >> https://en.wikipedia.org/wiki/Binary_GCD_algorithm >> to get a reported 1.7-2.1x

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 5:45 PM, Ganesh Ajjanagadde wrote: > On Sat, Oct 10, 2015 at 5:32 PM, Henrik Gramner wrote: >> On Sat, Oct 10, 2015 at 11:06 PM, Ganesh Ajjanagadde >> wrote: >>> This uses Stein's binary GCD algorithm: >>>

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sun, Oct 11, 2015 at 12:10:39AM +0200, James Darnley wrote: > On 2015-10-10 23:06, Ganesh Ajjanagadde wrote: > > ... > > Is the greatest common denominator (yes, I had to look that up) actually > used anywhere that is slow and needs to be fast? > > All the uses of 'av_gcd' found by grep

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On 2015-10-10 23:06, Ganesh Ajjanagadde wrote: > ... Is the greatest common denominator (yes, I had to look that up) actually used anywhere that is slow and needs to be fast? All the uses of 'av_gcd' found by grep appear be dealing with timing. I see framerate, timebase, scale. I do see uses

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 07:45:17PM -0400, Ganesh Ajjanagadde wrote: > On Sat, Oct 10, 2015 at 7:14 PM, Michael Niedermayer > wrote: > > On Sat, Oct 10, 2015 at 11:32:06PM +0200, Henrik Gramner wrote: > >> On Sat, Oct 10, 2015 at 11:06 PM, Ganesh Ajjanagadde > >>

[FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

This uses Stein's binary GCD algorithm: https://en.wikipedia.org/wiki/Binary_GCD_algorithm to get a reported 1.7-2.1x speedup over Euclidean GCD on standard architectures. Have not benchmarked, so I can't comment. Note that there may be some room for optimization of the bit operations. Quick note

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sat, Oct 10, 2015 at 11:06 PM, Ganesh Ajjanagadde wrote: > This uses Stein's binary GCD algorithm: > https://en.wikipedia.org/wiki/Binary_GCD_algorithm > to get a reported 1.7-2.1x speedup over Euclidean GCD on standard > architectures. > Have not benchmarked, so I

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm

On Sun, Oct 11, 2015 at 01:14:27AM +0200, Michael Niedermayer wrote: > On Sat, Oct 10, 2015 at 11:32:06PM +0200, Henrik Gramner wrote: > > On Sat, Oct 10, 2015 at 11:06 PM, Ganesh Ajjanagadde > > wrote: > > > This uses Stein's binary GCD algorithm: > > >