![](/static/253f0d9b/assets/icons/icon-96x96.png)
![](https://programming.dev/pictrs/image/1f7e5534-88d3-4d6f-bc57-7cda9553890f.webp)
Apparently generating “Finite Projective Planes”. For context on how I got here, I went camping with my family and brought the game Spot It. My brother was analyzing it and came up with the same type of pattern.
When we got home he made a python script to generate these boards, but it was quite slow, so he half joked asking me to rewrite it in Rust.
I kinda struggled a bit since I didn’t fully understand what it was doing. Near the end I even got a segfault using safe code😃! (i was spawning a thread with a large stack size, and allocating huge slices on its stack, rather than you know… boxing the slice Lol.) When I finally got it working, it ended up being in the ballpark of a 23x speedup. Not bad for changing the language choice!
There’s lots of room for improvement left for sure. The algorithm could benefit with some running statistics about cols/rows and the algorithm itself is quite naïve and could maybe be improved too :P
More progress on the Finite Projective Plane (incidence matrix) generation from last week. There already exists an algorithm to generate boards of order p+1 where p is prime. It is stateless, so with CUDA we can generate huge boards in seconds since all you need is the x, y position and board size. 258x258 under 3s!
However, p+1 isn’t the only sequence. It seems by our observations that the fermat numbers also generate valid boards, using our “naïve” algorithm.
Unfortunately 3x3, 5x5, and 17x17 might not contain all the nuggets of generality to find a nice algorithm like the p+1, so we’re gonna generate the next up: 257x257. We’ve been improving the naïve algorithm since it is too slow. (The resulting image would be 65793x65793)
true
elements would be using row and column indexes. This is okay because of the constraint which limits how manytrue
elements can be in a row/columnslice::contains
, useslice::binary_search(...).is_ok()
Next steps: