OSX Build reaches dead state

[akielaries]

When running the build commands listed in the repository on OSX (regardless of version or architecture), build reaches a dead state/infinite loop when running the GoogleTest suite part of the build process.

[sidsbrmnn]

Hi @akielaries, I took a look at this issue. Looks like rand() is the issue on macOS. It's marked obsolete. Can you assign this issue to me? I have a working fix for this.

[sidsbrmnn]

Tests for prime_test.compute_miller_rabin on Linux render these values for d, n, a, x.

DEBUG: d = 7, n = 5, a = 2, x = 3
DEBUG: d = 7, n = 1, a = 3, x = 0
DEBUG: d = 1049, n = 5, a = 2, x = 2
DEBUG: d = 2999, n = 5, a = 2, x = 3
DEBUG: d = 4, n = 2, a = 3, x = 1
DEBUG: d = 200392, n = 5, a = 2, x = 1
DEBUG: d = 90, n = 5, a = 2, x = 4

On macOS, the tests for the same give these results.

DEBUG: d = 7, n = 5, a = 2, x = 3
DEBUG: d = 7, n = 1, a = 3, x = 0
DEBUG: d = 1049, n = 5, a = 2, x = 2
DEBUG: d = 2999, n = 5, a = 2, x = 3
DEBUG: d = 4, n = 2, a = 2, x = 0

Tests hang for p.compute_miller_rabin(4, 2) as the generated a value is 2 and x is 0. This leads to a dead state/infinite loop.

[akielaries]

Sure thing! Went ahead and assigned the issue to you, feel free to submit a PR and I'll review it

[sidsbrmnn]

Hi @akielaries, can you give me some insight on how you chose the test data for compute_miller_rabin? We had second thoughts about changing the rand() calls for macOS and after some more digging, seems like the some of these test inputs are out of bounds for the function.

[akielaries]

@sidsbrmnn For the test data it is completely randomized on my end. For some cases I went with larger prime numbers to see if the miller_rabin functions would be able to handle it. Since development is done on Linux machines I was under the impression that my test cases passed as they were supposed to, is one of the cases messing things up? The test cases are located here

[sidsbrmnn]

Oh, ok. So... here's the real issue. I tried multiple builds with the macOS replacement for rand() and it still seemed to fail 3 out of 5 times.

The input to compute_miller_rabin() has some boundary condition. d is got to be an odd number and n has to be greater than 4. I see that you're handling that boundary in miller_rabin_prime() but the test data for compute_miller_rabin is not respecting that boundary.

We can go either of the two ways:

• Add the boundary condition for n to compute_miller_rabin as well, OR
• Change the test data to respect the boundary condition.

What would you prefer? Personally, I'd go with the former approach of adding boundary condition to the function, as it's a library and there's a high chance one might want to use compute_miller_rabin as a standalone implementation.

[akielaries]

This sounds great! I think adding the boundary condition to the function will be the best method. The Miller-Rabin primality test essentially checks for prime numbers given a range of integers, the sequence of these 3 miller-rabin functions is first miller_rabin -> miller_rabin_prime -> compute_miller_rabin .... this could use some updating and probably some re-naming as it was a lazy implementation on my end where we have miller_rabin as an optional call to simply print the range of prime numbers. The miller_rabin_prime method simply iterates based on the iters parameter and checks if n is prime.