PHP Solution 2 with Bitwise storage.

[sqonk]

A ChatGPT-assisted solution for PHP with impressive results.

Description

This solution attempts to boost the performance out of PHP significantly, by using anything that will allow the interpreter and the Opcache JIT to precompile where possible.

The prime count storage utilises bitwise operations, as with many other high performance solutions for other languages. However, PHP has a limitation with regard to its type handling, and the maximum size it can allocate for a single integer. And so in my experiments simply replacing an array of bools with a singular int will only output the correct count for a sieve of 100 or 10.

This solution instead runs a series of ints as storage for every 100 units, storing the whole lot in an array.

Finally, of particular note (especially after the latest episode of Dave's Garage) is the core algorithm in this solution is heavily influenced and aided by ChatGPT, which assisted over many iterations of trial and error in producing a workable solution.

@rbergen I believe this solution to be both faithful and inline with the base algorithm. Please glance over the main class, if you feel so inclined, to confirm.

Contributing requirements

• [x] I read the contribution guidelines in CONTRIBUTING.md.
• [x] I placed my solution in the correct solution folder.
• [x] I added a README.md with the right badge(s).
• [x] I added a Dockerfile that builds and runs my solution.
• [x] I selected drag-race as the target branch.
• [x] All code herein is licensed compatible with BSD-3.

[rbergen]

@sqonk Thank you for your submission.

I've reviewed it, and I see the following:

• The class allocates an array with int values, to the number of the sieve size divided by 100. As the algorithm seems to aim to mark off odd multiples of factors only, this would allow for enough bit space on a 64-bit system, but it is also rather wasteful. This is because of every 64 bits available per int, only 50 would be used. I'm not going to make up my mind right now if I find this over-allocation "excessively wasteful", due to the following points.

• The algorithm implemented in this solution is not the base algorithm. Going back to the definition of that, quoting from the contributing guidelines, the first bullets are as follows:

  • The algorithm uses an outer loop, in which two operations are performed:
    • searching for the next prime in the sieve, and
    • clearing this prime's multiples in the sieve.
  • In order to allow for idiomatic code, it is permissible to perform these steps in either order, provided the results are correct.
  • When seeking factors (the first operation), the algorithm sequentially checks all odd numbers, starting at 3.

  The algorithm in this solution does not seek factors by sequentially checking all odd numbers, starting at 3. Instead, it uses a calculative approach in the isComposite() function. In that, the function uses knowledge that 3 is a prime number, which is also not allowed. The only factor for which the use of prior knowledge is allowed, is 2. Based on this, I'd say the algorithm should be marked as "other".

• When looking at the multiple marking loop in the compute() function, I don't think it works. What it does is mark each factor - or actually, factor modulo 100 - once per array member, starting at the factor squared. As there are (sieve size + 1) / 100 array members, as captured in the rbs variable, that's approximately 100 times too few for lower factors and missing 100% for factors over 100; that being the square root of 1,000,000 / 100. Furthermore, the fact it performs a bit shift of factor modulo 100 to set the actual bit in the array member means that for factors with a modulo 100 between 63 and 100, the bit is shifted outside of the int it is supposed to be set in.

• The fact that the count() function doesn't notice that the sieve algorithm doesn't work is because it doesn't count the number of unset bits in the sieve array. Instead, it uses the isComposite() function to establish for each number under the sieve limit if it is a prime number or not.

As the solution does not currently implement a functioning prime sieve, I can't merge this. I'll leave it up to you whether you want to change the PR to make the solution work, or close it. If you do want to move forward with submitting a bit-mapped PHP solution, then please:

• consider using all bits available in the sieve array you allocate
• take note of the earlier comment about the requirements for a base algorithm implementation - if that is what you are aiming for
• write the count routine/function such that it actually counts set/unset bits in the computed sieve space

Finally, in your PR description, you refer to Dave's last video. I'd like to note that it is true that he created a number of prime sieve implementations with the aid of ChatGPT. However, those implementations were not vetted for inclusion in this project, as that wasn't the point of the video. That means they should not be used as a reference for a "faithful, base" implementation.

[sqonk]

@rbergen Thank you for your comprehensive feedback. I will review and see what can be done.

[sqonk]

I am going to close this off for now. Besides the faults you mention, I have found another critical flaw in the algorithm. I fixed it for the sake of the exercise but not without the cost of the speed.

I am exploring other solutions but they are likely to be different enough that they should be submitted under a seperate request.