Middle-square Randomizer

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
'
' 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.
'
'    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
```