Understanding through Discussion


Welcome! You are not logged in. [ Login ]
EvC Forum active members: 79 (8961 total)
33 online now:
caffeine, jar, JonF, PaulK (4 members, 29 visitors)
Newest Member: Mikee
Post Volume: Total: 869,362 Year: 1,110/23,288 Month: 1,110/1,851 Week: 234/320 Day: 6/87 Hour: 1/0


Thread  Details

Email This Thread
Newer Topic | Older Topic
  
Author Topic:   Evolution as an Algorithm
Percy
Member
Posts: 19242
From: New Hampshire
Joined: 12-23-2000
Member Rating: 3.2


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 <stdio.h>
#include <stdlib.h>
#include <time.h>

// #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 responded

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

  
Percy
Member
Posts: 19242
From: New Hampshire
Joined: 12-23-2000
Member Rating: 3.2


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 yet responded

  
Percy
Member
Posts: 19242
From: New Hampshire
Joined: 12-23-2000
Member Rating: 3.2


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 responded

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

  
Newer Topic | Older Topic
Jump to:


Copyright 2001-2018 by EvC Forum, All Rights Reserved

™ Version 4.0 Beta
Innovative software from Qwixotic © 2020