Two More Random Exercises
August 21, 2012
We did two tasks related to random numbers in the most recent exercise, and we have looked at high-quality random number generators in several previous exercises. In today’s exercise we look at two very low-quality random number generators, which should not be used for any production application.
The first, invented by John von Neumann in 1949, occasioned his famous quip “Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.” The middle-square method takes a number with an even number of digits, squares it, and extracts the middle digits for the next iteration; for instance, if the seed is 675248, the square is 455959861504, and the middle digits are 959861.
The second, invented by IBM in the early 1960s, caused Donald Knuth to claim “its very name RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists!”. RANDU is based on the recursion xn+1 = 65539 · xn (mod 231), with x0 odd.
Your task is to write functions that generate random numbers by the middle-square and RANDU methods. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] Pages: 1 2 […]
Needs -std=c++0x if compiling with g++.
#include <iostream> constexpr int ipow( int v, int e ) { return e == 0 ? 1 : ipow(v, e-1) * v; } template<int digits> class RandMidSqr { public: RandMidSqr( int seed = 675248 ) : value( seed ){} int operator()() { return value = ((long long)value * value) / ipow(10,digits/2) % ipow(10,digits); } private: int value; }; struct Randu { public: Randu( unsigned int seed = 1 ) : lastVal( seed ){} unsigned int operator()() { return lastVal = (lastVal * 65539) % ipow(2,31); } private: int lastVal; }; int main( int argc, char**args ) { RandMidSqr<6> rms; for( int i = 0; i < 100; ++i ) { std::cout << rms() << std::endl; } Randu ru; for( int i = 0; i < 100; ++i ) { std::cout << ru() << std::endl; } return 0; }I went ahead and coded up both of them in Scheme. This is the sort of thing where a language that has functions as first class citizens can really shine. You can write a function that generates a function that generates random numbers!
[…] Praxis put out another two “random” exercises, this time about making psuedorandom number generators (where the previous had us composing already […]
A Python solution:
import math def rand_middle_square(seed): n = seed seed_len = int(round(math.log(seed, 10))) while True: yield n n = (n * n) / (10 ** (seed_len / 2)) % (10 ** seed_len) def randu(seed): n = seed while True: yield n n = (65539 * n) % 2147483648 def random(count, seed, rand_fn): nums = [] random_gen = rand_fn(seed) for _ in xrange(count): nums.append(random_gen.next()) return nums print(random(5, 675248, rand_middle_square)) print(random(5, 7, randu))Hey! I think I have bug, or I implemented it wrongly. Any tips anyone?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace NeumannRandNumGen
{
class Program
{
//The middle-square method takes a number with an even number of digits, squares
//it, and extracts the middle digits for the next iteration; for instance, if the
//seed is 675248, the square is 455959861504, and the middle digits are 959861
static void Main(string[] args)
{
int seed = 45505986; // seed
while(true) {
int randomNumber = NeumannRandom0To100(ref seed);
Console.WriteLine(randomNumber.ToString());
Console.ReadLine();
if (randomNumber == -1)
break;
}
}
static SortedSet alreadySeen = new SortedSet();
static int NeumannRandom0To100(ref int seed)
{
if (seed == 0 || seed == -1)
return -1;
// jabūt pāra skaitlim ciparu
if (seed.ToString().Length % 2 != 0)
seed /= 10;
unchecked
{
seed *= seed;
}
string newSeed = seed.ToString();
int length = newSeed.Length;
int middleFirst = length / 2; // int truncate division
int generatedNumber = int.Parse(newSeed[middleFirst].ToString() + newSeed[middleFirst + 1].ToString());
if (alreadySeen.Contains(generatedNumber))
return -1;
alreadySeen.Add(generatedNumber);
return generatedNumber;
}
}
}
[…] built several random number generators: [1], [2], [3], [4], [5], [6], [7], [8], [9] (I didn’t realize it was so many until I went back and looked). In […]