Suggestion: adding primality check and prime factorisation
JaroPaska opened this issue · 3 comments
I just discovered this project and I thought this collection could benefit from implementations of algorithms like Miller-Rabin and Pollard-Rho. Thoughts?
If this does get the nod, I would love to implement this so I can practice my Rust skills.
Miller rabin is guaranteed to work on all 64 bit numbers if you test on the following set of bases: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37. I've started trying to implement it, and for the Miller test you also need fast exponentiation. However, traditional implementations of the fast exponentiation algorithm don't handle cases where the exponent < 0 (this can be calculated with modular inverses) or where base == exp == 0 (this could return None). Would you prefer it if I implemented all edge cases at the cost of the function being less clean, or if I ignored them (and perhaps made the function fail if such an edge case was presented)?
EDIT: I thought about it some more and I think it would be cleaner to ignore these edge cases (handle them via assertions) as I don't think they appear often in the contest setting, and they make using the function a bit more of a hassle (having to use match to extract the result and check for None). Apologies if I'm bothering you by the way, it's my first time properly contributing to someone else's repo.
To answer your previous question, you could always define 0^0 = 1 or whatever seems reasonable for the application, and have a comment to that effect. Anyway, the choices you made seem to work. In Field, the exponent is unsigned :)