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.

About these ads

Pages: 1 2

5 Responses to “Two More Random Exercises”

  1. madscifi said

    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;
    }
    
  2. JP said

    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!

  3. [...] Praxis put out another two “random” exercises, this time about making psuedorandom number generators (where the previous had us composing already [...]

  4. 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))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 631 other followers

%d bloggers like this: