CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
May 2017
Posts
6

## Non-deterministic programs

Hello everyone

Is there anyone who can help me understand the notion of non-determinist program; What I know is that a non-deterministic program is a program for the same inputs it gives me diffrent resulats. Can you give me a simple program that helps me understand the concept of non derminism

2. ## Re: Non-deterministic programs

[Moved to General Programming as not c++ related]

For a first start, have a look at https://en.wikipedia.org/wiki/Nondet...ic_programming and the links. It refers to two non-deterministic programming
languages.

3. Member
Join Date
Feb 2017
Posts
296

## Re: Non-deterministic programs

What I know is that a non-deterministic program is a program for the same inputs it gives me diffrent resulats.
That definition is somewhat problematic because given the same input a program will always produce the same result.

With (current) computers you can only approximate non-determinism and that is by using random number generators. Still, a program or algorithm that makes use of a random number generator (in one way or another) could (with some good will) be called non-deterministic. There are several areas of computing where this is done routinely, for example Monte Carlo methods and Genetic Algorithms.

The canonical example of a Monte Carlo method is to estimate PI: You inscribe a circle in a square. Then you generate many points at random inside the square. Some will end up inside the circle and some outside. Comparing these two point fractions will give you an estimate of PI, the more points the better.

An example of a deterministic alternative would be to estimate PI by evaluating a series,

http://mathworld.wolfram.com/PiFormulas.html
Last edited by wolle; May 30th, 2017 at 09:28 AM.

4. Junior Member
Join Date
May 2017
Posts
6

## Re: Non-deterministic programs

Thank you for your reply. But I need a small non-deterministic algorithm that does not exceed the 5 instructions and without having used the random. I made this program using the random draw, which we have, a text t and a randomly drawn alphabet p and we check whether this alphabet exists in t or not:
If it is in t and p ∈ to vowels alphabet (P ∈ listV) then:
The variable z should contain one word of text t that contain the alphabet p drawn randomly.
We put in n an index indicates where is p; otherwise z=0 and n=0

As you can see for the same inputs (the text t and the randomly drawn alphabet p) we get different result of z and n which create the non-determinism. Now I need an idea of a small non-deterministic algorithm (that does not exceed the 4-5 instructions) without using the random draw

This is my program

Code:
```#include <stdlib.h>
#include <time.h>
#include <string>
#include <iostream>
#include <vector>
#include <stdio.h>
#include <ctype.h>

using namespace std;

//
int generate_bounds(int, int);
void initialize_rand(unsigned int);

int call_srand = 0;

int generate_bounds(int min, int max)
{
if(call_srand!= 1)
initialize_rand((unsigned)time(NULL));
return rand()%(max-min+1) + min;
}

void initialize_rand(unsigned int n)
{
srand(n);
call_srand = 1;
}
//
int random(int a, int b){
//  Initialization of rand
srand((unsigned int)time(NULL));
return rand()%(b-a) +a;
}

vector<string> Conversion (string s)
{      vector<string> v ;
string x ="";
int index = 0 ;
//Check the word
for ( std::string::iterator it=s.begin(); it!=s.end(); it++)
{

if ( *it != ' ' ) {
if ( isalnum(*(it)) ){
x+=*it ;
}
}
else {
v.push_back(x);
x ="";
}
index ++ ;
}
return v ;
}

bool isExist(char x , vector<char> v)
{
for ( vector<char>::iterator it=v.begin(); it!=v.end(); ++it)
{
if (*(it) == x ) return true ;
}

}
bool isVowel(char x)
{
char listV [6] = { 'a' , 'e' , 'i' , 'o' , 'u' ,'y' } ;
for ( int i=0; i!=6; ++i)
{
if (listV[i] == x ) return true ;
}
return false ;
}

char listV [6] = { 'a' , 'e' , 'i' , 'o' , 'u' ,'y' } ;

int main()
{

while (1)
{

//  we can change the text

string Text = "Relative Correctness is the property of a program to be more correct than another with respect to a given specification whereas absolute correctness with respect to a specification r divides candidate programs into two classes, correct and incorrect, relative correctness defines a partial ordering between candidate programs, whose maximal elements are the absolutely correct programs. Correctness Enhancement is the process of mapping a program P1 into a program P2 that is more correct than P with respect to a specification r ";

std::string alphabet ("abcdefghigklmnopqrstuvwxyz");
char caracter ;
std::string z ;
std::vector<int> n ,n_char ;
int index = 0 , a = 0 ;

//Preparation of our table from the given text
Text+=" ";
vector<string> v = Conversion(Text) ;
string tab [v.size()];
for ( unsigned int i=0; i!=v.size(); ++i)
{
tab[i] = v[i] ;
}
//End of table preparation
//Choice of character with random number
index = random(0,26);
caracter = *(alphabet.begin()+index);
//end choice
//Verification of the character in each word
//See the character family
//Vérification du mot
if ( isVowel(caracter) ){

for ( int i = 0 ; i<v.size() ; i++)
{
for ( string::iterator it=tab[i].begin(); it!=tab[i].end(); ++it)
{
if ( *it == caracter ) {
n.push_back(i);
break ;
}
}
}

index = 0 ;

for ( int i=0 ; i<Text.size(); i++)
{
if ( Text[i] == caracter ) {

if (0< index < Text.size()) {
n_char.push_back(index);
}
}
index ++ ;
}
if (n.size() == 0) {
z="The random alphabet character does not exist in the text";
}

}
else
{
z = "The randomly drawn alphabet character does not belong to the vowel letters" ;
}

//End alphabet character specification
//end verification

//Research result
std::cout << "___________________________________________________________________________" <<  '\n';
std::cout << "                             Program 1  " <<  '\n' ;

std::cout << "___________________________________________________________________________" <<  '\n' <<  '\n';
std::cout << "The randomly drawn alphabet caracter is = '" << caracter << "'"<< '\n';
std::cout << "The text is = '" << Text << "'"<<'\n' <<  '\n';
std::cout << "________________________________" <<  '\n';
std::cout << "THE EXECUTION RESULT: " << '\n';
std::cout << "________________________________" <<  '\n';
std::cout << "* z = " ;
index = 0 ;
if ( n.size()>0) {
index = random(0,n.size()) ;
cout <<  tab[ n[index] ] << " " ;
std::cout << '\n';
index = generate_bounds(0,n_char.size()-1) ;
std::cout << "* n = " <<  n_char[index]+1 <<  '\n';
}
else {  cout << z ;
std::cout << '\n';
std::cout << "* n = " << 0 << '\n';
}
std::cout << '\n'<< '\n'<< '\n'<< '\n'<< '\n'<< '\n'<< '\n';
system("pause");
}
return 0;
}```
Last edited by 2kaud; May 31st, 2017 at 05:39 AM. Reason: Added code tags

5. ## Re: Non-deterministic programs

[Moved back to c++ as now apparent c++ related. Doh!]

6. ## Re: Non-deterministic programs

When posting code, please use code tags. Go Advanced, select the formatted code and click '#'.

What c++ compiler are you using? as
Code:
```string tab[v.size()];
for (unsigned int i = 0; i != v.size(); ++i)
{
tab[i] = v[i];
}```
is not valid standard c++ as the size of array is not known at compile time. For standard c++ try
Code:
`vector<string> tab(v);`
which also copies v to tab without the for loop.

Also
Code:
`if (0< index < Text.size()) {`
probably doesn't work the way expected. Consider
Code:
`if (0< index && index < Text.size()) {`
Last edited by 2kaud; May 31st, 2017 at 06:03 AM.

7. Member
Join Date
Feb 2017
Posts
296

## Re: Non-deterministic programs

As you can see for the same inputs (the text t and the randomly drawn alphabet p) we get different result of z and n which create the non-determinism. Now I need an idea of a small non-deterministic algorithm (that does not exceed the 4-5 instructions) without using the random draw
I remember now that you presented that algorithm here first in French,

http://forums.codeguru.com/showthrea...-code-source-C

You seem to have implemented it to your satisfaction. You now post your solution here, not because you have questions about it, but simply as an example of a non-deterministic algorithm. What you want is another example of a non-deterministic algorithm that doesn't use a random number generator. Is that correct? Is that what you want?

Well, as I said in my previous post, to get non-determinism you normally use a random number generator. This is because it has known statistical properties. But if you don't care about that you could use an un-initialized ordinary variable. This code snippet checks whether an unitialized integer happens to be odd or even,
Code:
```void non_deterministic() { // checks whether an unitialized integer is odd or even
int i; // not initialized, could be anything

if ((i & 1) == 0) std::cout << "this time I am even" << std::endl;
else  std::cout << "this time I am odd" << std::endl;
}```
As an alternative you could read the system clock for example. That would also be non-deterministic. This actually is how random number generators are often "seeded".

But note that this still is not in accordance with your definition of a non-deterministic program. It is because both the un-initialized variable and the system clock are inputs to the program and with the same value they will produce the same result. That is the program is deterministic. But of course if you make a distinction between different kinds of input then you could possibly argue a program can be non-deterministic. If only what the user enters counts as input and reading an external event does not then okay, then a program probably could be called non-deterministic I guess.
Last edited by wolle; May 31st, 2017 at 10:35 AM.

8. ## Re: Non-deterministic programs

Having looked at the code in post #4, as part of understanding it I've 'simplified' it somewhat to be more 'modern' c++11. Consider
Code:
```#include <ctime>
#include <string>
#include <iostream>
#include <vector>
#include <cctype>
#include <sstream>
#include <algorithm>

using namespace std;

int random(int a, int b) {
return rand() % (b - a) + a;
}

void Conversion(string s, vector<string>& v)
{
s.erase(remove_if(s.begin(), s.end(), [](char c) {return !(isalnum(c) || isspace(c)); }), s.end());

stringstream ss(s);
string x;

for (v.clear(); ss >> x; v.push_back(x));
}

bool isVowel(char x)
{
return "aeiouy"s.find(x) != string::npos;
}

int main()
{
srand((unsigned int)time(NULL));

const string Text = "Relative Correctness is the property of a program to be more correct than another with respect to a given specification whereas absolute correctness with respect to a specification r divides candidate programs into two classes, correct and incorrect, relative correctness defines a partial ordering between candidate programs, whose maximal elements are the absolutely correct programs. Correctness Enhancement is the process of mapping a program P1 into a program P2 that is more correct than P with respect to a specification r ";

while (true) {
const char caracter = (char)(random(0, 26) + 'a');

cout << "___________________________________________________________________________" << '\n';
cout << "                             Program 1  " << '\n';

cout << "___________________________________________________________________________" << '\n' << '\n';
cout << "The randomly drawn alphabet caracter is = '" << caracter << "'" << '\n';
cout << "The text is = '" << Text << "'" << '\n' << '\n';
cout << "________________________________" << '\n';
cout << "THE EXECUTION RESULT: " << '\n';
cout << "________________________________" << '\n';

vector<string> v;
Conversion(Text, v);

if (isVowel(caracter)) {
vector<int> n;

for (size_t i = 0; i < v.size(); ++i)
if (v[i].find(caracter) != string::npos)
n.push_back(i);

if (n.size() == 0)
cout << "The random vowel character does not exist in the text";
else {
vector<int> n_char;

for (size_t pos = 0, old = 0; (old = Text.find(caracter, pos)) != string::npos; pos = old + 1)
n_char.push_back(old);

cout << "* z = " << v[n[random(0, n.size())]] << "\n" << "* n = " << n_char[random(0, n_char.size())] + 1 << '\n';
}
} else
cout << "The randomly drawn alphabet character does not belong to the vowel letters";

cout << string(6, '\n');
system("pause");
}

return 0;
}```
As I understand it,
string Text contains the text to examine
vector v contains the words from the string Text with non alpha-numeric chars removed
char caracter contains a random lower-case letter
vector n contains the indexes of v for those words that contain caracter when caracter is a vowel
vector n_char contains the positions in Text for caracter when caracter is a vowel

If caracter is a vowel and it appears in Text then the output is
- z - a random word that contains that vowel
- n - a random position in Text (starting from 1) that contains the vowel

random is used three times in the code
- to obtain a letter
- display an element from v
- to display an index for Text

Are you now looking for the same text analysis without using random but will produce potentially different output each time run?

9. ## Re: Non-deterministic programs

This code snippet checks whether an unitialized integer happens to be odd or even,
Code:
```void non_deterministic() { // checks whether an unitialized integer is odd or even
int i; // not initialized, could be anything

if ((i & 1) == 0) std::cout << "this time I am even" << std::endl;
else  std::cout << "this time I am odd" << std::endl;
}```
With VS2017, this gives an error C4700 that uninitialized local variable 'i' used.

10. ## Re: Non-deterministic programs

As an alternative you could read the system clock for example. That would also be non-deterministic. This actually is how random number generators are often "seeded".
Another ways are
- the time in milliseconds since the computer was powered on
- the time in milliseconds taken for a user to reply to a question (ie Do you want to continue [Y/N]: ) This can be a good one in the right circumstances

Ideally, you want to 'result' to be different each time you use it in a program. So reading from a memory location may give a 'random' number each time a program is run, but is unlikely to give different values if used more than once in a program.

You can obtain a hardware random number generator that can be plugged into a computer that will produce a true random number each time it is accessed as these are based on a physical process such as thermal noise etc. See https://en.wikipedia.org/wiki/Hardwa...mber_generator

11. Member
Join Date
Feb 2017
Posts
296

## Re: Non-deterministic programs

Originally Posted by 2kaud
With VS2017, this gives an error C4700 that uninitialized local variable 'i' used.
It's a warning actually. C++ allows you to not initialize variables.

In previous versions of VS it was easy to disregard warnings but it seems more complicated in VS 2017.

12. ## Re: Non-deterministic programs

Originally Posted by wolle
It's a warning actually. C++ allows you to not initialize variables.

In previous versions of VS it was easy to disregard warnings but it seems more complicated in VS 2017.
Its an error with my version of VS2017 using Toolset v141 with release build and produces a failed compilation - and no, I haven't got 'Treat warnings as errors' set.

Code:
`1>c:\develop\vc\test64\source.cpp(23): error C4700: uninitialized local variable 'i' used`

13. Junior Member
Join Date
May 2017
Posts
6

## Re: Non-deterministic programs

I'm looking for an idea of another simple non-deterministic program (different from this one) without having used the random

14. Member
Join Date
Feb 2017
Posts
296

## Re: Non-deterministic programs

I'm looking for an idea of another simple non-deterministic program (different from this one) without having used the random
With "the random" do you mean a random number generator? You don't want to use that? I still don't understand why but you could do this for example,

Code:
```int non_deterministic() {
int* p = new int;
int i = *p;
delete p;
return i;
}

void test() {
for (int i = 0; i < 25; ++i) {
std::cout << non_deterministic() << std::endl;
}
}```
It allocates an uninitialized int on the heap and just returns it. So the random number will be an int that happens to be somewhere in memory. I've tested it and it must be run in release mode (not debug). If works if the int is deleted but better if it is not (but then you get a memory leak so you may prefer to delete).

Non_deterministic() is based on the fact that in C++ an uninitialized variable is undefined. Unlike an ordinary random number generator the statistical properties are unknown.
Last edited by wolle; May 31st, 2017 at 01:57 PM.

15. Member
Join Date
Feb 2017
Posts
296

## Re: Non-deterministic programs

Originally Posted by 2kaud
Its an error with my version of VS2017 using Toolset v141 with release build and produces a failed compilation - and no, I haven't got 'Treat warnings as errors' set.
I had the same problem. Strangely enough I could run the code in #14 without problems.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•