Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
Go Back  Xtreme Visual Basic Talk > > > Code Snippets From the Web May Spell Doom!


Reply
 
Thread Tools Display Modes
  #1  
Old 11-01-2015, 02:24 PM
Cerian Knight's Avatar
Cerian KnightCode Snippets From the Web May Spell Doom! Cerian Knight is offline
Polymath (in disciplina)

Super Moderator
* Expert *
 
Join Date: May 2004
Location: Michigan
Posts: 4,193
Default Code Snippets From the Web May Spell Doom!


Now that I've got your attention, the fact is that there is a lot of good code posted out there. However, as usual, use it at your own risk.

One of my colleagues refuses to use any code (no matter how simple I think it is) without fully understanding how and why it works. Considering all the horror stories you hear in the news about code-gone-awry, this makes more sense than ever.

Here is one particular random (pun intended) VB6 example I found on the web for how not to write an algorithm: Fast and simple shuffle function. Randomizes given - Visual Basic , VB.NET

Although well documented, everything else has fallen apart.
1. Documentation says any type of array, but actually it must be a zero-based dynamic array.
2. Loop counter is one element shy, so last value in returned shuffled array is empty.
3. Use of 'Now' to seed 'Randomize' will choose the same sequence. At least if 'Timer' had been chosen (which is redundant), it would have worked as intended.
4. Uses 'CLng', instead of 'Int', to gather 'Rnd' element, which causes statistical bias against choosing first and last element in the array.
5. Even correcting for the above, the algorithm still does not work quite right because of the phenomena of 'over-shuffling', which can render some shuffles impossible to achieve, which is most easily demonstrated with an array of just a few elements. The Knuth-Fisher-Yates algorithm should have been chosen instead, which would have required only a minor change.
6. Lack of performance optimizations are not a show-stopper, but just a pet-peeve of mine.
7. Finally, even if everything above is corrected, this (and and all similar algorithms) cannot even arrange a deck of cards through all possible shuffles. To do so would require a PRNG with a period of 52! (factorial), or a true RNG (or nearly so, which is built into the latest Intel CPUs).

With regard to the last point, this is my feeble attempt at a VB6 RNG that might actually be capable of generating all card shuffle permutations. I'll be testing this shortly on Diehard, etc. I expect the results will be just more justification for being careful of code you find on the Web.
Edit by Cerian: Indeed... fixed a major issue (-I overflow) and a minor issue (ScaleI Const limited low bits randomness).
.
Code:
Option Explicit
Private Declare Function QPC Lib "KERNEL32" Alias "QueryPerformanceCounter" (lpPerformanceCount As QWord) As Long
Private Const ScaleI As Double = 7.13318249978691E-15 'was 2.78639941397926E-17 
Private Const ULngCnt As Double = 2 ^ 32
Private Const LngMax As Long = 2 ^ 31 - 1
Private Const Indicies As Long = 2 ^ 24
Private Const IdxLim As Long = 2 ^ 24 - 1
Private Init As Long
Private Random(IdxLim) As Double
Private Reseed As Double 'This may be problematic, as simulations show potential for feedback to cause clustering
Private Type QWord
    l As Long
    H As Long
End Type

Public Function QRndD() As Double 'Call this
Dim Q As QWord
Static I As Long
If Init = 0 Then QRandomizeD 'force initialization
If Init = -1 Then QPC Q
'Sum Feedback with unbiased PRNG base and biased temporal component, then fill resulting partition gaps
Reseed = Reseed + Random(I And IdxLim) + (Not I Xor Q.l) / ULngCnt + Q.l * ScaleI 'Not I' was '-I', which caused overflow on -I when I = -2^31 
I = CLng(I = LngMax) Xor I - CLng(I < LngMax) 'Ring counter
QRndD = Reseed - Int(Reseed) 'Return Fraction
Reseed = QRndD
End Function

Public Sub QRandomizeD(Optional Seed As Variant = 0) 'only call this for testing (0=Normal, -1=Repeat, 1=Override)
Dim I As Long, j As Long, Q As QWord, s As Long
Dim Rswp As Double
s = Val(Seed)
If s < 0 Then j = Rnd(s)
If s <> 0 Then Randomize s Else Randomize
For I = 0 To IdxLim 'Pump entire RND table for QRndD base
    Random(I) = (Rnd * Indicies + 1) / (Indicies + 1) - 0.5 'unbiased -0.5 < N < 0.5
Next
For I = 0 To IdxLim - 1 'KFY Shuffle poorly distributed RND table
    If s >= 0 Then QPC Q 'aquire temporal component
    Reseed = Reseed + Random(-I And IdxLim) + (-I Xor Q.l) / ULngCnt + Q.l * ScaleI
    Reseed = Reseed - Int(Reseed)
    j = Int((Indicies - I) * Reseed) + I
    Rswp = Random(I): Random(I) = Random(j): Random(j) = Rswp 'Swap the numbers
Next
If s >= 0 Then Init = -1 Else Init = 1
End Sub
__________________
I got all the answers wrong on the GLAT, apparently even #9 (where I put a period in the middle of the box and labeled it 'singularity ripe for rapid inflation').

Last edited by Cerian Knight; 11-15-2015 at 10:36 PM. Reason: Corrected code for Const ScaleI and -I overflow issue
Reply With Quote
  #2  
Old 11-03-2015, 06:31 PM
dilettante's Avatar
dilettanteCode Snippets From the Web May Spell Doom! dilettante is offline
Underclocked lifestyle

Forum Leader
* Guru *
 
Join Date: Feb 2005
Location: Michigan, USA
Posts: 4,524
Default

This post brings to mind something I heard somebody advocate recently. Their idea was to create and maintain a sort of a VB equivalent of the C++ community's Boost libraries.

Basically it would differ somewhat from the random grab-bags of code we have now on the web by requiring adherence to a "blue book" of coding standards, being heavily peer-reviewed and improved, and more curated than most other attempts of the past.

The closest thing of this nature that I can recall was the old Common Controls Replacement Project © but that fell apart fairly quickly in terms of VB6's lifetime.
Reply With Quote
  #3  
Old 11-15-2015, 09:50 PM
Cerian Knight's Avatar
Cerian KnightCode Snippets From the Web May Spell Doom! Cerian Knight is offline
Polymath (in disciplina)

Super Moderator
* Expert *
 
Join Date: May 2004
Location: Michigan
Posts: 4,193
Default

Excellent idea. However, my bias would be toward supporting any and all languages (perhaps in the style of Wikipedia). Contributors would be able to translate to/from any language/platform, where appropriate.

Regarding my prediction about my above code, '(-I Xor Q.l)' should be '(Not I Xor Q.l), as '-I' will overflow. Also, I'm favoring 'Private Const ScaleI As Double = 7.13318249978691E-15'. Edited above code seems to pass Ent and all Diehard tests now. I'll have to install CygWin again (was on my old PC) to do further batteries of tests. I've added further improvements to the code that I'll post later (with full visualization engine for various PRNGs).

Toward improving performance of my own code, which relies on the imperfect Rnd for output value steering/balance, I found this brilliant post attempting to replicate Rnd and Randomize in VB6 for porting to PHP (Linux): Random Number Generator for PHP and VB6 (PRNG)

However brilliant this 'Verified Answer' is, there are three issues:
1. A show-stopper allows 'Rnd' to return 1 (and not 0). The line 'If last_value > two24 Then last_value = last_value - two24' should have been '>=', or better yet eliminate the line altogether and add 'And &HFFFFFF' to the end of the previous line.
2. Minor issue with 'My_Randomize' (without argument) not exactly replicating that of 'Randomize' (without argument). I'm not sure how Timer is used internally within 'Randomize' in order to suggest a fix. ???
3. Lack of obvious optimizations (e.g. ~3x slower than native Rnd). Normally I would let this slide. However, when optimized, this code is >4x (~7.5x with Advanced Optimizations checked) faster than the native VB 'Rnd' (while replicating 99% of Rnd's functionality). Yeah, that caught me off-guard, which is why I say the code is brilliant.
__________________
I got all the answers wrong on the GLAT, apparently even #9 (where I put a period in the middle of the box and labeled it 'singularity ripe for rapid inflation').

Last edited by Cerian Knight; 11-16-2015 at 12:07 AM.
Reply With Quote
  #4  
Old 11-16-2015, 08:56 PM
Cerian Knight's Avatar
Cerian KnightCode Snippets From the Web May Spell Doom! Cerian Knight is offline
Polymath (in disciplina)

Super Moderator
* Expert *
 
Join Date: May 2004
Location: Michigan
Posts: 4,193
Default

Hmmm... now I remember that EE won't let you see the 'Verified Answer' under certain circumstances. What a shame if you can't see it or can only see the incomplete code by the same author (though it is better optimized).

@dilettante: I see you have participated in discussion(s) like those (on random) to which I refer, but of course you were not the offender. The one I noticed is where you provided a brief example of RtlGenRandom API, and wrapped around you someone was bent on helping the TS by trying to manipulate Rnd (which contains on 24 bits of data) with either 2^32 or 2^31 in ways that could not possibly fill a 32-bit Long (or ULong). Like you (in that particular circumstance), I'm going to have to put some blinders on and move along. However, I still recommend finding opportunity where others have found adversity.
__________________
I got all the answers wrong on the GLAT, apparently even #9 (where I put a period in the middle of the box and labeled it 'singularity ripe for rapid inflation').
Reply With Quote
  #5  
Old 11-16-2015, 11:07 PM
dilettante's Avatar
dilettanteCode Snippets From the Web May Spell Doom! dilettante is offline
Underclocked lifestyle

Forum Leader
* Guru *
 
Join Date: Feb 2005
Location: Michigan, USA
Posts: 4,524
Default

For most uses Rnd() is probably good enough. Of course it falls down hard in cases where it isn't good enough, and it all comes down to what problem you are trying to solve.

Schemes based on special hardware operators fall apart since those tend to be specific to individual x86-compatible hardware product families and even to specific devices.

If this was really important we'd have a well defined hardware device spec and most PCs would ship with one integrated into the chipset or motherboard.

If this was more than occasionally useful such a hardware device spec would exist and we'd see implementations available as cheap USB devices with a dedicated USB device profile, driver support, and access APIs standard in every OS - not some crappy thing parasitizing the serial (COMn:) port profile.
Reply With Quote
  #6  
Old 11-17-2015, 09:41 AM
Cerian Knight's Avatar
Cerian KnightCode Snippets From the Web May Spell Doom! Cerian Knight is offline
Polymath (in disciplina)

Super Moderator
* Expert *
 
Join Date: May 2004
Location: Michigan
Posts: 4,193
Default

Quote:
Originally Posted by dilettante View Post
For most uses Rnd() is probably good enough. Of course it falls down hard in cases where it isn't good enough, and it all comes down to what problem you are trying to solve.
The issue (by example) being that a sword that is double-edged is not labeled as such. This is fine for the sword-master, but all others should (know to) stay away as accidents could happen. I don't subscribe to that mentality regarding programming tools, as it doesn't work in other paridigms (e.g. the building of sky-scrapers would be suspect if the use of Lego bricks and butter knives were routine in their construction simply because someone left them in the toolbox).

Quote:
Schemes based on special hardware operators fall apart since those tend to be specific to individual x86-compatible hardware product families and even to specific devices.
Agreed.

Quote:
If this was really important we'd have a well defined hardware device spec and most PCs would ship with one integrated into the chipset or motherboard.
It is important (to some) thus there is a half-way successful step toward accomplishing this with Intel's RdRand... though compliant with multiple standards, it needs to be opened before it can be considered as a possible single source of entropy. Intel's RdSeed is another possibility. It will take years for these (or other efforts) to play out, as it is only meaningful once the availability is sufficient (perhaps 90% of devices).

Quote:
If this was more than occasionally useful such a hardware device spec would exist and we'd see implementations available as cheap USB devices with a dedicated USB device profile, driver support, and access APIs standard in every OS - not some crappy thing parasitizing the serial (COMn port profile.
See above. Actually... I just wanted to be able to quickly shuffle a deck of 52 playing cards and know that any shuffle was possible. Oddly enough, there was nothing out there suitable (that I could find with a period of >52!) which could be implemented on a reasonably platform independent basis (as my yet unpublished final code should be). Unfortunately, my solution is too unusual for consideration as a true RNG and also falls short on the cryptographic/encryption side, but could be used (I suppose) as an additional source of entropy for that purpose.
__________________
I got all the answers wrong on the GLAT, apparently even #9 (where I put a period in the middle of the box and labeled it 'singularity ripe for rapid inflation').
Reply With Quote
  #7  
Old 11-17-2015, 12:55 PM
dilettante's Avatar
dilettanteCode Snippets From the Web May Spell Doom! dilettante is offline
Underclocked lifestyle

Forum Leader
* Guru *
 
Join Date: Feb 2005
Location: Michigan, USA
Posts: 4,524
Default

"All shuffles possible" is one thing... then the question becomes "with equal probability?"

I agree that it can get dicey. I'm less convinced that a hardware device would necessarily be an improvement since many of them may have their own biases.
Reply With Quote
  #8  
Old 11-19-2015, 01:58 PM
ElderKnightCode Snippets From the Web May Spell Doom! ElderKnight is offline
Senior Contributor

Forum Leader
 
Join Date: Oct 2003
Location: Central Florida
Posts: 1,275
Default

Before I incorporated someone else's code in a project of mine, I'd write some simple code to put the routine through its paces a million times to evaluate the results (check the distribution for bumps) and to look for outliers: e.g. card number less than 1 or greater than 53.

No more testing than was justified by the intended use, however. Playing a game is one thing, certifying an airplane part is quite another.
__________________
-- D.J.

I do not endorse any items advertised within this frame, and regret that the viewer is subjected to such.
Reply With Quote
  #9  
Old 05-18-2016, 06:37 PM
Cerian Knight's Avatar
Cerian KnightCode Snippets From the Web May Spell Doom! Cerian Knight is offline
Polymath (in disciplina)

Super Moderator
* Expert *
 
Join Date: May 2004
Location: Michigan
Posts: 4,193
Default

Apparently someone else has shuffled along and gone to a great deal of trouble to achieve a breakthrough that is considered a big deal:
Researchers Discover Breakthrough Method To Generate True Random Numbers From Weak Randomness Sources

I never finished fully certifying my above (though slightly modified) code, but it passed all tests I ran it through. I could have easily substituted a different weak-random source for the QueryPerformanceCounter call I'm using and still achieved similar results, I guess.
__________________
I got all the answers wrong on the GLAT, apparently even #9 (where I put a period in the middle of the box and labeled it 'singularity ripe for rapid inflation').
Reply With Quote
  #10  
Old 05-28-2016, 09:15 AM
dilettante's Avatar
dilettanteCode Snippets From the Web May Spell Doom! dilettante is offline
Underclocked lifestyle

Forum Leader
* Guru *
 
Join Date: Feb 2005
Location: Michigan, USA
Posts: 4,524
Default

Every time I see this thread title I think:

"Somebody should record this song 'Code Snippets From the Web' sung to the tune of 'Ghost Riders.'"

Last edited by dilettante; 05-28-2016 at 09:20 AM.
Reply With Quote
Reply

Tags
reseed, private, double, const, idxlim, init, array, qword, rnd, code, q.l, qrndd, randomi, indicies, lngmax, element, algorithm, rswp, xor, randomize, ulngcnt, type, function, qpc, scalei


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom! Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
 
Code Snippets From the Web May Spell Doom!
Code Snippets From the Web May Spell Doom!
 
-->