11 ms·

The Solovay–Strassen and Miller–Rabin tests, which are fast and accurate, but not easy to implement: the former requires understanding the Legendre and Jacobi s

The Solovay–Strassen and Miller–Rabin tests, which are fast and accurate, but not easy to implement: the former requires understanding the Legendre and Jacobi symbols (arcane mathematical concepts) and the latter requires an efficient factorisation algorithm. Its very frustrating how often this comes up: an answer is well known but "hard to implement". The answer here should have clearly been "so then I used Solovay–Strassen and Miller–Rabin". You'd think there would be SOME sample code out there or that translating the math wouldn't be too difficult, yet I often run into this problem myself. The divide between mathematical notation, or perhaps the "language of CS papers" and actual code is distressing.

blake8086 15y ago
I too am very frustrated with this problem. I would love a library to implement temporal-difference learning, but I can't implement it from the papers describing it. What could I or others do about this problem?
- tolmasky 15y ago
  I'm not sure, an easy biased answer from our side is that papers should include pseudo code closer to what we actually use to code (the flip side being we should learn more math). However, a particularly frustrating example was one paper that did actually code up what they were talking about to test it, but didn't include the code in the paper at all (instead just graphs of the results). I think there is a general feeling that the code is all "implementation details" and not as important as the theory/proof/etc, which is very unfortunate.
elemeno 15y ago
Miller-Rabin isn't that hard to implement - it just needs some reasonable maths skills related to modular arithmetic, and a copy of Knuth for fast versions of some algorithms helps a lot as well. I've stuck a very simple version (in C#) here - https://github.com/elemeno/SimpleMillerRabin/blob/master/SimpleMillerRabin/MillerRabin.cs https://github.com/elemeno/SimpleMillerRabin/blob/master/Sim...
- nhaehnle 15y ago
  I agree. Implementing the Miller-Rabin algorithm is one of the homework assignments in the Computer Algebra course we give here. In fact, once you've got the necessary concepts from group theory and modular arithmetic down, the algorithm itself is actually quite simple (it's the correctness proof that has a subtle and clever idea). When the author was talking about the "Project Triangle" in the context of primality testing, I thought he was going to bring up AKS!

blake8086 15y ago

I too am very frustrated with this problem. I would love a library to implement temporal-difference learning, but I can't implement it from the papers describing it. What could I or others do about this problem?

tolmasky 15y ago
I'm not sure, an easy biased answer from our side is that papers should include pseudo code closer to what we actually use to code (the flip side being we should learn more math). However, a particularly frustrating example was one paper that did actually code up what they were talking about to test it, but didn't include the code in the paper at all (instead just graphs of the results). I think there is a general feeling that the code is all "implementation details" and not as important as the theory/proof/etc, which is very unfortunate.

elemeno 15y ago

Miller-Rabin isn't that hard to implement - it just needs some reasonable maths skills related to modular arithmetic, and a copy of Knuth for fast versions of some algorithms helps a lot as well. I've stuck a very simple version (in C#) here - https://github.com/elemeno/SimpleMillerRabin/blob/master/SimpleMillerRabin/MillerRabin.cs https://github.com/elemeno/SimpleMillerRabin/blob/master/Sim...

nhaehnle 15y ago
I agree. Implementing the Miller-Rabin algorithm is one of the homework assignments in the Computer Algebra course we give here. In fact, once you've got the necessary concepts from group theory and modular arithmetic down, the algorithm itself is actually quite simple (it's the correctness proof that has a subtle and clever idea). When the author was talking about the "Project Triangle" in the context of primality testing, I thought he was going to bring up AKS!