EvC Forum: Evolution as an Algorithm

Email This Thread

Newer Topic | Older Topic

Author

Topic: Evolution as an Algorithm

Percy

Member

Posts: 22502

From: New Hampshire

Joined: 12-23-2000

Member Rating: 4.9

Normal Thread Display

Message 49 of 74 (345475)
08-31-2006 3:06 PM

Reply to: Message 37 by JavaMan
08-31-2006 12:04 PM

Re: Not an algorithm

An example might help you understand how random numbers work in algorithm development. Here's a number guessing program written in C:

// Number guessing program

#include 
#include 
#include 

// #define RANDOMIZE

int main(int argc, char* argv) {
#ifdef RANDOMIZE
  srand(clock());
#endif
  printf("Number guessing program.  Enter 0 to quit.\n");
  while(1) {
    unsigned int randomNumber = (rand() % 10) + 1;
    unsigned int guessedNumber;
    printf("I'm thinking of a number between 1 and 10.  Your guess: ");
    scanf("%d", &guessedNumber);
    if (guessedNumber == 0) {
      break;
    }
    if (randomNumber == guessedNumber) {
      printf("Right you are!\n");
    } else {
      printf("Sorry, the number was %d.\n", randomNumber);
    }
  }
}

Put the above code in a file called randgame.c, then compile and run the program by typing a.out:

% cc randgame.c
% a.out
Number guessing program.  Enter 0 to quit.
I'm thinking of a number between 1 and 10.  Your guess: 5
Sorry, the number was 9.
I'm thinking of a number between 1 and 10.  Your guess: 4
Sorry, the number was 9.
I'm thinking of a number between 1 and 10.  Your guess: 3
Sorry, the number was 4.
I'm thinking of a number between 1 and 10.  Your guess: 2
Sorry, the number was 6.
I'm thinking of a number between 1 and 10.  Your guess: 1
Sorry, the number was 2.
I'm thinking of a number between 1 and 10.  Your guess: 0
%

If you run the program again you'll get the same result. The program generates the same sequence of random numbers every single time. And that's exactly what you need while you're debugging the program. It's impossible to debug a program that is given different data every time it runs.

But now the program is debugged, so let us randomize the generation of random numbers by calling srand with an argument of the processor clock. Do this by uncommenting the "#define RANDOMIZE" line. Now repeat the steps as before, but this time you'll get a different sequence of random numbers. Everytime you run the program the sequence of random numbers will be different, because the processor clock has a different value each time the program runs:

% cc randgame.c
% a.out
Number guessing program.  Enter 0 to quit.
I'm thinking of a number between 1 and 10.  Your guess: 5
Sorry, the number was 1.
I'm thinking of a number between 1 and 10.  Your guess: 4
Sorry, the number was 9.
I'm thinking of a number between 1 and 10.  Your guess: 3
Sorry, the number was 9.
I'm thinking of a number between 1 and 10.  Your guess: 2
Sorry, the number was 8.
I'm thinking of a number between 1 and 10.  Your guess: 1
Sorry, the number was 9.
I'm thinking of a number between 1 and 10.  Your guess: 0
%

--Percy

Edited by Percy, : Accidentally hit submit.

Edited by Percy, : Fix typos.

Edited by Percy, : Fix angle brackets on include statements.

This message is a reply to:
	Message 37 by JavaMan, posted 08-31-2006 12:04 PM		JavaMan has replied

Replies to this message:
	Message 57 by JavaMan, posted 09-01-2006 3:33 AM		Percy has replied

Percy

Member

Posts: 22502

From: New Hampshire

Joined: 12-23-2000

Member Rating: 4.9

Normal Thread Display

Message 59 of 74 (345659)
09-01-2006 7:21 AM

Reply to: Message 57 by JavaMan
09-01-2006 3:33 AM

Re: Not an algorithm

JavaMan writes:

Thanks for the example, Percy, but I'm a computer programmer

Oh, okay. I think this is just a semantic issue then, because it depends upon which definition of algorithm you prefer, or which definition you're using at any particular time. A loose definition, the one we programmers use every day, allows that there is such a thing as a random algorithm, and it just considers the randomizing factors as part of the algorithm.

A more formal approach to algorithms, one which doesn't come up much for most programmers in their day-to-day work but which is an area of specialization within computer science, holds that any random factors are outside the algorithm and that the algorithm itself is deterministic. The easiest way to eliminate the complexity of modern computer languages in which we all think and that would cloud the consideration of questions like, "Are algorithms deterministic" is to examine the question in terms of a Turing machine, and then the answer becomes unambiguous: algorithms are deterministic. Always.

--Percy

This message is a reply to:
	Message 57 by JavaMan, posted 09-01-2006 3:33 AM		JavaMan has not replied

Percy

Member

Posts: 22502

From: New Hampshire

Joined: 12-23-2000

Member Rating: 4.9

Normal Thread Display

Message 60 of 74 (345660)
09-01-2006 7:30 AM

Reply to: Message 58 by JavaMan
09-01-2006 4:25 AM

Re: Not an algorithm

JavaMan writes:

In this second sense, a deterministic algorithm is one where the outcome, given a particular set of inputs, is always the same. A non-deterministic algorithm is one where the outcome can't be predicted from the initial inputs.

This confirms my original suspicion that this is just a case of using different definitions. When trying to nail things down precisely it helps to introduce a bit of formalism, and I think that Nwr would agree with me that it is important to separately consider an algorithm from its inputs. You're grouping the randomizing factors with the algorithm when in fact they are actually inputs to the algorithm.

Consider the simple programming example I provided. In a formal sense, the generation of randomNumber is not part of the algorithm. It is an input.

--Percy

This message is a reply to:
	Message 58 by JavaMan, posted 09-01-2006 4:25 AM		JavaMan has replied

Replies to this message:
	Message 62 by JavaMan, posted 09-01-2006 9:24 AM	Percy has not replied
	Message 65 by nwr, posted 09-01-2006 9:29 AM	Percy has not replied

Date format: mm-dd-yyyy

Timezone: ET (US)

Newer Topic | Older Topic

Do Nothing Button

4 online now:	AZPaul3, Pollux, Tangle, Taq
Newest Member:	ChatGPT
Post Volume:	Total: 916,871 Year: 4,128/9,624 Month: 999/974 Week: 326/286 Day: 47/40 Hour: 1/1