I have brute forced my wait into a solution by doing performance analysis and thinking of clever ways to reduce the calculations which you have also done.
(Side note, when doing performance analysis/debugging I noticed that I had bug on my optimizations which you could also double check)
Still, there are generic ways to improve performance of any algorithm which you could try.