Page 8 of 11
Re: qfind - a spaceship search program
Posted: October 31st, 2024, 2:04 am
by very
i was invited to outline a method to halve the lookup tables
the idea is basically the same as scourge. instead of storing the whole lookup table for solutions
x such that
r1 r2 x evolves into
r3, you only store the first L+1 bits, and enforce the first L evolution constraints, and make another lookup table where you store the last W-L+1 bits and enforce the last W-L evolution constraints
then to look up a full width
r1 r2 r3 you look up their respective halves and take the pairs of
x that share the same center 2 bits, since they can be spliced together into a row that satisfies all evolution constraints
this is already pretty much implemented in qfind with lowbit/highbit during makerow, but would need a lot of changing of lookahead
my code is here
https://gitlab.com/terezi/scourge/-/blo ... type=heads i couldn't get it to be faster than SAT at width 22ish, but it might be a poor lookahead implementation
Re: qfind - a spaceship search program
Posted: November 27th, 2024, 12:34 am
by CARuler
can someone tell me how to make qfind upload to catagolue
Re: qfind - a spaceship search program
Posted: November 27th, 2024, 1:13 am
by Sokwe
CARuler wrote: November 27th, 2024, 12:34 am
can someone tell me how to make qfind upload to catagolue
It would be helpful if you could give more detail on what your goal is here, but qfind cannot upload to catagolue directly. You would instead need to run the output through apgsearch. Note that if you use the dump feature, you can get a list of partial results from a loaded dump file using the preview feature. Use the "--help" option in qfind to see the full list of options.
Edit: (unrelated note to self) trying to load a saved state from the following search in v2.4b causes a segfault:
Code: Select all
./qfind -r B2cen3aj4ai5aj6i/S1e2eik3enr4iq5i -w 5 -v c/8 -s a -t 3 -q 16 --dump-interval 1
Re: qfind - a spaceship search program
Posted: November 27th, 2024, 1:15 am
by confocaloid
CARuler wrote: November 27th, 2024, 12:34 am
can someone tell me how to make qfind upload to catagolue
In short, that could be done by compiling apgsearch separately, choosing something like "qfind_stdin_test" as the destination census name, and then running qfind with the output piped into apgsearch.
Here is what I did to find p3 orthogonal c/3 spaceships in the B38/S23 CA, using qfind with "-s odd -w 9".
No warranty express or implied.
Note: if you want to actually submit the spaceships (
as I did) then remove the part " -t 1 " in the last invocation. Otherwise, it will just save a log file locally (which you will be able to open with a text editor and view the apgcodes) and quit without submitting anything.
Code: Select all
# mkdir test
# cd test
# git clone https://github.com/Matthias-Merzenich/qfind.git
# cd qfind
# gcc qfind.c -O3 -fopenmp -march=native -o qfind
# cd ..
# git clone https://gitlab.com/apgoucher/apgmera.git --recursive
# cd apgmera
# ./recompile.sh --rule b38s23 --symmetry qfind_stdin_test
# cd ..
# ./qfind/qfind -r B38/S23 -v c/3o -s odd -w 9 | ./apgmera/apgluxe -t 1 -L 1 -n 10000 -i 0
Re: qfind - a spaceship search program
Posted: May 8th, 2025, 5:47 am
by vilc
I found a strange bug in qfind v2.4b. With this command (or any command with a similar rule and this combination of speed, symmetry and width):
Code: Select all
qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
The output is:
Code:
Select all
qfind v2.4b by Matthias Merzenich, 13 September 2024
Input: qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
Rule: B2ek3cij4ci/S2ce
speed: 2c/5
Width: 4
Symmetry: odd
Dump interval: 1800 seconds
Dump mode: overwrite
Queue size: 2^20
Hash table size: 2^20
Minimum deepening increment: 3
Cache memory per thread: 32 megabytes
Number of threads: 1
08/05/25 11:32:36 Starting search
08/05/25 11:32:36 Search complete.
0 spaceships found.
Maximum depth reached: 9
Longest partial result:
P¯‗;
The partial diplayed at the end is always corrupt.
I compiled qfind on Windows with gcc 13.2.0 and mingw-w64, using the command given in readme.txt.
Re: qfind - a spaceship search program
Posted: May 8th, 2025, 6:08 am
by confocaloid
vilc wrote: May 8th, 2025, 5:47 am
I found a strange bug in qfind v2.4b. [...]
Confirmed on Ubuntu with each of the following commands:
Code: Select all
# ./qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
# ./qfind -r B2ek3cij4ci/S2ce -v 2c/7 -s o -w 5
# ./qfind -r B2ek3cij4ci/S2ce -v 3c/7 -s o -w 5
Instead of a partial result, there are several "random-looking" bytes at the end, different when the test is repeated several times.
Re: qfind - a spaceship search program
Posted: May 8th, 2025, 9:57 pm
by AforAmpere
Also happens on v2.3 with the corresponding command, and width 4 or 5:
Code: Select all
qfind v2.3 by Matthias Merzenich, 19 March 2023
Input: ./qfind -r B2ek3cij4ci/S2ce -p 5 -y 2 -s o -w 5
Rule: B2ek3cij4ci/S2ce
Period: 5
Offset: 2
Width: 5
Symmetry: odd
Queue size: 2^20
Hash table size: 2^20
Minimum deepening increment: 3
Cache memory per thread: 32 megabytes
Number of threads: 1
08/05/25 21:56:27 Starting search
08/05/25 21:56:27 Search complete.
0 spaceships found.
Maximum depth reached: 10
Longest partial result:
��,0^
Re: qfind - a spaceship search program
Posted: May 9th, 2025, 12:21 am
by Sokwe
vilc wrote: May 8th, 2025, 5:47 am
I found a strange bug in qfind v2.4b. With this command (or any command with a similar rule and this combination of speed, symmetry and width):
Code: Select all
qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
The output is:
Code:
Select all
...
0 spaceships found.
Maximum depth reached: 9
Longest partial result:
P¯‗;
The partial diplayed at the end is always corrupt.
I compiled qfind on Windows with gcc 13.2.0 and mingw-w64, using the command given in readme.txt.
I've known about this bug for a long time, and it only seems to occur when the search finishes at an extremely shallow depth with no spaceships found. I suspect this is a result of printing the pattern buffer before it's been written. I intend to fix it eventually, but I consider it a low priority. Let me know if you find an example search where it occurs for a longer final partial.
Re: qfind - a spaceship search program
Posted: May 9th, 2025, 5:34 pm
by dexter1
Sokwe wrote: May 9th, 2025, 12:21 am
I've known about this bug for a long time, and it only seems to occur when the search finishes at an extremely shallow depth with no spaceships found. I suspect this is a result of printing the pattern buffer before it's been written.
Correct. Valgrind confirms that patternBuf is used before assignment:
Code: Select all
$ valgrind ./qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
.
.
09/05/25 22:50:36 Starting search
09/05/25 22:50:36 Search complete.
0 spaceships found.
Maximum depth reached: 9
Longest partial result:
==22532== Conditional jump or move depends on uninitialised value(s)
==22532== at 0x484ED19: strlen (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==22532== by 0x48EDD30: __vfprintf_internal (vfprintf-internal.c:1517)
==22532== by 0x48D779E: printf (printf.c:33)
==22532== by 0x114A0F: finalReport (common.h:3069)
==22532== by 0x116F2B: main (qfind.c:501)
file common.h line 3069 is where patternBuf is used:
Code: Select all
3068 if (params[P_LONGEST] && aborting != 3){ /* aborting == 3 means we reached ship limit */
3069 if (patternBuf) printf("Longest partial result:\n\n%s",patternBuf);
3070 else printf("No partial results found.\n");
Using gdb to run the program while watching changes in patternBuf gives the following:
Code: Select all
$ gdb qfind
.
Reading symbols from qfind...
(gdb) watch patternBuf
Hardware watchpoint 1: patternBuf
(gdb) run -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
Starting program: /home/frank/Documents/GOL/qfind/qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
qfind v2.4b by Matthias Merzenich, 21 September 2024
Input: -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
.
09/05/25 23:02:36 Starting search
Hardware watchpoint 1: patternBuf
Old value = 0x0
New value = 0x55555556d8b0 "\340\254\341\367\377\177"
0x000055555555a314 in bufferPattern (b=3, pRows=0x0, nodeRow=0, lastRow=0, printExpected=0) at /home/frank/Documents/GOL/qfind/common.h:944
944 patternBuf = (char*)malloc(((2 * MAXWIDTH + 4) * sxsAllocRows + 300) * sizeof(char));
(gdb) continue
Continuing.
09/05/25 23:03:06 Search complete.
0 spaceships found.
Maximum depth reached: 9
Longest partial result:
����[Inferior 1 (process 23201) exited normally]
(gdb)
Conclusion: The patternBuf is indeed being allocated in file common.h line 944 but it is never written into or cleared, leaving it filled with random data.
The most pragmatic way to fix this bug is by allocating the buffer using calloc. This fills the buffer with zeroes, which happen to be string terminators. Any subsequent call to a printf-like function with an uninitialized patternBuf as argument prints a null-string with length 0 instead of some random junk.
Re: qfind - a spaceship search program
Posted: August 18th, 2025, 4:05 am
by mmmmmmmmm
I have put qfind into visual studio code. How do I run it with an input? How do I run it in a different rule?
Re: qfind - a spaceship search program
Posted: August 18th, 2025, 4:36 am
by Sokwe
mmmmmmmmm wrote: August 18th, 2025, 4:05 am
I have put qfind into visual studio code. How do I run it with an input? How do I run it in a different rule?
Are you using Windows and trying to compile from the source code? In that case I would
highly recommend compiling qfind under Windows Subsystem for Linux instead. It also compiles fine using MinGW-w64. As I recall, qfind would need a very slight modification to compile with Visual Studio, because VS is a stickler for something regarding OpenMP (I can't remember the details at the moment). I think it compiles with clang with some warnings which I intend to address at some point.
Please let me know if you have any difficulty with this or if you have any further questions.
Also, I moved your post to the qfind discussion thread.
Re: qfind - a spaceship search program
Posted: August 18th, 2025, 5:09 am
by ThePlayzr
Sokwe wrote: August 18th, 2025, 4:36 am
Since you mention Visual Studio, I assume you're using Windows and trying to compile from the source code. In that case I would
highly recommend compiling qfind under Windows Subsystem for Linux instead. As I recall, qfind would need a very slight modification to compile with Visual Studio, because VS is a stickler for something regarding OpenMP (I can't remember the details at the moment). It also compiles fine using MinGW-w64.
Please let me know if you have any difficulty with this or if you have any further questions.
Also, I moved your post to the qfind discussion thread.
I am trying to do the exact same thing, funnily, so this is very helpful. I am going to try using MinGW-w64 to use it now.
Re: qfind - a spaceship search program
Posted: August 18th, 2025, 5:14 am
by Sokwe
ThePlayzr wrote: August 18th, 2025, 5:09 am
I don't think my laptop is able to do compile qfind like that
Sorry, I'm having a bit of trouble understanding. Are you using Windows? If so, is there a problem with using Windows Subsystem for Linux?
Re: qfind - a spaceship search program
Posted: August 18th, 2025, 5:18 am
by ThePlayzr
Sokwe wrote: August 18th, 2025, 5:14 am
ThePlayzr wrote: August 18th, 2025, 5:09 am
I don't think my laptop is able to do compile qfind like that
Sorry, I'm having a bit of trouble understanding. Are you using Windows? If so, is there a problem with using Windows Subsystem for Linux?
Yes, I do use windows, but I use a thinkpad laptop.
erm, how do I use mingw-w64 to compile qfind?
Re: qfind - a spaceship search program
Posted: August 18th, 2025, 5:27 am
by Sokwe
ThePlayzr wrote: August 18th, 2025, 5:18 am
how do I use mingw-w64 to compile qfind?
Again, I would primarily recommend using Windows Subsystem for Linux. However, you can install MinGW-w64 by following the instructions
here. You can then open a terminal in your qfind folder and run the installation command given in the qfind readme:
Code: Select all
gcc qfind.c -O3 -fopenmp -march=native -o qfind
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 2:22 am
by ThePlayzr
I read the instruction page, but I cannot find the 'bin' folder inside mingw-w64. I downloaded it
here. What is this version's equivalent of the 'bin' folder?
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 3:24 am
by Sokwe
ThePlayzr wrote: August 19th, 2025, 2:22 am
I read the instruction page, but I cannot find the 'bin' folder inside mingw-w64. I downloaded it
here. What is this version's equivalent of the 'bin' folder?
You seem to have downloaded only the source code. What you need is either pre-built binaries or an installer. One source of pre-built binaries is from the link given in
the tutorial. Other sources are available in the "pre-built toolchains" section of
this webpage.
Another way to install gcc is to first install
MSYS2, and then use the MSYS2 package manager to install gcc, although I've never done this myself, so I can't give further advice.
And again, I recommend Windows Subsystem for Linux (WSL2) first. I created the MinGW-w64 tutorial for those who, for whatever reason, couldn't use WSL2.
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 4:22 am
by ThePlayzr
Sokwe wrote: August 19th, 2025, 3:24 am
ThePlayzr wrote: August 19th, 2025, 2:22 am
...
You seem to have downloaded only the source code. What you need is either pre-built binaries or an installer. One source of pre-built binaries is from the link given in
the tutorial. Other sources are available in the "pre-built toolchains" section of
this webpage.
Another way to install gcc is to first install
MSYS2, and then use the MSYS2 package manager to install gcc, although I've never done this myself, so I can't give further advice.
And again, I recommend Windows Subsystem for Linux (WSL2) first. I created the MinGW-w64 tutorial for those who, for whatever reason, couldn't use WSL2.
I do not have administrator rights, which is why I am trying to use MinGW-w64. Also, do I not need the source code that I downloaded?
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 4:27 am
by Sokwe
ThePlayzr wrote: August 19th, 2025, 4:22 am
do I not need the source code that I downloaded?
No, you do not need the source code. Instead, I recommend following the instructions in
the tutorial exactly as they are written. If you have any trouble with this or any further questions, please let me know. You might also want to install Git Bash (see the previous section in the tutorial).
Edit: if you get it working, please give this post a like.
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 6:29 am
by ThePlayzr
Sokwe wrote: August 19th, 2025, 4:27 am
ThePlayzr wrote: August 19th, 2025, 4:22 am
do I not need the source code that I downloaded?
No, you do not need the source code. Instead, I recommend following the instructions in
the tutorial exactly as they are written. If you have any trouble with this or any further questions, please let me know. You might also want to install Git Bash (see the previous section in the tutorial).
Edit: if you get it working, please give this post a like.
I installed minGW-w64, put it on the path, compiled the file, I did everything. but after all that, 'your administrator has caused windows security to block this action' ughhhh whyyyyy
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 6:53 am
by Resu
ThePlayzr wrote: August 19th, 2025, 6:29 am
I installed minGW-w64, put it on the path, compiled the file, I did everything. but after all that, 'your administrator has caused windows security to block this action' ughhhh whyyyyy
Are you using a administrator account?
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 6:54 am
by ThePlayzr
Resu wrote: August 19th, 2025, 6:53 am
ThePlayzr wrote: August 19th, 2025, 6:29 am
I installed minGW-w64, put it on the path, compiled the file, I did everything. but after all that, 'your administrator has caused windows security to block this action' ughhhh whyyyyy
Are you using a administrator account?
I do not have administrator rights on this device.
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 6:59 am
by Resu
ThePlayzr wrote: August 19th, 2025, 6:54 am
I do not have administrator rights on this device.
Can you contact your administrator?
Also, are you actually allowed to install qfind on that device?
What are you doing to cause the ‘your administrator has caused windows security to block this action' message?
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 1:08 pm
by Sokwe
ThePlayzr wrote: August 19th, 2025, 6:29 am
I installed minGW-w64, put it on the path, compiled the file, I did everything. but after all that, 'your administrator has caused windows security to block this action' ughhhh whyyyyy
Can you give any more details? What are the exact steps you take that cause the error? Does the error say anything more than "your administrator has caused windows security to block this action"?
Re: qfind - a spaceship search program
Posted: August 19th, 2025, 7:30 pm
by Sokwe
I'm not really finished with qfind v2.4, but I haven't worked on it in almost a year, and in light of the above questions I decided I should at least provide a portable Windows executable for the latest version.
Here is a zip archive containing a Windows executable for x86-64 CPUs:
This was compiled under
MinGW-w64 with the MSVCRT runtime library using the following command:
Code: Select all
gcc qfind.c -static -O3 -fopenmp -march=x86-64 -o qfind
If anyone has any trouble getting this to work on their machine, please let me know.
I'm curious to know if there's a desire or need for a pre-compiled Windows executable for ARM64 CPUs. I don't actually know anything about cross-compiling for the ARM64 architecture, but if there's interest I wouldn't mind giving it a shot.