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

apgsearch v3.1

For general discussion about Conway's Game of Life.

Re: apgsearch v3.1

Postby A for awesome » September 3rd, 2016, 9:50 pm

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
User avatar
A for awesome
 
Posts: 1673
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: apgsearch v3.1

Postby David » September 11th, 2016, 4:51 am

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.
David
 
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: apgsearch v3.1

Postby calcyman » September 11th, 2016, 5:56 am

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!
User avatar
calcyman
 
Posts: 1832
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Postby David » September 11th, 2016, 6:39 am

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.
David
 
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: apgsearch v3.1

Postby calcyman » September 11th, 2016, 2:43 pm

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!
User avatar
calcyman
 
Posts: 1832
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Postby David » September 12th, 2016, 10:37 am

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.
David
 
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: apgsearch v3.1

Postby calcyman » September 12th, 2016, 11:30 am

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!
User avatar
calcyman
 
Posts: 1832
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Postby biggiemac » September 12th, 2016, 2:05 pm

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.
User avatar
biggiemac
 
Posts: 503
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: apgsearch v3.1

Postby David » September 13th, 2016, 10:38 am

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.
David
 
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: apgsearch v3.1

Postby calcyman » September 13th, 2016, 11:48 am

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!
User avatar
calcyman
 
Posts: 1832
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Postby David » October 6th, 2016, 4:29 am

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:
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:
make: g++: Couldn't find the command.
make: *** [main.o] Error 127
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.
David
 
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: apgsearch v3.1

Postby Rich Holmes » October 6th, 2016, 7:29 am

You appear not to have the g++ compiler installed. Try

sudo apt-get update && sudo apt-get install build-essential
Rich Holmes
 
Posts: 55
Joined: October 31st, 2015, 1:13 am

Re: apgsearch v3.1

Postby David » October 6th, 2016, 9:45 am

Rich Holmes wrote:You appear not to have the g++ compiler installed. Try

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.
David
 
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: apgsearch v3.1

Postby muzik » November 27th, 2016, 1:49 pm

Professor and cloverleaf interchange haven't been named in catagolue yet.
waiting for apgsearch to support one-dimensional rules
muzik
 
Posts: 2963
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: apgsearch v3.1

Postby David » November 28th, 2016, 12:58 am

It appears Apgsearch doesn't separate pseudo still lifes properly:
https://catagolue.appspot.com/object/xs54_o8w8ko0ok21jz012460uiiu0rahzxg0ga6y256zx11/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.
David
 
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: apgsearch v3.1

Postby drc » November 28th, 2016, 2:02 am

David wrote:It appears Apgsearch doesn't separate pseudo still lifes properly:
https://catagolue.appspot.com/object/xs54_o8w8ko0ok21jz012460uiiu0rahzxg0ga6y256zx11/b3s23
The two boats should be separated as well as the other two.

That is...strange, to say the least :shock:
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: apgsearch v3.1

Postby GUYTU6J » December 3rd, 2016, 11:30 am

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.
Welcome to share your ideas about
etymology of names!
User avatar
GUYTU6J
 
Posts: 347
Joined: August 5th, 2016, 10:27 am
Location: outside Plain of Life

Re: apgsearch v3.1

Postby calcyman » December 4th, 2016, 10:32 am

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!
User avatar
calcyman
 
Posts: 1832
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Postby Saka » December 5th, 2016, 3:33 am

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.
If you're the person that uploaded to Sakagolue illegally, please PM me.
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2624
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: apgsearch v3.1

Postby calcyman » December 5th, 2016, 3:35 am

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!
User avatar
calcyman
 
Posts: 1832
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Postby Saka » December 5th, 2016, 3:52 am

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
If you're the person that uploaded to Sakagolue illegally, please PM me.
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2624
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: apgsearch v3.1

Postby rokicki » December 7th, 2016, 4:34 pm

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?
rokicki
 
Posts: 48
Joined: August 6th, 2009, 12:26 pm

Re: apgsearch v3.1

Postby drc » December 7th, 2016, 4:58 pm

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.
This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.)
Current rule interest: B2ce3-ir4a5y/S2-c3-y
User avatar
drc
 
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm
Location: creating useless things in OCA

Re: apgsearch v3.1

Postby BlinkerSpawn » December 7th, 2016, 5:10 pm

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]

Image
User avatar
BlinkerSpawn
 
Posts: 1808
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: apgsearch v3.1

Postby David » December 29th, 2016, 2:57 am

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.
David
 
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

PreviousNext

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 1 guest