arb icon indicating copy to clipboard operation
arb copied to clipboard

Compute bin_uiui via Flint for small n

Open albinahlback opened this issue 4 years ago • 6 comments

Big speedup for smaller n and increased precision due to not using floating point precision.

Let me know if you want any timings for this.

albinahlback avatar Oct 18 '21 15:10 albinahlback

Sorry. Didn't include flint/fmpz.h the first time and didn't include the prefix flint/ the second time.

albinahlback avatar Oct 18 '21 16:10 albinahlback

Does it fail because MPIR might be used?

albinahlback avatar Oct 19 '21 11:10 albinahlback

Does this look good @fredrik-johansson ?

albinahlback avatar Dec 21 '21 12:12 albinahlback

It's ok, but I'd like to see cutoffs based on n, k and the precision.

Computing bin(n, k) via GMP should be faster even for huge n, if k is small or if log2(bin(n, k)) is less than some small multiple of prec.

It would be nice if also arb_bin_ui called the same algorithm when n is a small integer.

fredrik-johansson avatar Jan 14 '22 14:01 fredrik-johansson

Yes, that's true! Thanks for your input.

albinahlback avatar Jan 14 '22 14:01 albinahlback

I haven't tested the code yet, but I think the thoughts are solid.

I profiled with 10 bits in order to give the original code an advantage, and found that the bounds in the code are pretty good estimates for when the new version is faster. I had to do some extra code in case that ulong != unsigned long and in case that FLINT_BITS != 64.

albinahlback avatar Feb 26 '22 13:02 albinahlback