Most computer programs do the same thing every time they execute, so they are said to be deterministic. Determinism is usually a good thing, since we expect the same calculation to yield the same result. For some applications, though, we want the computer to be unpredictable. Games are an obvious example, but there are more.
Making a program truly nondeterministic turns out to be not so easy, but there are ways to make it at least seem nondeterministic. One of them is to generate random numbers and use them to determine the outcome of the program. Euphoria provides a built-in function that generates pseudorandom numbers , Euphoria provides a built-in function called rand( atom x1 ) that returns an integer from 1 and x1. Each time you call rand(), you get the next number in a long series. To see a sample, run this loop:
atom x for i = 1 to 10 do x = rand( 100 ) print(1, x ) puts(1, " ") end for -- 32 48 69 32 58 59 30 11 26
The argument for rand() may be any integer from 1 up to 1073741823.
As a convenience, there are additional routines for random numbers in the math.e include file.
The function rand_range() produces "random" integers between (inclusively) a specified low and high limit.
? rand_range( 3, 9) --4
To generate fractional random numbers you could multiply your random values by some constant. The other way is to use rnd() with produces random atom values between (inclusively) 0.0 and 1.0 :
include std/math.e atom x = rnd() ? x -- 0.2634879318
It is possible to create reproducible "random" numbers. It is possible to seed the random number generator so it produces the same results each time. When testing a program it is best if the numbers are not random; otherwise it will be very difficult to find bugs.
include std/math.e set_rand( 1234 ) ? rand( 200 )
As long as the seed value is the same, the "random" number produced will also be the same.
The first step is to generate a list of random values. randomList() takes an integer parameter and returns a list of random numbers with the given length. It starts with a list of n zeros. Each time through the loop, it replaces one of the elements with a random number. The return value is the complete list:
include std/math.e function randomList( integer n ) sequence s s = repeat( 0, n ) for i = 1 to n do s[i] = rnd( ) end for return s end function ? randomList( 5 ) -- { 0.58156264,0.128900711,0.138621469,0.782595345,0.474883733 }
You could also make this list by appending random values:
include std/math.e function randomList( integer n ) sequence s = {} for i=1 to n do s = append( s, rnd() ) end for return s end function
These examples shows a sequence of five elements. For purposes of debugging, it is a good idea to start small.
For the rand() function you can specify a value up to 1073741823 (the largest value for the integer-type). It is much easier to remember that this is almost 109. We can use "scientific notation" to write out this number; so that "1e9" is the same as 1 times 109 or 1000000000.
The numbers generated by random are supposed to be distributed uniformly, which means that every value is equally likely.
If we divide the range of possible values into equal-sized "buckets," and count the number of times a random value falls in each bucket, we should get roughly the same number in each.
We can test this theory by writing a program to divide the range into buckets and count the number of values in each.
A good approach to problems like this is to divide the problem into subproblems and look for subproblems that fit a computational pattern you have seen before.
In this case, we want to traverse a list of numbers and count the number of times a value falls in a given range. That sounds familiar. We previously wrote a program that traversed a string and counted the number of times a given letter appeared.
So, we can proceed by copying the old program and adapting it for the current problem. The original program was:
sequence fruit = "banana" atom count = 0 for char=1 to length(fruit) do if fruit[char] = 'a' then count = count + 1 end if end for ? count -- 3
The first step is to replace fruit with list and char with num. That doesn't change the program; it just makes it more readable.
The second step is to change the test. We aren't interested in finding letters. We want to see if num is between the given values low and high.
sequence list = { 15, 20, 88, 12, 45 } integer count = 0 integer low, high low = 5 high = 40 for num=1 to length(list) do if low < list[num] and list[num] < high then count = count + 1 end if end for ? count -- 3
The last step is to encapsulate this code in a function called inBucket(). The parameters are the list and the values low and high.
function inBucket( sequence list, atom low, atom high ) integer count = 0 for num=1 to length(list) do if low < list[num] and list[num] < high then count = count + 1 end if end for return count end function sequence list = { 15, 20, 88, 12, 45 } ? inBucket( list, 5, 40 ) -- 3
By copying and modifying an existing program, we were able to write this function quickly and save a lot of debugging time. This development plan is called pattern matching. If you find yourself working on a problem you have solved before, reuse the solution.
As the number of buckets increases, inBucket() gets a little unwieldy. With two buckets, it's not bad:
low = inBucket(a, 0.0, 0.5) high = inBucket(a, 0.5, 1)
But with four buckets it is getting cumbersome.
bucket1 = inBucket(a, 0.0, 0.25) bucket2 = inBucket(a, 0.25, 0.5) bucket3 = inBucket(a, 0.5, 0.75) bucket4 = inBucket(a, 0.75, 1.0)
There are two problems. One is that we have to make up new variable names for each result. The other is that we have to compute the range for each bucket.
We'll solve the second problem first. If the number of buckets is numBuckets, then the width of each bucket is 1 / numBuckets.
We'll use a loop to compute the range of each bucket. The loop variable, i, counts from 0 to numBuckets - 1:
atom numBuckets = 8 atom low = 0 atom high = 1 atom bucketWidth = 1 / numBuckets for i = 1 to numBuckets - 1 do low = i * bucketWidth high = low + bucketWidth printf(1, "%g \t to %g\n", {low, high} ) end for
To compute the low end of each bucket, we multiply the loop variable by the bucket width. The high end is just a bucketWidth away. With numBuckets = 8, the output is:
0.0 to 0.125 0.125 to 0.25 0.25 to 0.375 0.375 to 0.5 0.5 to 0.625 0.625 to 0.75 0.75 to 0.875 0.875 to 1.0
You can confirm that each bucket is the same width, that they don't overlap, and that they cover the entire range from 0.0 to 1.0.
Now back to the first problem. We need a way to store eight integers, using the loop variable to indicate one at a time. By now you should be thinking, "Sequence!" We have to create the bucket sequence outside the loop, because we only want to do it once. Inside the loop, we'll call inBucket() repeatedly and update the i-eth element of the sequence:
numBuckets = 8 buckets = [0] * numBuckets bucketWidth = 1.0 / numBuckets for i in range(numBuckets) do low = i * bucketWidth high = low + bucketWidth buckets[i] = inBucket(list, low, high) print buckets end for
With a list of 1000 values, this code produces this bucket list:
{ 138, 124, 128, 118, 130, 117, 114, 131 }
These numbers are fairly close to 125, which is what we expected. At least, they are close enough that we can believe the random number generator is working.
?? what happens if a value fall exactly on a bucket border??
Although this program works, it is not as efficient as it could be. Every time it calls inBucket(), it traverses the entire list. As the number of buckets increases, that gets to be a lot of traversals.
It would be better to make a single pass through the list and compute for each value the index of the bucket in which it falls. Then we can increment the appropriate counter.
In the previous section we took an index, i, and multiplied it by the bucketWidth to find the lower bound of a given bucket. Now we want to take a value in the range 0 to 1 and find the index of the bucket where it falls. Since this problem is the inverse of the previous problem, we might guess that we should divide by bucketWidth instead of multiplying. That guess is correct.
Since bucketWidth = 1 / numBuckets, dividing by bucketWidth is the same as multiplying by numBuckets. If we multiply a number in the range 0 to 1 by numBuckets}, we get a number in the range from 0 to numBuckets. If we round that number to the next lower integer, we get exactly what we are looking for--a bucket index:
numBuckets = 8 buckets = [0] * numBuckets for i in list for index = int(i * numBuckets) buckets[index] = buckets[index] + 1 end for
We used the int function to convert a floating-point number to an integer.
Is it possible for this calculation to produce an index that is out of range (either negative or greater than len(buckets)-1)?
A list like buckets that contains counts of the number of values in each range is called a histogram .