Benchmarking? AKS Primality Test? about sympy-paper HOT 5 CLOSED

This sounds like an issue to be brought up in symengine issues list. I don't think it is relevant to the paper as it stands. The paper isn't even about symengine.

from sympy-paper.

I realize the issue is closed, but for future discussion.

"Full AKS" needs better definition. The algorithm from the original AKS paper? The revised (primality_v6) paper that has Lenstra's improvements? Other improvements such as Voloch or Bernstein 2003 (which run many orders of magnitude faster)?

In my experience, many AKS implementations are incorrectly implemented, making the benchmarking results of dubious merit. This of course applies to most software, but AKS is typically so glacially slow that people don't want to wait hours, days, or weeks for even a single trivially-small number to complete, so they often don't properly test.

The majority of the time is in the many modular polynomial congruency tests. These can be run in parallel, which would give some measure of scalability. The tests themselves boil down to doing modular polynomial squaring / multiplication. Implementations differ, which would make scalability comparisons tricky. E.g. binary segmentation boils the problem down to large integer multiplication, which will perform differently than a loop doing operations per polynomial term (the former is faster with GMP).

This isn't the right venue to have a conversation about this, but some things to consider for when you open it somewhere else.

from sympy-paper.

@danaj Thanks for the info, but I think you should open this issue in the SymEngine and/or SymPy benchmarks repository. I closed it because I don't think this is within scope of this paper.

from sympy-paper.

Oh sorry, I didn't realize that someone else opened this issue. Whoever cares about it should open the conversation where appropriate.

from sympy-paper.

Yes, somewhere else is more appropriate. I thought the comments provided some reasons why I believe this isn't a small task that would be appropriate to add to the paper without a lot more thought and work, even assuming it was decided to be relevant.

from sympy-paper.