## apgsearch v3.1

For general discussion about Conway's Game of Life.
A for awesome
Posts: 1949
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1
Contact:

### Re: apgsearch v3.1

https://catagolue.appspot.com/haul/b3s/C1?committed=2
This would suggest that Catagolue does not accept hauls containing zero objects. This greatly skews the statistics for this rule, because, from the times of submission, it appears that most hauls produce zero objects, meaning that the results displayed on Catagolue show a much greater frequency of objects than actually exists.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

### Re: apgsearch v3.1

In my computer, parallelization makes apgmera to run slower. Are you sure apgmera can be parallelized properly?
I am using Intel Core i7-2670QM, and Windows 10 Pro 64bit.
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

calcyman
Posts: 2126
Joined: June 1st, 2009, 4:32 pm

### Re: apgsearch v3.1

David wrote:In my computer, parallelization makes apgmera to run slower. Are you sure apgmera can be parallelized properly?
I am using Intel Core i7-2670QM, and Windows 10 Pro 64bit.
Yes, Windows has some difficulty with OpenMP parallelisation (unlike Linux, for instance). A suggested workaround is to run N single-core instances of apgmera; this is what biggiemac did on his Windows machines.
What do you do with ill crystallographers? Take them to the mono-clinic!

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

### Re: apgsearch v3.1

calcyman wrote: Yes, Windows has some difficulty with OpenMP parallelisation (unlike Linux, for instance). A suggested workaround is to run N single-core instances of apgmera; this is what biggiemac did on his Windows machines.
Well, that is parallel, but not concurrent. I can't expect any speed improval from it.
What about using the standard parallelized algorithms?
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

calcyman
Posts: 2126
Joined: June 1st, 2009, 4:32 pm

### Re: apgsearch v3.1

David wrote: Well, that is parallel, but not concurrent. I can't expect any speed improval from it.
I don't understand -- if you have n instances running on separate cores, then you'll produce n times as many soups per unit time.
What do you do with ill crystallographers? Take them to the mono-clinic!

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

### Re: apgsearch v3.1

calcyman wrote: I don't understand -- if you have n instances running on separate cores, then you'll produce n times as many soups per unit time.
Suppose that the time complexity of apgmera is O(f(n)). As I have 4 cores, the time complexity would be O(f(n) / 4), but by the definition of big O notation, the time complexity falls back to O(f(n)).
If you use concurrent algorithms, I can expect improval in time complexity. For example, for a sorting algorithm, it's time complexity would be O(n log n) if it is neither parallel nor concurrent, but it could be O(log³ n), O(log² n), or even O(log n) if it is parallel and concurrent.
You can use the thread support library, or if possible, the parallelism TS.
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

calcyman
Posts: 2126
Joined: June 1st, 2009, 4:32 pm

### Re: apgsearch v3.1

David wrote:
Suppose that the time complexity of apgmera is O(f(n)).
What is n?
What do you do with ill crystallographers? Take them to the mono-clinic!

biggiemac
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

### Re: apgsearch v3.1

All apgsearch is doing is many independent iterations of the same task - evolve random soup and census objects. The operative word there is "independent," which differentiates it from the sorting algorithm you mentioned. Soups need to share no information. As such, there is no way to have a better asymptotic complexity using a finite number of cores, just speed things up by a constant factor as Adam mentioned.
Physics: sophistication from simplicity.

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

### Re: apgsearch v3.1

calcyman wrote:What is n?
Whatever n is, the point is the time complexity cannot be improved by just speeding things up by a constant factor.
biggiemac wrote:All apgsearch is doing is many independent iterations of the same task - evolve random soup and census objects. The operative word there is "independent," which differentiates it from the sorting algorithm you mentioned. Soups need to share no information. As such, there is no way to have a better asymptotic complexity using a finite number of cores, just speed things up by a constant factor as Adam mentioned.
But within a single soup, there might be a way to have a better complexity. Generate a random soup with parallelism and concurrency, evolve it with parallelism and concurrency, census objects with parallelism and concurrency, etc.
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

calcyman
Posts: 2126
Joined: June 1st, 2009, 4:32 pm

### Re: apgsearch v3.1

A soup takes O(1) time to run; the only possible improvements are those that reduce the constant factor.

Also (speaking of algorithms more generally), if you have k cores, you can't get any better than a k-fold time improvement over a single-core machine. In many cases, even that is optimistic (see Amdahl's law).
What do you do with ill crystallographers? Take them to the mono-clinic!

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

### Re: apgsearch v3.1

Hello, I am now a Linux user. Specifically, Linux Mint 17.3 'Rosa', MATE 64-bit.
I've installed apgmera and tried to compile it, but I get the following error message:

Code: Select all

ndos@AcerAspireONE ~/바탕화면/apgmera $bash recompile.sh Skipping updates; use --update to update apgmera automatically. Rule unspecified; assuming b3s23. Symmetry unspecified; assuming C1. Configuring rule b3s23; symmetry C1 Valid rulestring: b3s23 Valid symmetry: C1 Rule integer: 6152 Rule circuit: [-131-124-450-014-672] Rule integer: 6152 Rule circuit: [-131-124-450-014-672] Rule integer: 6152 Rule circuit: [-131-124-450-014-672] Success! g++ -c -Wall -O3 -march=native -fopenmp -DUSE_OPEN_MP main.cpp -o main.o make: g++: 명령을 찾지 못했음 make: *** [main.o] 오류 127  The last two lines can be translated to: Code: Select all make: g++: Couldn't find the command. make: *** [main.o] Error 127  Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki. Rich Holmes Posts: 55 Joined: October 31st, 2015, 1:13 am ### Re: apgsearch v3.1 You appear not to have the g++ compiler installed. Try Code: Select all sudo apt-get update && sudo apt-get install build-essential David Posts: 212 Joined: November 3rd, 2009, 2:47 am Location: Daejeon, South Korea ### Re: apgsearch v3.1 Rich Holmes wrote:You appear not to have the g++ compiler installed. Try Code: Select all sudo apt-get update && sudo apt-get install build-essential Well, since I had already updated the system, I typed only "sudo apt-get install build-essential", and that worked. Thank you. And I can now do parallel processing practically. Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki. muzik Posts: 3772 Joined: January 28th, 2016, 2:47 pm Location: Scotland ### Re: apgsearch v3.1 Professor and cloverleaf interchange haven't been named in catagolue yet. Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace! David Posts: 212 Joined: November 3rd, 2009, 2:47 am Location: Daejeon, South Korea ### Re: apgsearch v3.1 It appears Apgsearch doesn't separate pseudo still lifes properly: https://catagolue.appspot.com/object/xs ... zx11/b3s23 The two boats should be separated as well as the other two. Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki. drc Posts: 1664 Joined: December 3rd, 2015, 4:11 pm Location: creating useless things in OCA ### Re: apgsearch v3.1 David wrote:It appears Apgsearch doesn't separate pseudo still lifes properly: https://catagolue.appspot.com/object/xs ... zx11/b3s23 The two boats should be separated as well as the other two. That is...strange, to say the least \100\97\110\105 GUYTU6J Posts: 890 Joined: August 5th, 2016, 10:27 am Location: 中国 ### Re: apgsearch v3.1 I have a vague idea:use apgsearch to generate a random string,encode it into a QR code,then treat it like a normal soup in apgsearch. Sorry but I prefer to contribute to cellular automata anonymously, so I made up a random string for my username. -GUYTU6J calcyman Posts: 2126 Joined: June 1st, 2009, 4:32 pm ### Re: apgsearch v3.1 GUYTU6J wrote:I have a vague idea:use apgsearch to generate a random string,encode it into a QR code,then treat it like a normal soup in apgsearch. That was my original idea, but I chose SHA-256 for cryptographic security: it's impossible to reverse-engineer (say) a loafer into a trivial predecessor and submit it as part of a haul. What do you do with ill crystallographers? Take them to the mono-clinic! Saka Posts: 3138 Joined: June 19th, 2015, 8:50 pm Location: In the kingdom of Sultan Hamengkubuwono X ### Re: apgsearch v3.1 calcyman wrote: GUYTU6J wrote:I have a vague idea:use apgsearch to generate a random string,encode it into a QR code,then treat it like a normal soup in apgsearch. That was my original idea, but I chose SHA-256 for cryptographic security: it's impossible to reverse-engineer (say) a loafer into a trivial predecessor and submit it as part of a haul. No, that is not his idea, I think. I think he means to generate a random string, make a QR code with that random string and use the QR code as the soup. Airy Clave White It Nay Code: Select all x = 17, y = 10, rule = B3/S23 b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)

calcyman
Posts: 2126
Joined: June 1st, 2009, 4:32 pm

### Re: apgsearch v3.1

Saka wrote:
calcyman wrote:
GUYTU6J wrote:I have a vague idea:use apgsearch to generate a random string,encode it into a QR code,then treat it like a normal soup in apgsearch.
That was my original idea, but I chose SHA-256 for cryptographic security: it's impossible to reverse-engineer (say) a loafer into a trivial predecessor and submit it as part of a haul.
No, that is not his idea, I think. I think he means to generate a random string, make a QR code with that random string and use the QR code as the soup.
Yes, that's what I meant. But you can construct a QR code which is also a loafer predecessor, and then compute the string which yields that particular QR code. Then submit a haul to Catagolue containing that string, and the census will mistakenly believe that a loafer has occurred naturally.
What do you do with ill crystallographers? Take them to the mono-clinic!

Saka
Posts: 3138
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

### Re: apgsearch v3.1

calcyman wrote: Yes, that's what I meant. But you can construct a QR code which is also a loafer predecessor, and then compute the string which yields that particular QR code. Then submit a haul to Catagolue containing that string, and the census will mistakenly believe that a loafer has occurred naturally.
Ah, I see
Airy Clave White It Nay

Code: Select all

x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o\$4bob2o2bobobo!

(Check gen 2)

rokicki
Posts: 54
Joined: August 6th, 2009, 12:26 pm

### Re: apgsearch v3.1

How many distinct 16x16 soups are there of the two different x8 symmetries?

I calculate 2^36, or about 70B.

Haven't we already covered most of this space, with high probability? We are above
the 100B mark for both symmetries.

Or is this just well known and understood and people are focusing on other symmetries?

drc
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

### Re: apgsearch v3.1

rokicki wrote:How many distinct 16x16 soups are there of the two different x8 symmetries?
We use 32x32 for those, though.
Edit: Ah , disregard i'm an idiot.
Last edited by drc on December 7th, 2016, 6:01 pm, edited 1 time in total.
\100\97\110\105

Posts: 1938
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

### Re: apgsearch v3.1

drc wrote:
rokicki wrote:How many distinct 16x16 soups are there of the two different x8 symmetries?
We use 32x32 for those, though.
That's an important point: All symmetries (excl. D8 I think) are based off of a 16x16 soup with additional copies translated, rotated, and superimposed upon each other accordingly.
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

### Re: apgsearch v3.1

Is there any limit to the number of soups? I've been running apgsearch for Day & Night [b3678s34678].
The haul of 10000 soups is uploaded, but the haul of 100000000 soups is not.
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.