Middle-square Randomizer

From TheAlmightyGuru
Jump to: navigation, search
The program in action.

Middle-square Randomizer is a program I wrote in FreeBASIC which demonstrates one of the ways programmers can use the Middle-square method to generate pseudorandom numbers. This method has been supplanted by much better methods and is no longer used, but it is of historical significance because it is the very first method of generating pseudorandom numbers ever described in mathematics, first explained in 1949 by John von Neumann.

Below is the source and a compiled Windows binary. The program allows a middle width of 2-9 digits, and automatically detects when it loops.

Source

' This program uses the middle-square method to generate pseudorandom 
' numbers.
' 
' The process has three steps:
'   Step 1.) Begin with an input seed.
'   Step 2.) Square the value (multiply it with itself).
'   Step 3.) Take only the middle digits for the number. The number of digits 
'            to take from the middle should be determined beforehand. If the 
'            square isn't large enough, pad it with leading zeroes.
' 
' The number you get is your pseudorandom number, which you can then feed 
' back into the algorithm to get another pseudorandom.
' 
' For example, if you start with seed 41 and use a middle width of 2, you 
' will get the following result:
'     Seed:       41
'     Squared:   1681
'     Middle 2:   68
'     Squared:   4624
'     Middle 2:   62
'     Squared:   3844
'     Middle 2:   84
'     Squared:   7056
'     Middle 2:   05
'     Squared:    25
'     Middle 2:   25
'     Squared:   0625
'     Middle 2:   62
'
' Once we encounter a number we have already seen, in this case, 62, we have 
' become stuck in a loop. For our example seed of 41 with a middle width of 
' 2, the total sequence is 6 cycles, and it loops back to the third cycle and 
' then repeats the same 4 numbers forever. Every seed eventually loops, but, 
' generally speaking, the larger your middle width, the longer it takes to 
' encounter a loop. Some numbers, like 0 and 1, immediately loop since they 
' square to the same value.
'
' This is the very first method ever described for generating random numbers. 
' It was invented by John von Neumann in 1949. It's also one of the worst 
' methods for generating random numbers since, when using a low width for 
' middle digits, loops occur very early. You can increase the time before 
' this occurs by using a high width for the middle digits, but, the wider it 
' gets, the more complicated the math becomes.
' 
' This program was written by Dean Tersigni. It's based on von Neumann's 
' method, only it has a slight variation that gives it better results when 
' the square doesn't result in an even number of digits.
' 
' For more information visit: 
'    https://en.wikipedia.org/wiki/Middle-square_method for more 

Const As ULongInt MaxCycles = 10000

Dim As ULongInt InitialSeed, MiddleWidth, Seed, Count, RepeatIndex
Dim As String SquareString
Dim As LongInt I, RepeatSeed = -1
Dim As ULongInt SeedHistory(MaxCycles)

' Ask the user for a middle width.
Do
	Input "Enter a middle width (1-9): ", MiddleWidth
Loop While MiddleWidth < 1 Or MiddleWidth > 9

' Ask the user for a seed value.
Do
	Input "Enter a seed number (2-999,999,999): ", InitialSeed
Loop While InitialSeed < 2 Or InitialSeed > 999999999

Seed = InitialSeed

Cls
Print "Processing for seed "; InitialSeed; " using a middle width of "; MiddleWidth; "."
Print

Do While RepeatSeed = -1
	Print Count; ".) "; Seed

	' Store the seed in the history.
	SeedHistory(Count) = Seed

	' Look for a repeat in the seed history.
	For I = 0 To (Count - 1)
		If Seed = SeedHistory(I) Then
			RepeatSeed = SeedHistory(I)
			RepeatIndex = I
			Exit For
		End If
	Next I

	If RepeatSeed = -1 Then
		' Square the seed.
		Seed = Seed ^ 2
		
		' Convert the squared seed to a string so it's easier to work with.
		SquareString = Str(Seed)

		' Trim digits alternating between left and right until the square is 
		' back down to the desired middle width.
		Do While Len(SquareString) > MiddleWidth
			If Len(SquareString) Mod 2 = 0 Then
				SquareString = Right(SquareString, Len(SquareString) - 1)
			Else
				SquareString = Left(SquareString, Len(SquareString) - 1)
			End If
		Loop
		
		' Convert the string back to a number.
		Seed = Val(SquareString)
		
		Count = Count + 1
		
		' Failsafe for extremely large sequences.
		If Count = MaxCycles Then
			Exit Do
		EndIf
	End If
Loop

' Report findings.
Print
If RepeatSeed = -1 Then
	Print "Seed doesn't repeat after "; MaxCycles; " cycles."
Else
	Print "Total Cycle: "; Count
	Print "Repeating Value: "; RepeatSeed
	Print "Returns to Index: "; RepeatIndex
	Print "Repeating Cycle: "; Count - RepeatIndex
End If

Sleep
End

Download

This includes the program and source code.

Links

Link-Wikipedia.png