The new vbAccelerator Site - more VB and .NET Code and Controls

Generating Long Sequences of Unique Numbers

Author:

Steve McMahon(steve@vbaccelerator.com)

Keywords:

Bit Manipulation

Updated:

18/08/99

Other Tips
All Tips
By Date
By Subject


API (33)
Bit
Manipulation (3)

Clipboard (3)
Combo
Box (5)

Desktop (3)
GDI (13)
Graphics (13)
Internet (2)
Interprocess
Comms (3)

Keyboard (2)
Mouse (1)
Shell (1)
Sprites (1)
Subclassing (3)
Text
Box (2)

Windows (11)
Windows
Controls (10)



Submit


Sometimes it is very useful to be able to generate a long sequence of unique numbers. This tip provides a method to generate long sequences which are not consecutive by using a shift register approach.

As well as providing a sequence of widely spaced unique numbers, the code also generates a bit stream which can be used as a random bit generator, yielding an equally probable but suitably "random" stream of 0s and 1s.

To try it out, start a new project. Then add a module and copy the following code into it:


Public Power2(0 To 31) As Long
Private m_lPoly(0 To 31) As Long
Private m_lMask(0 To 31) As Long

Private m_lNum As Long
Private m_lLength As Long

Public Property Get Number() As Long
Number = m_lNum
End Property

Public Property Let Number(ByVal lNumber As Long)
' Equivalent to seed in random numbers
m_lNum = lNumber
End Property

Public Property Get SequenceLength() As Long
SequenceLength = m_lLength
End Property

Public Property Let SequenceLength(ByVal lLength As Long)
m_lLength = lLength
End Property

Public Function NextNumber() As Long
If m_lNum And Power2(m_lLength - 1) Then
m_lNum = m_lNum Xor (m_lPoly(m_lLength))
' Shift and put 1 into lowest order bit:
m_lNum = RShift(m_lNum, 1) Or 1
' Return lowest order bit:
NextNumber = 1
Else
' Shift and put 0 into lowest order bit:
m_lNum = RShift(m_lNum, 1)
' Return lowest order bit:
NextNumber = 0
End If
' Mask out > bits
m_lNum = m_lNum And m_lMask(m_lLength)
End Function

Public Function RShift(ByVal lThis As Long, ByVal lBits As Long) As Long
If (lBits RShift = lThis
ElseIf (lBits > 63) Then
' .. error ...
ElseIf (lBits > 31) Then
RShift = 0
Else
If (lThis And Power2(31 - lBits)) = Power2(31 - lBits) Then
RShift = (lThis And (Power2(31 - lBits) - 1)) * Power2(lBits) Or Power2(31)
Else
RShift = (lThis And (Power2(31 - lBits) - 1)) * Power2(lBits)
End If
End If
End Function

Public Sub Init()
Power2(0) = &H1&
Power2(1) = &H2&
Power2(2) = &H4&
Power2(3) = &H8&
Power2(4) = &H10&
Power2(5) = &H20&
Power2(6) = &H40&
Power2(7) = &H80&
Power2(8) = &H100&
Power2(9) = &H200&
Power2(10) = &H400&
Power2(11) = &H800&
Power2(12) = &H1000&
Power2(13) = &H2000&
Power2(14) = &H4000&
Power2(15) = &H8000&
Power2(16) = &H10000
Power2(17) = &H20000
Power2(18) = &H40000
Power2(19) = &H80000
Power2(20) = &H100000
Power2(21) = &H200000
Power2(22) = &H400000
Power2(23) = &H800000
Power2(24) = &H1000000
Power2(25) = &H2000000
Power2(26) = &H4000000
Power2(27) = &H8000000
Power2(28) = &H10000000
Power2(29) = &H20000000
Power2(30) = &H40000000
Power2(31) = &H80000000

' Mod2 Polynomials for maximal length sequences:
m_lPoly(1) = 0
m_lPoly(2) = Power2(0)
m_lPoly(3) = Power2(0)
m_lPoly(4) = Power2(0)
m_lPoly(5) = Power2(1)
m_lPoly(6) = Power2(0)
m_lPoly(7) = Power2(0)
m_lPoly(8) = Power2(3) Or Power2(2) Or Power2(1)
m_lPoly(9) = Power2(3)
m_lPoly(10) = Power2(2)
m_lPoly(11) = Power2(1)
m_lPoly(12) = Power2(5) Or Power2(3) Or Power2(0)
m_lPoly(13) = Power2(3) Or Power2(2) Or Power2(0)
m_lPoly(14) = Power2(4) Or Power2(2) Or Power2(0)
m_lPoly(15) = Power2(0)
m_lPoly(16) = Power2(4) Or Power2(2) Or Power2(1)
m_lPoly(17) = Power2(2)
m_lPoly(18) = Power2(4) Or Power2(1) Or Power2(0)
m_lPoly(19) = Power2(4) Or Power2(1) Or Power2(0)
m_lPoly(20) = Power2(2)
m_lPoly(22) = Power2(0)
m_lPoly(23) = Power2(4)
m_lPoly(24) = Power2(3) Or Power2(2) Or Power2(0)
m_lPoly(25) = Power2(2)
m_lPoly(26) = Power2(5) Or Power2(1) Or Power2(0)
m_lPoly(27) = Power2(4) Or Power2(1) Or Power2(0)
m_lPoly(28) = Power2(2)
m_lPoly(29) = Power2(1)
m_lPoly(30) = Power2(5) Or Power2(3) Or Power2(0)
m_lPoly(31) = Power2(2)
'm_lPoly(32) = Power2(6) Or Power2(4) Or Power2(2) Or Power2(1) Or Power2(0)

' Masks:
Dim i As Long
For i = 0 To 30
m_lMask(i) = Power2(i) - 1
Next i
m_lMask(31) = &H7FFFFFFF

m_lNum = 1

End Sub

To test this function out, add a CommandButton and a ListBox to the project's form. Set the Sorted property of the ListBox to True. Then add the following code:


Private Sub TestSequence(ByVal lLength As Long)
Dim i As Long

' Seed at 1:
Number = 1
' Set a sequence length:
SequenceLength = lLength

' Show that the algorithm generates
' unique digits 2^Length-1:
lstTest.Clear
lstTest.AddItem Number
For i = 1 To Power2(lLength) - 2 NextNumber
lstTest.AddItem Number
Next i

For i = 0 To lstTest.ListCount - 2
If lstTest.List(i) = lstTest.List(i + 1) Then
' Does not occur!
lstTest.ListIndex = i
MsgBox "Duplicate: " & lstTest.List(i)
End If
Next i

End Sub

Private Sub Command1_Click()
' Test a 255 number sequence (2^8-1):
TestSequence 8
End Sub

Private Sub Form_Load()
' Must initialise to set up the precompiled Powers of 2
' and polynomials:
Init
End Sub


Run the project. When you click the button, the list box will be filled with the sequence of 255 numbers. Because the ListBox is sorted, the numbers will appear in order - this is just to make the duplicate test simple.

To see the numbers in the sequence they are generated, change the ListBox's Sorted property to False and re-run the project.

To check out the random bits generated by the routine, modify the line

NextNumber

To read:

If NextNumber = 0 Then
Debug.Print "Tails"
Else
Debug.Print "Heads"
End If

This will then display a random sequence of Heads and Tails.


&nbsp

Related Tips and Articles:

&nbsp

AboutContributeSend FeedbackPrivacy

Copyright 1998-1999, Steve McMahon ( steve@vbaccelerator.com). All Rights Reserved.
Last updated: 18/08/99