Code Golf: MSM Random Number Generator

Question

The challenge:

The shortest code by character count that will generate a series of (pseudo)random numbers using the Middle-Square Method.

The Middle-Square Method of (pseudo)random number generation was first suggested by John Von Neumann in 1946 and is defined as follows:

R_n+1 = mid((R_n)², m)

For example:

3456² = 11943936

mid(11943936) = 9439

9439² = 89094721

mid(89094721) = 0947

947² = 896809

mid(896809) = 9680

9680² = 93702400

mid(93702400) = 7024

Another example:

843² = 710649

mid(710649) = 106

106² = 11236

mid(11236) = 123

123² = 15129

mid(15129) = 512

512² = 262144

mid(262144) = 621

621² = 385641

mid(385641) = 856

856² = 732736

mid(732736) = 327

327² = 106929

mid(106929) = 069

69² = 4761

mid(4761) = 476

476² = 226576

mid(226576) = 265

Definition of mid:

Apparently there is some confusion regarding the exact definition of mid. For the purposes of this challenge, assume that you are extracting the same number of digits as the starting seed. Meaning, if the starting seed had 4 digits, you would extract 4 digits from the middle. If the starting seed had 3 digits, you would extract 3 digits from the middle.

Regarding the extraction of numbers when you can't find the exact middle, consider the number 710649. If you want to extract the middle 3, there is some ambiguity (106 or 064). In that case, extract the 3 that is closest to the beginning of the string. So in this case, you would extract 106.

An easy way to think of it is to pad zeroes to the number if it's not the right number of digits. For example, if you pad leading-zeroes to 710649 you get 0710649 and the middle 3 digits now become 106.

Test cases:

Make no assumptions regarding the length of the seed. For example, you cannot assume that the seed will always be 4-digit number

A starting seed of 3456 that generates 4-digit random-numbers should generate the following series (first 10):

9439, 947, 9680, 7024, 3365, 3232, 4458, 8737, 3351, 2292

A starting seed of 8653 that generates 4-digit random numbers should generate the following series (first 10):

8744, 4575, 9306, 6016, 1922, 6940, 1636, 6764, 7516, 4902

A starting seed of 843 that generates 3-digit random numbers should generate the following series (first 10):

106, 123, 512, 621, 856, 327, 69, 476, 265, 22

A starting seed of 45678 that generates 5-digit ranom numbers should generate the following series (first 10):

86479, 78617, 80632, 1519, 30736, 47016, 10504, 3340, 11556, 35411

As far as leading zeroes are concerned, the answer is no leading zeroes should be displayed :).

Answer 1

JavaScript: 91 characters

function a(s,n){m=(s+'').length;while(n--)c=''+s*s,s=1*c.substr((c.length-m)/2,m);return s}

Usage:

a(3456, 4);     // 4th seed of 3456:   Returns: 7024
a(8653, 2);     // 2nd seed of 8653:   Returns: 4575
a(843, 10);     // 10th seed of 843:   Returns: 22
a(45678, 6);    // 6th seed of 45678:  Returns: 47016

Full Test Cases:

var tests = [3456, 8653, 843, 45678];

for (var i = 0; i < tests.length; i++) {
   console.log('-------------');
   console.log('| Seed: ' + tests[i]);
   console.log('-------------');

   for(var j = 1; j <= 10; j++) {
      console.log('| ' +  a(tests[i], j));
   }

   console.log('~~~~~~~~~~~~~');
}

Test Results:

-------------         -------------
| Seed: 3456          | Seed: 8653
-------------         -------------
| 9439                | 8744
| 947                 | 4575
| 9680                | 9306
| 7024                | 6016
| 3365                | 1922
| 3232                | 6940
| 4458                | 1636
| 8737                | 6764
| 3351                | 7516
| 2292                | 4902
~~~~~~~~~~~~~         ~~~~~~~~~~~~~

-------------         -------------
| Seed: 843           | Seed: 45678
-------------         -------------
| 106                 | 86479
| 123                 | 78617
| 512                 | 80632
| 621                 | 1519
| 856                 | 30736
| 327                 | 47016
| 69                  | 10504
| 476                 | 3340
| 265                 | 11556
| 22                  | 35411
~~~~~~~~~~~~~         ~~~~~~~~~~~~~

Answer 2

Groovy - 82 chars

s=args[0]as int;def r(){f=s*s;g=f as String;t=g.size()/2;g=g[t-2..t+1];s=g as int}

using first argument as seed and output made by 4 base10 digits like in your examples..

Answer 3

Python (86 chars)

r=input()
l=len(str(r))
while 1:
 x=str(r*r)
 y=(len(x)-l)/2
 r=int(x[y:y+l])
 print r

Produces infinite sequence on stdout. Note that backtick trick won't work at least on older versions with long type because of the ending L in representation. Python 3 print as function would add 1 more char for closing paren.

Answer 4

Perl - 112 - now, 108 - now 95 (thanks to Zaid's idea) - chars sans white space, excluding test driver loop (e.g. I only counted the code to generate 1 sequence) - the code in the body of foreach loop.

@s=(8653,843,45678,3456);
foreach $s (@s){
    for(0..9){$s*=$s;$l=length($s);$L||=($l+1)/2;$H=($l+$L+1)/2;
        $s=substr($s,-$H,$L)+0;
        print "$s,"
    }
    print "\n";
    $L=0; @S=(); # Reset for next loop
}

Output:

8744,4575,9306,6016,1922,6940,1636,6764,7516,4902,
106,123,512,621,856,327,69,476,265,22,
86479,78617,80632,1519,30736,47016,10504,3340,11556,35411,
9439,947,9680,7024,3365,3232,4458,8737,3351,2292,

Compressed code that was 112:

for(0..9){$s*=$s;$l=length($s);$L||=($l+1)/2;$H=($l+$L+1)/2;$s=substr($s,-$H,$L)+0;print "$s,"}

Answer 5

Perl (102 96 95 93 92 79 chars)

$s=$_;$d=length$s;map{$s*=$s;print 0+($s=substr$s,($s=~y///c-$d)/2,$d),$/}0..9

echo -n 3456 | perl -ne '$s=$_;$d=length$s;map{$s*=$s;print 0+($s=substr$s,($s=~y///c-$d)/2,$d),$/}0..9'
9439
947
9680
7024
3365
3232
4458
8737
3351
2292

Answer 6

C# (96 81 79 85 84 chars)

Change log

• Added Yuliy's suggestion for 81
• Removed extra brackets for 79.
• Incremented count because I did not initially count the necessary spaces (only chars).
• Replacing 1.0 by 1d as per Camerons suggestion.

---

My Code:

    int F(int s, int l)
    {
        var r = "" + 1d*s*s;

        return int.Parse(r.Substring((r.Length - l) / 2, l));
    }

---

Usage Example:

    int s = 8653;
    int l = 4;
    for(int i = 0; i< 10; i++)
    {
        s = F(s, l);
        Console.WriteLine(s);
    }

---

Results

---8653---
8744
4575
9306
6016
1922
6940
1636
6764
7516
4902

---843---
106
123
512
621
856
327
69
476
265
22

---45678---
86479
78617
80632
1519
30736
47016
10504
3340
11556
35411

Answer 7

Haskell (97 99 chars)

Can probably still be shortened. Produces an infinite sequence, or at least it encounters 0, in which case it crashes.

i(f:l)x=x:i l(f x)
m n=head.filter((==n).length).i(cycle[init,tail])
b r n=n:b r(read$m r$show$n*n)

Usage: b <length of number> <number>

*Main> b 5 45678
[45678,86479,78617,80632,1519,30736,47016,10504,3340,11556,35411...

Explanation

Rather than applying substring and using string length arithmetic, this program iterates between removing the last character (init), and removing the first character (tail) until the desired length is reached.

As iterate as well as most Haskell functions assume that the function used is constant. Since we have the function itself changing, we need to implement a special version of iterate.

Answer 8

Lua (135 128 114 chars)

function r(i)
l=string.len
b=i or b
s=i or s
p=s*s..""
e=(l(p)-l(b))/2
s=tonumber(p:sub(e+1,e+l(b)))
return s
end

Seeds with one argument and returns first MSM random integer; subsequent calls with no arguments return next MSM random integer. Call will another integer to re-seed.

Test:

> =r(3456)
9439
> =r()
947
> =r()
9680
> =r()
7024
> =r()
3365
> =r()
3232
> =r()
4458
> =r()
8737
> =r()
3351
> =r()
2292
> =r(8653)
8744
> =r()
4575
> =r()
9306
> =r()
6016
> =r()
1922
> =r()
6940
> =r()
1636
> =r()
6764
> =r()
7516
> =r()
4902
> =r(843)
106
> =r()
123
> =r()
512
> =r()
621
> =r()
856
> =r()
327
> =r()
69
> =r()
476
> =r()
265
> =r()
22
> =r(45678)
86479
> =r()
78617
> =r()
80632
> =r()
1519
> =r()
30736
> =r()
47016
> =r()
10504
> =r()
3340
> =r()
11556
> =r()
35411
> 

Answer 9

Google Docs - Spreadsheet: 42 chars

=MID(C2^2,LEN(C2^2)/2-LEN(C2)/2+1,LEN(C2))

Usage:

• Put the initial seed in cell C2, and drag the formula for all the sequence.

Test Cases:

• Shared Document: Live preview of all test cases.

Screenshot:

Limitations:

• This formula preserves leading zeros, but they could be trimmed using another column and applying INT() on the results.

Answer 10

Perl, 80 chars

(from commandline)

$n=pop;$l=length$n;map{$n*=$n;print 0+($n=substr$n,(length($n)-$l)/2,$l),$/}0..9

Answer 11

Ruby (66 chars)

Assuming integer inputs:

def r s,l=s.to_s.size;x=(s*s).to_s;y=x.size;x[(y-l)/2,l].to_i;end

Answer 12

Perl, 100 94 92 91 90 88 chars

Seed provided through standard input. Newlines included for readability:

@n=($n=pop)=~/./g;
for(0..9){
    @s=$n**2=~/./g;
    $n=join$\,splice@s,(@s-@n)/2,@n;
    print$/,$n+0
}

Answer 13

Ruby, 85 76 69 chars (generates and prints 10 numbers)

n=gets
l=n.size
10.times{n=n.to_i;x=(n*n).to_s;p n=x[(x.size-l)/2,l]}

Reads from standard input.

Output

> ruby rand.rb < 3456
9439
947
9680
7024
3365
3232
4458
8737
3351
2292

> ruby rand.rb < 8653
8744
4575
9306
6016
1922
6940
1636
6764
7516
4902

> ruby rand.rb < 843
106
123
512
621
856
327
69
476
265
22

> ruby rand.rb < 45678
86479
78617
80632
1519
30736
47016
10504
3340
11556
35411

Answer 14

dc 26/37 chars

26 chars the function for a single number:

?dZsl2^dZ1+ll-2/Ar^/All^%p

37 chars with a 10 cycles loop:

?dZsl[2^dZ1+ll-2/Ar^/All^%pdzB>L]dsLx

Explanation of the function:

?            Input n
dZ           calculate number of digits
sl           store in register l
2^           calculate n^2
dZ           calculate number of digits of square
1+ll-2/Ar^/  n/(10^((squaredigits+1-l)/2)) int division truncates last digits 
All^%        n%(10^l) modulus truncates first digits
p            print the number

Test:

dc msml.dc
45678
86479
78617
80632
1519
30736
47016
10504
3340
11556
35411

Answer 15

Haskell

---

Note: An infinite list is produced containing MSM random numbers.

---

Function, 81

l=length
m k n=take k$drop(div(l n-k)2)n
r n=iterate(read.m(l$show n).show.(^2))n

Example usage:

r 34562

Example output:

[34562,94531,36109,3859,48918,92970,...

---

Program, 103

l=length
m k n=take k$drop(div(l n-k)2)n
r n=iterate(read.m(l$show n).show.(^2))n
main=readLn>>=print.r

---