Two More Random Exercises
August 21, 2012
We calculate the next item in a middle-square sequence by computing quotients and remainders to appropriate powers of ten:
(define (middle-square n)
(let* ((len (+ (ilog 10 n) 1)) (len2 (quotient len 2)))
(modulo (quotient (* n n) (expt 10 len2)) (expt 10 len))))
Here’s an example:
> (let loop ((n 675248) (k 25))
(when (positive? k)
(display n) (newline)
(loop (middle-square n) (- k 1))))
675248
959861
333139
981593
524817
432883
387691
304311
605184
247673
341914
905183
356263
923325
529055
899193
548051
359898
526570
275964
156129
376264
574597
161712
150770
RANDU is a simple multiplication and modulus:
(define (randu n) (modulo (* 65539 n) (expt 2 31)))
Here’s an example:
> (let loop ((n 1) (k 25))
(when (positive? k)
(display n) (newline)
(loop (randu n) (- k 1))))
1
65539
393225
1769499
7077969
26542323
95552217
334432395
1146624417
1722371299
14608041
1766175739
1875647473
1800754131
366148473
1022489195
692115265
1392739779
2127401289
229749723
1559239569
845238963
1775695897
899541067
153401569
We used ilog from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/sNh3CRcZ.
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 […]