Java improvements - which are likely possible in other languages

[ronlamb]

Below are some improvements I found in the Java version of the Primes code.

The following changes are for the while loop in runSeive for solution_1. Similar changes can be made to solution_2, and likely other languages that only keep an array of the odd numbers

The first for loop increments each number by one. Since all prime numbers > 2 are odd, the even numbers can be skipped, and incrementing by two reduces by half the number of values to check,

As shown below

Original for loop	New version
for (int num = factor; num <= sieveSize; num++)	for (int num = factor; num <= sieveSize; num +=2)

With the above change, the value checked inside the loop is guaranteed to be odd, the call to getBit which checks for even numbers, and if even returns true, otherwise returns the current status. Is no longer needed in the loop.

private boolean getBit(int index)
{
	return (index & 1) == 1 && !dataSet[index >> 1];
}

Instead the second half of the statement inside getBit, !dataset[index >> 1], can be substituted for the call to getBit(num)

Original check	New version
if (getBit(num))	if (!dataSet[num>>1])

Finally the loop setting all multiples of the current prime number, shown below, can also be simplified

for (int num = factor * factor; num <= sieveSize; num += factor * 2)
	clearBit(num);

Since the loop already is skipping all even values, the check for even in the call to clear bit is not needed, and the call to clearBit itself can be removed, and replaced with, **dataSet[num >> 1] = true; **.

The array is set to true, since the implementation for solution_1 uses false to signify prime and true, non-prime, to eliminate the need to all values to true first.

The loop then becomes

for (int num = factor * factor; num <= sieveSize; num += factor * 2)
	dataSet[num >> 1] = true;

The function clearBit is no longer needed, and can be deleted. Since getBit is used in the validation section, it is still needed.

The entire while loop in runSieve can then me updated as follows Including comments added.

while (factor < q)
{
	// Find the next odd false value in the dataSet, which is the next prime
	for (int num = factor; num <= sieveSize; num +=2)
	{
		if (!dataSet[num>>1])
		{
			factor = num;
			break;
		}
	}

	// Set all multiples of the current prime number to true, signifying the number is not prime
	// Multiply the factor by two to skip all even values, and set the value to true.  Since the array
	// only contains the odd numbers, shift right by 1 to divide by two before setting the flag to true
	for (int num = factor * factor; num <= sieveSize; num += factor * 2)
		dataSet[num >> 1] = true;

	// Skip to the next odd number
	factor += 2;
}

The changes below (tested in Java 16 on an Ryzen 5900X) added around 900 additional passes.

Passes: 10472, Time: 5.000000, Avg: 0.000477, Limit: 1000000, Count: 78498, Valid: true

MansenC;10472;5.000000;1;algorithm=base,faithful=yes

To

Passes: 11380, Time: 5.000000, Avg: 0.000439, Limit: 1000000, Count: 78498, Valid: true

MansenC;11380;5.000000;1;algorithm=base,faithful=yes

[ronlamb]

One thing I just noticed when I typed this is the for loop in solution_2 and solution_1 are very similar the main difference is that solution_1 has

for (var num = factor * factor; num <= this.sieveSize; num += factor * 2

While solution_2 has

for (var num = factor * 3; num <= this.sieveSize; num += factor * 2)

I tried both versions, and the times are not much different. Not sure for validating implementations, which should be used.

[rbergen]

I tried both versions, and the times are not much different. Not sure for validating implementations, which should be used.

Both can be used. The original implementations that started this project used factor * 3, but factor * factor is an optimization that's explicitly allowed under the description of the base algorithm in the contributing guidelines. I've seen reports that in certain languages, the latter increases performance by approximately 5%.

[Kinematics]

Note that while (factor < q) is incorrect. It should be while (factor <= q). If you test against a sieve size of 1000, you'll find that the < version generates an incorrect number of primes.

[ronlamb]

Good catch. The (factor < q) is currently in both solutions for Java, and likely other languages.

After looking at the code a bit, I noticed that the while loop is hiding a for loop. So I changed the code to for loop. I didn't notice a difference in speed, but it makes it a little cleaner.

public void runSieve()
{
	int q = (int) Math.sqrt(sieveSize);

	for (int factor = 3; factor <= q; factor += 2) {
		// Find the next odd false number, which signifies a prime
		for (int num = factor; num <= sieveSize; num +=2)
		{
			if (!dataSet[num>>1])
			{
				factor = num;
				break;
			}
		}

		// Set all multiples of the current prime number to true, signifying the number is not prime
		// Multiply the factor by two to skip all even values, and set the value to true.  Since the array
		// only contains the odd numbers, shift right by 1 to divide by two before setting the flag to true
		for (int num = factor * factor; num <= sieveSize; num += factor << 1)
			dataSet[num >> 1] = true;
	}
}