3

After reading about the HashLife algorithm, I found that it runs in O(log n). The Game of Life is also Turing Complete, so in theory we should be able to run any algorithm on a "computer" constructed in GoL.

As a consequence of HashLife's time complexity, could algorithms run faster? e.g. if an algorithm takes 10 seconds to run on a pc, could it run faster in HashLife on that same pc?

An example: An algorithm running takes a 1000 instructions to run. A certain computer can process 1 instruction per second. So that algorithm takes a 1000 seconds to run.

Now, if we take that same algorithm and run it on the "computer" in GoL. It would, because of HashLife being O(log n) take 3 seconds? (assuming O(log₁₀n))

I'm probably overlooking something, since this would be a very important discovery, but I still thought I'd ask about it here.

  • 1
    check the drawbacks, the algorithm works by looking at patterns that form repetitive patterns locally and can thus skip ahead several cycles only when nothing interferes – ratchet freak Apr 2 '14 at 15:46
  • So if it were to implement a sorting algorithm, you wouldn't gain speed if the data was random, but you would if it were for example the same data repeated x times? So in the end it would be as fast as a regular computer because a computer would also recognize the fact that the data was repeated x times. – Simon Verbeke Apr 2 '14 at 15:54
  • @SimonVerbeke: No. Half-life relies on a reliably-repeating pattern. You wouldn't see that in data that you're sorting until you looked at all the elements, which is O(n). There are some compression algorithms that rely on temporal redundancy of data (repeating patterns) but I suspect that those, too, are at least O(n). – Robert Harvey Apr 2 '14 at 16:09
  • “Big O” is about how run-time scales asymptotically. It doesn't allow you to reason about the run-time of any input of given size. – 5gon12eder Apr 1 '16 at 17:33
2

Since Hashlife runs the Game of Life which is Turing complete, it can run any Turing-computable program. If the complexity for all programs run through Hashlife would be reduced by log(n), that would for example get the (NP-complete) SAT problem (where the best known implementations have O(2^n)) run in O(n). Maybe with multiple Hashlife simulations nested in each other, you could maybe solve every problem in O(log(n)). That could eventually lead to a proof for P=NP.

The problem is that the O(log(n)) only works for the average case, while the worst case still has O(n). Hashlife has three major optimisations:

  1. A Quadtree to be able to generalise operations for all higher level nodes of the tree
  2. Canonicalisation of all nodes in a hashtable to have only one object for every used node layout
  3. Memoisation of the next generation for each node to avoid recalculating it

Both of the latter only work so well because most configurations have many reoccuring patterns and comparatively few different possible nodes. For some of the more complex starting patterns, the Golly simulator starts with the usual very quickly growing speed (when the pattern is still small and regular), but gets slower the more the pattern grows, so it has apparently not purely logarithmic complexity.

You can use memoisation to speed up any other repeated deterministic procedure. You can use trees for efficient data management. You can use canonicalisation for immutable objects to save a lot of memory and calculations.

1

What I meant to ask was if a certain algorithm could run faster, because it is executed in an environment that can run at O(log n). I've also updated my question to not imply a better time complexity, just running faster. I think your logic might be a little flawed.

Even if HashLife is O(log n) and Turing Complete, there's no guarantee that a program you write in it's "programming language" is going to run any faster. The most likely possibility is that it will run slower, because HashLife is optimized for Conway's Game of Life, not general computing algorithms.

  • Aha, I see. As I mentioned in my question there was probably something I was overlooking. – Simon Verbeke Apr 2 '14 at 21:27
1

Edit 2

I think looking at the math behind big O will help. I will not really do this here.

Suppose we have n cells in game of life. Now we implement an algorithm that walks though a list of m elements. This algorithm uses O(m) time. So with the ordinairy GoL implementation this runs in O(n*m). With the more effeicient implementation it needs O(m * log(n)).

Edit 1

algorithms that currently run in e.g. O(n), run in O(log n) instead?

Algorithms do not run. They are a model. Implementations of algorithms run.

I would like the question to be stated more clearly.

Here are thoughts. There are four cases: (without GoL O(log n)) => (with GoL O(log n))

  1. algorithms O(n) => algorithm O(log n) ? Not possible
  2. implementation O(n) => algorithm O(log n) ? Can exist
  3. implementation O(n) => implementation O(log n) ? Exists (GoL)
  4. algorithm O(n) => implementation O(log n) ? Not possible
  • 1
    I'd love to upvote this, but there doesn't seem to be much information here, other than the pedantic observation about implementations and "maybe yes, maybe no." – Robert Harvey Apr 2 '14 at 16:07
  • There has apparently been a misunderstanding on my part. What I meant to ask was if a certain algorithm could run faster, because it is executed in an environment that can run at O(log n). I've also updated my question to not imply a better time complexity, just running faster. – Simon Verbeke Apr 2 '14 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.