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

Syzygy

Perl masters, this way \/ \/ \/ \/ – Bumpkin

Please make sure that your code works with the 947 test case as well!!! – Churchwarden

Clarify how exactly mid() is defined. What is round to which direction is completely non-obvious. – Surrebuttal

Also, is it acceptable to give answer with leading 0 or not? – Surrebuttal

@M28 Until J/APL come in and does it in a third the count ;-) – Ferroconcrete

@doublep I've given a better explanation of mid – Syzygy

Update doesn't compute. It says "assume that you are extracting the same number of digits as the original seed", yet test case says to produce 476 for seed 69. – Surrebuttal

@doublep I reworked that. Original seed means "starting seed". Ugh. My bad. Didn't realize that this algorithm isn't so clear on the definition of mid. – Syzygy

@Vivin: So it is not to produce one number? The programs should produce 10 numbers? – Surrebuttal

@doublep a series of numbers is fine (you can keep generating them forever if you want). It doesn't have to be exactly 10 numbers. Just as long as it generates a series using the algorithm. – Syzygy

@Vivin - please add the test case in your example (3456 produces 9439, 947, 9680, ...) - the 947 breaks some of the shorter code that assumes all the squares have at least 7 characters. – Churchwarden

@Churchwarden I've added the test case for 3456. – Syzygy

Please check your solution against all posted test-cases and annotate any deviations. Thanks. – Ferroconcrete

Isn't it funny that most code golf questions systematically start out with a basic definition and then edge cases come out and only then an extensive writeup of the requirements happen? My, it's just like in the real world! – Singlehandedly

@Singlehandedly so true. This is my second code golf question. The first one was better defined! – Syzygy

Answer 1

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

Iraq

Wow, I don't know dc can be used in this way. – Buttercup

Answer 2

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:

Code Golf: MSM Random Number Generator http://img59.imageshack.us/img59/6830/golfo.png

Limitations:

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

Tisman

So, including the "Fill Down" operation, shouldn't this be "42 chars + 1 click-drag"? – Gardol

@Jeff: I would consider the clicks and drags as stdin, standard input :) ... That's how the user tells the spreadsheet how long the sequence should be. – Tisman

@Jeff:I would consider 10 copies of 42 bytes of code to be 420 bytes total, putting this in last place by a wide margin -- which (at the risk of sounding harsh) is exactly where it belongs; duplicating code 10 times to produce 10 values is just a bad idea. – Passive

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.

Befitting

@doublep I've explained the definition of mid. Sorry about that! – Syzygy

Thanks for asking for more explanation by the way. I apologize for the initial vagueness of the rules. I hope the current set of rules make more sense. – Syzygy

Answer 4

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

Arrivederci

First line can be replaced with var r = "" + (1.*s*s); to save some characters. – Sacci

@AboutDev: Counting int F(int s, int l){var r=""+1.0*s*s;return int.Parse(r.Substring((r.Length-l)/2, l));} seems to be 87 chars. Or am I missing something? – Tisman

@AboutDev: In addition, I think you should derive the length of the seed inside your code, as the length is really functionally dependent on the seed. – Tisman

@Daniel - I'm only counting char but if I include the spaces it comes to 85 for me. – Arrivederci

@AboutDev: True, I missed two spaces. However I think indispensable whitespace should be counted. – Tisman

@Arrivederci - If the whitespace is important, it should be counted. Also you can remove the 1.0* to save 4 characters. – Bosworth

@Daniel - I'll update my number momentarily. @Cameron - You can't remove the 1.0* because doing so will result in the type of s * s to be evaluated as int and thus cause overflow for large numbers of s. – Arrivederci

r.Length can be replaced with ss%10. This allows you to put (""+ss).Substring etc in place without having to declare the variable, saving more characters. – Bosworth

@Arrivederci - About 1.0: I see now. :P The rest still works though. – Bosworth

Save 1 char by replacing 1.0 with 1d – Bosworth

@Cameron - Huzza! 1d it is!! :-) – Arrivederci

If you don't care to return an integer, and can do with a string, the count decreases to 77 char. 'string F(int s, int l){var r=""+1dss;return r.Substring((r.Length-l)/2,l);}' – Arrivederci

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

Syzygy

Answer 6

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

---

Stupe

Answer 7

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

Ianthe

Answer 8

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

Pattypatulous

Answer 9

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.

Hudnall

Answer 10

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

Strouse

does there have to be a space between ; and def? 82 chars – Gigolo

Does this handle 3456 seed? (I don't read Groovy so not sure, sorry) – Churchwarden

its output for 3456: 9439, 947, 9680, 7024, 3365, 3232, 4458, 8737, 3351, 2292 – Strouse

gonna check if it's "new mid definition compliant" tomorrow! – Strouse

@Strouse sorry about the confusion. My bad :p The rules have stabilized so it should still be the same tomorrow! – Syzygy

Answer 11

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
~~~~~~~~~~~~~         ~~~~~~~~~~~~~

Tisman

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
}

Reservation

Answer 13

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

Gildagildas

Answer 14

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
> 

Allopathy

Answer 15

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,"}

Churchwarden

NOTE: the current code obeys all the rules and correctly handles both given test cases AND the example case – Churchwarden

No problem. No need for the space after print – Reservation