ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

zfind discussion

For scripts to aid with computation or simulation in cellular automata.

Re: zfind discussion

Postby danny » June 27th, 2018, 12:36 am

Could there be a way to find puffers using ntqfind/ntzfind? Kind of like the puffer switch in gfind...

The way I could see to implement this (admittedly I've never looked at the src code of gfind, though) is to check if the ship goes through two different cycles without losing any rows the second time around, but I don't quite know.
Please stop using my full name. Refer to me as dani.

she/they

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D.
User avatar
danny
 
Posts: 901
Joined: October 27th, 2017, 3:43 pm
Location: i love to eat bees

Re: zfind discussion

Postby AforAmpere » January 30th, 2019, 6:14 pm

Is there a way to do multithreading in zfind 3.0 or later?
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 899
Joined: July 1st, 2016, 3:58 pm

Re: zfind discussion

Postby Moosey » February 1st, 2019, 6:32 pm

Where do I find an nttable.c?
Ntzfind error.png
Where do I find nttable.c?
Ntzfind error.png (9.98 KiB) Viewed 1500 times
My rules:
They can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
User avatar
Moosey
 
Posts: 827
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board.

Re: zfind discussion

Postby wildmyron » February 1st, 2019, 8:56 pm

AforAmpere wrote:Is there a way to do multithreading in zfind 3.0 or later?

There's no functional multithreading implementation available that I'm aware of. There are several possibilities for how it could be done, including merging some of the zfind3 changes into qfind. I recall rokicki mentioning that some of the changes would be tricky to merge though.

Moosey wrote:Where do I find an nttable.c?
Ntzfind error.png

Instructions here: viewtopic.php?f=9&t=2070&p=53277&hilit=Ntzfind#p53277

A better alternative is to use zfind3. See discussion earlier in this thread. viewtopic.php?p=57074#p57074
Code: https://github.com/rokicki/ntzfind
wildmyron
 
Posts: 1028
Joined: August 9th, 2013, 12:45 am

Re: zfind discussion

Postby Sokwe » February 4th, 2019, 1:18 am

wildmyron wrote:I recall rokicki mentioning that some of the changes would be tricky to merge [into qfind] though.

I think the two difficulties are the following:
  • Since the lookup table is generated as-needed, each update to the table will have to be atomic. This might slow the search early on, but I hope it would become negligible after a little while.
  • The lookahead is done slightly differently in qfind for searches faster than c/3, so the hash function needs to be changed slightly.
Anyway, qfind needs to be made more thread-safe in general. Sadly, I've been too busy to work on it.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1413
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby calcyman » February 4th, 2019, 5:03 am

Sokwe wrote:
wildmyron wrote:I recall rokicki mentioning that some of the changes would be tricky to merge [into qfind] though.

I think the two difficulties are the following:
  • Since the lookup table is generated as-needed, each update to the table will have to be atomic. This might slow the search early on, but I hope it would become negligible after a little while.
  • The lookahead is done slightly differently in qfind for searches faster than c/3, so the hash function needs to be changed slightly.
Anyway, qfind needs to be made more thread-safe in general. Sadly, I've been too busy to work on it.


Looking at the code, it seems that making the lookup table generation threadsafe should be relatively straightforward, and doesn't require locking the table for more than a nanosecond or two. In particular, there's only one line:

https://github.com/rokicki/ntzfind/blob ... d.cpp#L422

in which the new row pointer is added to the table. So that can be replaced with (pseudocode):

-- acquire mutex;
-- see whether gInd3[(row1<<width)+row2] is equal to zero;
-- if it is zero, replace it with the row pointer;
-- if it is nonzero, free the row you've just created (because another thread has already created it before you);
-- release mutex;


and the final line should return gInd3[(row1<<width)+row2] instead of row to account for the case where you've freed the row.

It's something of a 'better to ask for forgiveness than permission' approach: you generate the row, possibly unnecessarily (because another thread might be doing the same thing at the same time), and only check at the moment you add the row to the lookup table.

Also, gInd3 should be changed to an array of type std::atomic_uintptr_t just in case someone is using a processor such as ARM which lacks atomic 64-bit stores. That way, we don't need to check the mutex when reading the lookup table, because gInd3[(row1<<width)+row2] changes atomically from 0 to row.

The other (minor) change is that you need a gWork array for each thread in the program. Easiest would be to replace:

int *gWork ;
[...]
gWork = (int *)calloc(sizeof(int), 3LL << width) ;


with:

int *gWorkConcat;
[...]
gWorkConcat = (int *)calloc(sizeof(int), (3LL * n_threads) << width);


and then, inside the body of makeRow:

int *gWork = gWorkConcat + ((3LL * thread_number) << width);
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1948
Joined: June 1st, 2009, 4:32 pm

Re: zfind discussion

Postby Naszvadi » February 24th, 2019, 8:04 am

There are 32 outer-totalistic Neumann rules with 16 non-isomorphic among them, they are:

  • B0/SV:B01c2cn3c4c/S
  • B0/S1V:B01c2cn3c4c/S1e2ak3inqy4ny5e
  • B0/S0V:B01c2cn3c4c/S01c2cn3c4c
  • B0/S01V:B01c2cn3c4c/S01ce2ackn3cinqy4cny5e
  • B04/SV:B01c2cn3c4ce5c6cn7c8/S
  • B04/S1V:B01c2cn3c4ce5c6cn7c8/S1e2ak3inqy4ny5e
  • B04/S0V:B01c2cn3c4ce5c6cn7c8/S01c2cn3c4c
  • B04/S01V:B01c2cn3c4ce5c6cn7c8/S01ce2ackn3cinqy4cny5e
  • B02/SV:B01c2cein3acjkr4acikqtwz5ajkr6ei/S
  • B02/S1V:B01c2cein3acjkr4acikqtwz5ajkr6ei/S1e2ak3inqy4ny5e
  • B02/S0V:B01c2cein3acjkr4acikqtwz5ajkr6ei/S01c2cn3c4c
  • B02/S01V:B01c2cein3acjkr4acikqtwz5ajkr6ei/S01ce2ackn3cinqy4cny5e
  • B024/SV:B01c2cein3acjkr4aceikqtwz5acjkr6cein7c8/S
  • B024/S1V:B01c2cein3acjkr4aceikqtwz5acjkr6cein7c8/S1e2ak3inqy4ny5e
  • B024/S0V:B01c2cein3acjkr4aceikqtwz5acjkr6cein7c8/S01c2cn3c4c
  • B024/S01V:B01c2cein3acjkr4aceikqtwz5acjkr6cein7c8/S01ce2ackn3cinqy4cny5e

I hope my ruleconverter script is bug-free :D.

Does ntzfind support Neumann blinking and/or isotropic blinking rules? Some of the above already have known gliders (c/2, c2/4. c/12d). Are there any experiences with such kind of rules?

As a test drive, tlife is supported well (after commenting out knightship configuration macro definitions)

user@errorlevel:0:~/github.com/rokicki/ntzfind$ ./ntzfind b3/s2-i34q p5 k1 w3 a rntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind b3/s2-i34q p5 k1 w3 a r
Rule: b3/s2-i34q
Period: 5
Offset: 1
Width:  3
Symmetry: asymmetric
Depth limit: 2000
Stop search if a ship is found.
Use randomized search order.
Starting search

.o.
o.o
...
ooo
...
Length: 22
Spaceship found. (1)

Current depth: 2001
Calculations: 2070
CPU time: 0.020634 seconds
Search terminated: spaceship found.
user@errorlevel:0:~/github.com/rokicki/ntzfind$ export LC_ALL=C; ./ntzfind B01c2cein3acjkr4acikqtwz5ajkr6ei/S p4 k2 w4 u r
ntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind B01c2cein3acjkr4acikqtwz5ajkr6ei/S p4 k2 w4 u r
Rule: B01c2cein3acjkr4acikqtwz5ajkr6ei/S
Period: 4
Offset: 2
Width:  4
Symmetry: odd
Depth limit: 2000
Stop search if a ship is found.
Use randomized search order.
Starting search
Segmentation fault (core dumped)
user@errorlevel:139:~/github.com/rokicki/ntzfind$


I also observed that the above ntzfind version has difficulties with b2*/s rules, too.
Naszvadi
 
Posts: 303
Joined: May 7th, 2016, 8:53 am

Previous

Return to Scripts

Who is online

Users browsing this forum: No registered users and 2 guests