How to squeeze more performance out of gcd?

H. S. Teoh hsteoh at quickfur.ath.cx
Mon Jun 15 16:45:01 UTC 2020


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


More information about the Digitalmars-d mailing list