Coding Help

| 23 Comments

I’m working on a little education project for this site that requires a good binomial random number generator written in javascript. I’m having a hard time finding a library written and would rather not write one myself. So I’m wondering if any of the tech-savvy people who read this blog are willing to port the code for generating a binomial random variable from GSL to javascript. You can depend on the jQuery library if it helps.

Any takers?

23 Comments

I used to make my own random number generators for various distributions by employing a uniform random number generator.

The basic idea is to generage a random number within the range of the distribution you are using. Then use this random number to calculate the height of the probability density function at that number.

To decide whether or not to keep this first generated random number, generate a second random number normalized to the maximum height of the probability density function.

If the second random number falls below the probability calculated using the first random number, keep the first random number. Otherwise, throw everything away and begin again.

Thus, the probability of keeping the first random number is the same as the probability that the second random number falls below the corresponting probability density function.

A quick google turned up this page:

http://www.ciphersbyritter.com/JAVA[…]HTM#Binomial

Does it do what you want?

Regards,

Derek Tattersall

Derek Tattersall said:

A quick google turned up this page:

http://www.ciphersbyritter.com/JAVA[…]HTM#Binomial

Does it do what you want?

No, that page is calculating the shape of the binomial distribution. I want efficient code that can sample from one.

Mike Elzinga said: Thus, the probability of keeping the first random number is the same as the probability that the second random number falls below the corresponting probability density function.

I’m not asking how to generate a binomial random variable, I’m familiar with the algorithms and the theory. I just want one in javascript format that I don’t have to port myself. The temporary one that I’m using builds the binomial from a sum of Bernoulli trials, but that’s inefficient when population sizes get large.

Reed A. Cartwright said:

Mike Elzinga said: Thus, the probability of keeping the first random number is the same as the probability that the second random number falls below the corresponting probability density function.

I’m not asking how to generate a binomial random variable, I’m familiar with the algorithms and the theory. I just want one in javascript format that I don’t have to port myself. The temporary one that I’m using builds the binomial from a sum of Bernoulli trials, but that’s inefficient when population sizes get large.

How about the analysis tools in Microsoft Excel? Go to Tools and select Add-ins and get the Analysis tools. There are several random number generators there. Can you use Excel to do what you want to do?

Reed,

From what I can understand from your request and replies, I get the impression that you are having the same problem that I often had.

I could write a short program or function faster than I could find one. I needed to sample from various kinds of distributions.

The method I mentioned requires only a rather short program if you already have access to a uniform random number generator. Scaling the range of the second random number to the maximum of the probability density function greatly increases efficiency, especially for distributions that extend to very large numbers. Given the parameters of the density function, it is easy to calculate its height at any particular value as well as its maximum height.

I certainly agree that using the sum of Bernoulli trials is very inefficient, especially for large numbers.

Mike Elzinga said:

How about the analysis tools in Microsoft Excel? Go to Tools and select Add-ins and get the Analysis tools. There are several random number generators there. Can you use Excel to do what you want to do?

No. I need it as a javascript library because the project that I’m working on is a javascript project. It is a little “game” that will appear on this site, which is why I can’t use C or R, where I already have a PRNG library.

I’m writing this off-the-cuff, with no testing (heck, I’m not even sure it’s syntactically correct), but you can use it. It’s based off of the ideas at http://www.winlab.rutgers.edu/~rito/ece541p1.pdf, but I think it’s the same technique in Knuth (my copy of which is at work).

I am also assuming that a “binomial random variable” is functionally the same as a normal random variable.

// Returns two normal random value with mean 0 and standard deviation 1
function get2Normals()
{ 
  var w = 2;
  var v = []
  while (w > 1) {
    var u = [Math.random(), Math.random()];
    var v = u.map(function (z) {return 2*z-1});
    w = v[0]*v[0] + v[1]*v[1];
  }
  var y = Math.sqrt(-2*Math.log(w)/w);
  var x = v.map(function(z) {return z*y;});
  return x;
}

I can’t get that to format properly…

Reed,

From what you wrote, you already have a good solution for small population sizes. For large sizes, you can just use a normal approximation. A normal random number generator is very simple to implement in Javascript: see this page, for example. The normal approximation works quite well even for relatively small population sizes, as long as the success probability p is not too small all too large - a useful heuristic is to use the approximation if np > 5 and n(1-p) > 5. Your only difficult case is when n is very large and p is very small, in which case you want to sample from a Poisson distribution with parameter Lambda = np. A simple algorithm can be found in this Wikipedia article.

What kind of resolution do you need? (how many unique values in the domain?) If the domain is sufficiently small, one cheap-and-dirty thing that could be done would be to pre-calculate an array containing samples that reflect a binomial distribution frequency of occurance, then index that table with a non-binomial random number. However, if the array is too large you are either paying for bandwidth to transmit it or the client is paying to calculate it on every startup. May not work for your needs… just a thought

I think I need to be more specific. I’m not asking how to implement a binomial random number generator. I’m asking for an implementation, because I can’t find one and don’t have the time to implement one. I’d love to have the gsl_ran_binomial from GSL ported to javascript so I can include it in my project.

Blaise Pascal said:

I am also assuming that a “binomial random variable” is functionally the same as a normal random variable.

Thanks, but I’m going to need a procedure that handles the edge cases eloquently, i.e. when N*p or N*(1-p) is near zero.

Reed A. Cartwright said: I’d love to have the gsl_ran_binomial from GSL ported to javascript so I can include it in my project.

Since you know exactly what you want and you apparently know Javascript, I think you would be better off translating the GSL code instead of discussing here. It is in randist/binomial_tpe.c

Best,

Carsten

Well I thought, javascript is part of the C syntax phylogenetic tree, and presumably this is mostly numeric calculations (no objects, data structures etc), so how hard can it be? I was just looking gsl-1.12/randist/binomial_tpe.c source, trying to gauge the amount of work. It seems to call three other functions which would require translation or javascript substitutions - Stirling() (I assume Stirling’s approximation for n!) which should be no problem, gsl_pow_int() which I assume is x^n, simple enough, and gsl_ran_uniform() which is the usual flat distribution, so translation seemed tractable.

Then I noticed its loaded with “goto”s! gotos?!!! GOTOS?!!! I thought I was seeing things. Jeez, what century is this? Did these guys just translate a fortran program?! BLECHH

Reed A. Cartwright said:

I’m asking for an implementation, because I can’t find one and don’t have the time to implement one. I’d love to have the gsl_ran_binomial from GSL ported to javascript so I can include it in my project.

I hope to have it done later this afternoon, just giving you a heads up. I’d have it done sooner but I have a bit of a drive… (I’m just porting the GSL functions…)

Reed,

Keep in mind that any algorithm you use other than using multiple Bernoullis is going to be an approximation. The GSL function is one such approximation (albeit probably a very good one).

That said, I would be interested in giving it a go; I’ve been needing an excuse to delve into javascript. Keep us posted if you find something else that has already been done, or if someone else does it more quickly.

Regards, Joe

Sean McCorkle Wrote:

Then I noticed its loaded with “goto”s! gotos?!!! GOTOS?!!! I thought I was seeing things. Jeez, what century is this? Did these guys just translate a fortran program?! BLECHH

You think that’s bad? There’s another C library (ranlib.c) that has an implementation of this same algorithm that literally looks like a Fortran program, lots of GOTOs, same variable naming conventions, lots of capital letters, etc. Keep in mind that back in the day, Fortran was the best tool for the job and when scientists starting porting their functions to C they probably didn’t have much incentive to get rid of some of these Fortran quirks. Converting GOTOs to more modern structures can be a real pain and may not have been worth it from a computational efficiency standpoint.

I had a go at doing it, I expect it has errors.

I haven’t had time to work out what this function is all about, plus its my first code in JavaScript.

I expect you know how to test it (I don’t), I don’t have anymore time at the moment to look.

anyway hope its at least a start

goto:

http://www.orieladmin.plus.com/JS/

then right click - view source.

Dan Earle said:

I had a go at doing it, I expect it has errors.

I haven’t had time to work out what this function is all about, plus its my first code in JavaScript.

I expect you know how to test it (I don’t), I don’t have anymore time at the moment to look.

anyway hope its at least a start

Dan (& Reed),

Looks pretty good to me, on superficial inspection anyway. There are two things I would worry about:

  1. Whether there is any effect of moving from “int” and “double” types in C to “var” in Javascript (which are all floating point). This is a limitation of Javascript not a problem with the port. I don’t know enough about how Javascript converts between integers and reals to know whether this is a problem.
  2. Whether the Javascript math.random() function is a good random number generator. I don’t know if there is an alternative (besides porting the GSL uniform random generator as well), but it may be worth a cursory investigation.

Normally, these concerns could easily be addressed by using the same random number seed in both versions and seeing if they give the same answer, but apparently the Javascript math.random() function does not let you choose a seed, but rather creates one automatically from the date and time.

The next best way to test it is to generate a huge set of random numbers using typical values of n and p and see if the probability distribution obtained matches what was expected.

Happy Trails… Joe

Made small change:

realised I could just use some breaks instead of the separate returns on each finish case - just shows you never need to use goto’s.

Joe: Yes it seems JavaScript doesn’t have integer types, so I hope I used the Math.floor in the appropriate places…

Thanks, Dan, for doing the heavy lifting. I haven’t tested it, but I will. I expect that in the end, I’ll make some changes to the organization to convert your global functions into member functions of my “game” object.

Reed: Let me know if you have some test code that finds a problem. Looking forward to the “game” will it be hosted on this site??

Larry_boy: Sorry for beating you to it, hope you didn’t go to too much trouble.

Oh that was a stupid question! you say it will be on this site in your opening entry.

can you plz send source code for development of lost articles and letters reconciliation system to my mail.technoligies used are java applets,JACOB,Mysql

This is just a heads up, seeing as I got here a bit late. I am very good in situations like these and am very available. <one of the joys of bring unemployed.>

Should anyone find themselves requiring problems solved, drop me a line, and I am sure I can help out. I know enough about js to get great joy in making it sit up like a nice puppy, and play well with others.

That Guy

About this Entry

This page contains a single entry by Reed A. Cartwright published on January 17, 2009 5:42 PM.

Freshwater Day 12: The Monitor was the previous entry in this blog.

Freshwater Day 13: A Parade of Teachers & Staff is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.

Categories

Archives

Author Archives

Powered by Movable Type 4.381

Site Meter