On Sat, Jun 13, 2020 at 02:25:21PM +0000, Uknown via Digitalmars-d wrote: [...]
> I was doing some competitive programming last month and fast-gcd came
> up, this was the fastest I found back then:
> https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/
> 
> Of course it turned out the actual fast approach to my problem was to skip the gcd calculations entirely, because they were irrelevant, but that blog post may help you.

Funnily enough, I did read that article before posting it, and I did check the disassembly that it was using the bsr instruction rather than a loop.  Unfortunately, the gcd computations still occupy about 51% of total runtime.

Probably I need to think about some way of reducing the number of gcd calculations, since the gcd computation itself is already maxed out in terms of optimization AFAICT.


T

-- 
"I'm running Windows '98." "Yes." "My computer isn't working now." "Yes, you already said that." -- User-Friendly

On Monday, 15 June 2020 at 16:45:01 UTC, H. S. Teoh wrote:
> On Sat, Jun 13, 2020 at 02:25:21PM +0000, Uknown via Digitalmars-d wrote: [...]
> [...]
> need to think about some way of reducing the number of gcd calculations, since the gcd computation itself is already maxed out in terms of optimization AFAICT.
>
>
> T

I didn't notice your reply, but if you haven't solved this yet, you could try this:

Make a simple recursive gcd implementation and memoize it. It might work better than any other implementation (depending on the numbers in question and the data set size)