search

flintlib / arb

Arb has been merged into FLINT -- use https://github.com/flintlib/flint/ instead
http://arblib.org/
GNU Lesser General Public License v2.1
456 stars 137 forks source link

Compute bin_uiui via Flint for small n #383

Open albinahlback opened 2 years ago

albinahlback commented 2 years ago

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 commented 2 years ago

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

albinahlback commented 2 years ago

Does it fail because MPIR might be used?

albinahlback commented 2 years ago

Does this look good @fredrik-johansson ?

fredrik-johansson commented 2 years ago

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.

albinahlback commented 2 years ago

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

albinahlback commented 2 years ago

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.