apgsearch v3.1

For general discussion about Conway's Game of Life.
User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: apgsearch v3.1

Post by praosylen » 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.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

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

Re: apgsearch v3.1

Post by 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.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Post by 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!

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

Re: apgsearch v3.1

Post by 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.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Post by 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!

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

Re: apgsearch v3.1

Post by 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.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Post by 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
biggiemac
Posts: 515
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: apgsearch v3.1

Post by 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.

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

Re: apgsearch v3.1

Post by 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.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Post by 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!

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

Re: apgsearch v3.1

Post by 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:

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

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

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

Post by David » October 6th, 2016, 9:45 am

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.

User avatar
muzik
Posts: 5614
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: apgsearch v3.1

Post by muzik » November 27th, 2016, 1:49 pm

Professor and cloverleaf interchange haven't been named in catagolue yet.

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

Re: apgsearch v3.1

Post by David » November 28th, 2016, 12:58 am

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

Re: apgsearch v3.1

Post by drc » November 28th, 2016, 2:02 am

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 :shock:

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: apgsearch v3.1

Post by 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.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Post by 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
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: apgsearch v3.1

Post by 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.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v3.1

Post by 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
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: apgsearch v3.1

Post by 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

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

Re: apgsearch v3.1

Post by 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?

drc
Posts: 1664
Joined: December 3rd, 2015, 4:11 pm

Re: apgsearch v3.1

Post by 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.

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

Re: apgsearch v3.1

Post by 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

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

Re: apgsearch v3.1

Post by 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.

Post Reply