-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Tony Godshall wrote: > On 10/17/07, Tony Godshall <[EMAIL PROTECTED]> wrote: >> On 10/17/07, Micah Cowan <[EMAIL PROTECTED]> wrote: >>> -----BEGIN PGP SIGNED MESSAGE----- >>> Hash: SHA256 >>> >>> Tony Godshall wrote: >>>>> Well, I'm don't have much to say about about the other points but one >>>>> certainly does not need to keep an array for something like this- with >>>>> the classic pseudorandom shuffle algorithm you only need to keep a >>>>> count of the ones visited. Shall I pull out my Knuth? >>> That... only applies if you actually keep a _queue_ around, of all the >>> ports that you plan to try, and shuffle it. Surely that's more waste >>> (65,535 shorts, versus 65,535 _bits_), not less? ...We're not shuffling, >>> here, we're choosing. >> No, the point was that with a relative prime or two you can walk in a >> pseudorandom pattern though, hitting each point only once needing no >> array at all. > > Donald E. Knuth, The Art of Computer Programming, Volume 2, 3rd > Edition, pp. 17-19
For the record, this is not what "pseudo-random shuffle" means to me: for instance, http://en.wikipedia.org/wiki/Fisher-Yates_shuffle (aka "Knuth shuffle"), which does in fact require an in-memory set to be permuted. Yes, that appears to work quite well, as long as we seed it right; starting with a consistent X₀ would be just as bad as trying them sequentially, and choosing something that does not change several times a second (such as time()) still makes it likely that multiple invocations will choose the same first port. Probably, /dev/random as first choice, falling back to by gettimeofday() where that's available. I don't know what Windows would use. We could probably use time() as a last resort, though I'm not crazy about it; maybe it'd be better to fail to support port ranges if there's not a decent seed available, and support exact port specifications. Thanks for the suggestion, Tony. - -- Micah J. Cowan Programmer, musician, typesetting enthusiast, gamer... http://micah.cowan.name/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHF9b37M8hyUobTrERCCI2AKCSbpAs60wVZGvnOQN3y44HF64wegCgjYxo Nczvd/z7HVWMH0FfN/zWe28= =YID8 -----END PGP SIGNATURE-----
