Anonymous user
Talk:Miller–Rabin primality test: Difference between revisions
→The pseudo-code from Wikipedia is [allegedly] broken
Line 57:
:: Thanks that seems to have fixed Run Basic, I've tried quite a few different numbers and it seems to be correct. I noticed PureBasic was doing almost exactly the same thing and from looking at the pseudocode I thought it was wrong. I wonder how these two Basic languages produced similar errors, maybe someone copied and didn't check the output. [[User:Bearded badger|Bearded badger]] ([[User talk:Bearded badger|talk]])
::: I haven't run the PureBasic code, but it looks like it does the base selection correctly (2 to n-2, albeit the pseudocode is 2 to n-1, so we should test input = 3) and has a continue to skip the test if x=1 or x=n-1. These were the two issues that weren't right with RunBasic. The Liberty Basic example has 200 lines of test cruft but the actual loop is broken in that it runs 11 iterations of Miller-Rabin all with the same base (7). It also looks broken in that it doesn't properly skip the loop if r = n-1. If we remove the optimization of checking small factors at the beginning, I believe it will fail if given 31 and a base of 3. IMO it should be written without this optimization and with far less code.
| |||