Re: hap.random: a new random number library for D
On Thursday, 19 June 2014 at 21:27:17 UTC, Joseph Rushton Wakeling wrote: I realized that it ought to be possible to allow a more direct drop-in replacement for std.random by adding static opCalls to the classes which were previously structs. Thoughts on this, in favour, against ... ? I'd say do it and make it @deprecated ... in general, I think allowing a struct like constructor for a class is bad style (at least for std, anyway) and should be discouraged, but deprecating it makes it an easy upgrade initially and will make it easier for people to compare the old vs new way with their code.
Re: hap.random: a new random number library for D
On Wednesday, 11 June 2014 at 16:35:31 UTC, Kagamin wrote: In some scenarios impredictability is not enough. For example, when you generate a session id, an attacker doesn't have to predict it ahead of time, he can guess it at any time later. And if they listen to radio waves - that's an open protocol, an attacker can setup antenna near their antenna and get the same readings. Cryptographic PRNG and quantum TRNG are better isolated, so it's harder to read them. That's an interesting thought on a potential attack. I wouldn't say same readings but similar readings is possible and might make attacks easier. It might not be a bad idea as part of a solution though, since it can be used to supplement other sources of local-machine crypto-grade entropy (since often such sources are exhaustible). But yes, just straight up using it alone appears to have a few critical problems.
Re: hap.random: a new random number library for D
On Wednesday, 11 June 2014 at 06:41:34 UTC, Joseph Rushton Wakeling wrote: Done :) ... if I get a response, I'll make sure to incorporate everything said. Great, let me know how that goes. :-) Well, the ultimate conclusion of the conversation with the guy is that: 1. ISAAC probably isn't cryptographically secure. Despite not having found any attacks, it just isn't proof of security. It's not been looked at enough to really approve of its usage for that purpose (I'm kind of agreeing with this) 2. ISAAC in his opinion probably isn't appropriate for non secure uses for much the same reason. I don't agree with that because everything I've seen for ISAAC shows that it has some really good statistical properties. Even if it's not cryptographically secure, it appears to produce better pseudorandom numbers to me than something like MT19937 or Well* (and ISAAC is really fast after the initial cost has been paid back) Ultimately, I think ISAAC (and ISAAC-64) _will_ get more scrutiny in the future as it's a PRNG used in Rust, for instance. I would not suggest it for default purposes, but I think having it as a non-crypto RNG in D wouldn't be a bad idea for those who want to choose to use it. 3. Better ideas for crypto PRNGs are AES-CTR or Salsa20. I agree with this approach for the crypto section of std.random. I'd also suggest Blum Blum Shub as another thing to add. It's awfully slow, but it's probably one of the few PRNGs that is provably strong (that is, it's been reduced to a known hard problem). Also, he suggested me to refer to a presentation he made last year: http://aumasson.jp/data/talks/randomness_hackepfl13.pdf I've gone through it and it looks like excellent reference material. Note slide 76 saying: Don't use RaaS (things like random.org) - random bits may be shared or reused. Also, it has suggestions for entropy on Windows (CryptGenRandom) which is something that will be necessary as well. Overall, very enlightening.
Re: hap.random: a new random number library for D
On Thursday, 12 June 2014 at 17:35:39 UTC, Nick Sabalausky wrote: Naturally, it doesn't yet exist in hap.random because, as Joseph said, hap.random's step one is to match the current std.random as closely as possible. I'd be happy to put together a PR to adapt my RNG stuff above to hap.random whenever it would be desired. Wow! Looks great :) Thanks for all the work on that.
Re: hap.random: a new random number library for D
On Wednesday, 11 June 2014 at 06:41:34 UTC, Joseph Rushton Wakeling wrote: That would be very cool. Can you point me at your code examples? It's written in Nimrod (in a way that someone who learned Nimrod the day before would write them, because I learned Nimrod the day before and worked on it for something like 17 hours straight to produce everything): https://github.com/Zshazz/Ramrod/blob/master/util.nim I'd like to make this concept a range in D. Not sure what exactly to call it but it's an adaptor. Honestly, I wouldn't be surprised if something like this didn't already exist in D in some form, but it didn't seem like Nimrod had anything like it. The paranoiac in me feels that anything that involves getting random data via HTTPS is probably insecure crypto-wise :-) Paranoia is good in this case. I appreciate the caution. However, I think sourcing random.org is a perfect case for an entry in hap.random.device. I think the best thing to do would probably be to offer a RandomOrgClient (which offers a very thin API around the random.org HTTP API) and then to wrap that in a range type that uses the client internally to generate random numbers with particular properties. This sounds like it would be beautiful. As a note, if we expose this via a part of the standard library, we would have to make certain that we follow the guidelines outlined on random.org (in particular, I'm concerned about having an internal locking mechanism to prevent multiple threads from asking for bits at the same time because that will cause clients to be banned ... global state, impurity, and all the nasty things will likely have to be a natural part of such a thing). Also a very interesting suggestion. Is there a standard name for this kind of procedure? I'm not really aware if there is. I remember hearing about the concept when talking with my cryptography professor awhile back (it may have even been in a lecture). IIRC, the description used was mixing in entropy, so my first thought is to call it a mix/remix function. Just for clarity, here's how I see things rolling out for the future: * First goal is to ensure the existing codebase plays nice with people's programs and that it works OK with dub, rdmd, etc. and doesn't have any serious architectural or other bugs. The 1.0.0 release will not have any new functionality compared to what is in place now. * Once it seems to be reasonably stable then work can begin on a 1.x release series that brings in successive pieces of new functionality. I like this procedure. Definitely confidence inspiring.
Re: hap.random: a new random number library for D
Awesome! I'll definitely check this out :) Would there be any chance of additional contributions, such as an ISAAC RNG implementation, being accepted? I wouldn't go as far as to guarantee it for crypto purposes, but I've been messing around with an implementation recently and wouldn't mind porting it over to D (it's based on the public domain implementation found on this website: http://burtleburtle.net/bob/rand/isaacafa.html ) So far the numbers it puts out appear to be pretty good from my observations, PLUS it's really fast for a large number of outputs (it costs a lot up-front, however). I also have a variation of ISAAC+ as described by the paper here: http://eprint.iacr.org/2006/438.pdf The problem I have with ISAAC+, though, is that the paper incorrectly describes the original ISAAC algorithm (Algorithm 1.1 fails to `xor a` at line 6) so it's unclear whether the paper actually solves a problem. Furthermore, I'd really prefer to keep that xor regardless (because it may have simply been an oversight but intended) so it's hard (I don't want to) to really call it ISAAC+ since it is notably different than the paper's description. That said, it's a paper that comes up often enough in discussions about ISAAC that people suggest a desire for it.
Re: hap.random: a new random number library for D
Hey again Joe, I had an opportunity to give the entire code a good once over read and I have a few comments. 1. Biggest thing about the new hap.random is how much nicer it is to actually READ. The first few times I went through the current std.random, I remember basically running out of breath. hap.random was almost a refreshing read, in contrast. I'm guessing it has a lot to do with breaking it down into smaller, more manageable pieces. Regardless, good work on that. I suspect it'll make it easier to contribute to in the future. 2. Something I'd really like to see is for the seed-by-range functions to take the range by reference instead of by value to ensure that the seed values used are less likely to be used in another RNG inadvertently later. Basically, I envision a similar problem with seedRanges as we currently have with RNGs where we have to make sure people are careful with what they do with the ranges in the end. This should cover use cases where users do things like `blah.seed(myEntropyRange.take(3))` as well, so that might take some investigation to figure out how realistic it would be to support. 3. I'd also REALLY like to see seed support ranges/values giving ANY type of integer and guarantee that few bytes are wasted (so, if it supplies 64-bit ints and the generator's internal state array only accepts 32-bit ints, it should spread the 64-bit int across two cells in the array). I have working code in another language that does this, and I wouldn't mind porting it to D for the standard library. I think this would greatly simplify the seeding process in user code (since they wouldn't have to care what the internal representation of the Random state is, then). 4. I'd just like to say the idea of using ranges for seeds gets me giddy because I could totally see a range that queries https://random.org for true random bits to seed with, wrapped by a range that zeroes out the memory on popFront. Convenient and safe (possibly? Needs review before I get excited, obviously) for crypto purposes! 5. Another possible improvement would be something akin to a remix function. It should work identically to reseeding, but instead of setting the internal state to match the seed (as I see in https://github.com/WebDrake/hap/blob/master/source/hap/random/generator.d#L485), remixing should probably be XOR'd into the current state. That way if you have a state based on some real entropy, you can slowly, over time, drip in more entropy into the state. 6. I'd like to see about supporting xorshift1024 as well (described here: http://xorshift.di.unimi.it/ and it's public domain code, so very convenient to port ... I'd do it too, of course, if that seems like an okay idea). This is a really small thing because xorshift1024 isn't really much better than xorshift128 (but some people might like the idea of it having significantly longer period). Why not write to the paper's author and ask about it? Done :) ... if I get a response, I'll make sure to incorporate everything said.
Re: So, You Want To Write Your Own Programming Language?
On Monday, 27 January 2014 at 09:19:25 UTC, Kagamin wrote: On Thursday, 23 January 2014 at 10:24:23 UTC, Chris wrote: A good example are headlines. A classic is Driver refused license. Now, everybody will assume that it was not the driver who refused the license (default assumption or the _unmarked case_). Why it's not a driver who refused a license? More likely that it's a driver who was refused a license by the State (because of some reason such as you've been caught drinking and driving 20 times so you're totally banned). People aren't offered licenses and accept or reject them, they must seek them out. It doesn't make sense for someone to walk up (or be given a ride to by a friend) to the DMV wait 30 minutes and once they do all the work to get the license say Wait, no, I refuse this after all. So, despite Driver refused license possibly meaning the driver refused to accept the license despite being able to or driver was refused a license by the State (due to some circumstance), it's massively more likely to be the latter.
Re: legacy code retreat's triva game : the D version
On Sunday, 22 December 2013 at 08:06:30 UTC, Marco Leise wrote: Can you elaborate a bit? How do you know that the Java LCG can produce every 32-bit integer once? If that's true then the problem with the Java code was something different and I was just biased, because I was already expecting the code to fail before the fact. (Expectations can do strange things to your perception.) If I may, http://en.wikipedia.org/wiki/Linear_congruential_generator Definition of an LCG: ``` Xnext = (a * Xprev + c) % m ``` An LCG is said to have a full period if the length of the period is m. If the period is m, we know the LCG must produce every number between 0 and m because if there was even one repeated number then the generator as defined above would repeat the entire sequence up to that point and, thus, the period would not be m, which is a contradiction. According to the Hull-Dobell Theorem, an LCG will have a full period iff: 1. `c` and `m` are relatively prime. For Java, c = 11 and m = 2^48 This condition applies. 2. `(a - 1)` is divisible by all prime factors of m` For Java, a = 25214903917 and thus a-1 is even which means the prime factors of m (just 2) do divide it. This condition applies. 3. `a - 1` is a multiple of 4 if `m` is a multiple of 4. For Java, m is a multiple of 4. `(a - 1)/4` is 6303725979, so it's also a multiple of 4. This condition applies as well. Since Java's LCG has a full period over 2^48, we know that taking the top 32 bits (which is what Java does to get better randomness) would also all be represented.
Re: legacy code retreat's triva game : the D version
On Friday, 20 December 2013 at 16:20:44 UTC, marcpmichel wrote:
On Friday, 20 December 2013 at 15:05:07 UTC, bearophile wrote:
marcpmichel:
Here is the ugly thing :
https://github.com/jbrains/trivia/tree/master/d
And wrong:
if (rand.front() % 9 == 7) {
Bye,
bearophile
Do you mean I should have used :
if (uniform(0,10) == 7) {
instead ?
TL;DR version:
Actually, the equivalent would be uniform(0, 9), but yes, that'd
be the preferable approach there. (also note
https://github.com/jbrains/trivia/blob/7b473f9fbbd125b0ab1c2e82582b8a8c414ca501/d/source/trivia.d#L19
too should be changed to `uniform(1, 6)` which will give numbers
in the range [1 .. 6) ... that's what you want, right?)
Long version:
For more information, I've written a document on an
implementation of uniform (which should be coming in 2.065, btw)
which discusses the issue with just using the modulus operator:
https://dl.dropboxusercontent.com/u/2206555/uniformUpgrade.pdf
Generally speaking, this new uniform will be _extremely_ close to
the same speed of just using the modulus operator, but avoids the
bias issue. I think there is no real good reason to not use the
standard function anymore.
That said, the bias with such a small number (9) won't be
significant. If rand gives you a uniform 32-bit number, then the
distribution of rand % 9 will be [477218589, 477218589,
477218589, 477218589, 477218588, 477218588, 477218588, 477218588,
477218588] (notice how the first 4 have 1 more occurrence than
the rest?)... so the bias is miniscule in this case.
The bias issue matters a lot more with larger numbers where some
numbers could actually occur twice as often as others, or if your
application demands high quality random numbers (think gambling
games). Related to those reasons, even if your code doesn't use
large numbers and isn't used for a gambling game now, it's still
possible for it to eventually be used for such things (or to
influence others to follow your example for the bad situations).
For those reasons alone, it's pretty important to get in the
habit of using the standard function.
But that's not all since the standard function is probably easier
to read, too. Let's say you want to emulate a standard 6-sided
die. If you want numbers in the range [1..6] (note inclusive
bounds) it's easier to see immediately when you say
`uniform' rather than `rand % 6 + 1`
That's probably all TMI, but maybe all of that will be useful for
you.
Re: llvm-d
On Saturday, 23 March 2013 at 10:01:19 UTC, Moritz Maxeiner wrote: No problem at all. There is an example quoted in the README and how to compile it, so without further information form your side I don't know what the problem is. To get the example from the README working: - Download/Clone the github repo into a folder (let's say llvm-d) - cd into that folder - execute rdmd -L-ldl sample/multithreaded.d The need for the -dl flag is only for POSIX platforms and will be gone with the next commit as I have included a lib pragma. If the above doesn't help could you please tell me what exactly you have done and at which point you have the problems? -- Moritz Thanks so much. I had dub upgrade the llvm-d package and now I have different problems. That said, I do have a working example (as long as rdmd is used). I have updated the gist (with repro steps): https://gist.github.com/Zshazz/c7dbd6eee0b6b242252b I'm running LLVM 3.2, so the example given in the README doesn't work. But the code in the gist works as long as you run 'dub --rdmd', so that's some progress! Not really sure about the linking problems without rdmd. This is sufficient to start some work with it to really try some things out, though. I'll keep messing around with it. It seems like you already know that JIT doesn't work because we need InitializeNativeTarget. That all said, the tutorials, instructions, and documentation for the C API of LLVM is pretty sparse. The best I've seen to figure out how things work is to go through http://llvm.org/doxygen/modules.html and piece together (very slowly) how something might work. I'm also having to cross reference tutorials made for the C++ API and figure out how to make it work in C by reading the raw source code to get the equivalent calls. Fortunately I did find that one post that gave a close-to-complete example in C. Is there any better way to do this at this point? Thanks again.
Re: llvm-d
On Saturday, 23 March 2013 at 21:19:14 UTC, Moritz Maxeiner wrote: TLDR: Your example should now work, provided you fix what I previously mentioned. You can also look at sample/fibonacci.d which I used instead of your fac to confirm that you gist now works. - Moritz Awesome. Indeed, it now fully works (and JIT does work after all! Thanks for showing me how to use that). Thanks for the more interesting example in the README, it's extremely helpful. And also thank you for taking some time to help with the issues I was having.
Re: llvm-d
On Friday, 15 March 2013 at 17:40:36 UTC, Moritz Maxeiner wrote: Hi, I would like to announce llvm-d, which provides LLVM bindings for D. Greetings, I hope you don't mind a bit of a support request, but I'm having difficulties getting it to work: https://gist.github.com/Zshazz/c7dbd6eee0b6b242252b The code is from http://npcontemplation.blogspot.com/2008/06/secret-of-llvm-c-bindings.html but with slight updates (and obviously fixing syntax to work in D). This is running on Manjaro Linux (a derivative of Archlinux) and using DMD v2.062. Thanks for your time.
Re: OT: Speed reading (was: Re: The best programming advice I ever got)
On Thursday, 30 August 2012 at 23:18:34 UTC, Nick Sabalausky wrote: I can usually identify speed readers when emailing because they're the ones whose responses clearly indicate they totally missed at least half --snip-- Look, I'm sure you've just met some poor speed readers. And your point about speed readers not being good at reading dictionaries and something about wearing flip flops is wrong. I wear normal shoes, thank you very much. ... :p
