Re: Better use of random number generator bits?
- From: James Waldby <j-waldby@xxxxxxxx>
- Date: Tue, 07 Mar 2006 23:49:48 -0700
James Waldby wrote:
DAC wrote:....
"James Waldby" ... wrote ...
Ben Rudiak-Gould wrote:
DAC wrote:[in "Better use of random number genator bits?" thread]
Although for half a minute I thought about writing a program,....
I ended up spending about 15 minutes on trial and error with
the bc calculator program to get the above.
Also the 10 9 8 7 6 5 4 3 2 1 multiple isn't very good (only
85% success rate), I have gone for 15bit 10 9 8 7 6 and
7bit 5 4 3 2 1, on average this uses just 232 bits! Very nice.
I am sure there must be some mathetmatical
way to calculate the best distribution of the multiples!
Since this resembles a bin-packing problem (ie, fitting
sums of logs into integer-size bins) I think it would be
difficult to find a conclusive method that performs much
better than exhaustive enumeration. However, dynamic
programming probably can solve it fairly quickly.
I meant to say that the dynamic programming approach I was
thinking of doesn't solve the general problem, but instead
just the limited case of grouping adjacent numbers together.
The dynamic programming equation for the minimum cost of
covering numbers from L to R is: cost(L,R) = min (cost(p),
min{j}(cost(L,L+j)+cost(L+j+1,R))), where p is the product
of numbers L, L+1, ... R, and j ranges from 0 to R-L-1, and
obvious boundary conditions. The solution value is cost(1,52).
For example, if your computer does arithmetic with 221-bit
words or larger, the optimal grouping of adjacent numbers
is 1 with 2; 3 by itself; 4 by itself; and 5-52 grouped
together. The expected number of bits used is 227.274,
vs. log_2(52!) ~ 225.581. See http://pat7.com/jp/adj-opti.c
for a program that computes the optimal solutions for word
sizes from 6 bits up to 256 bits, in 0.7 seconds on a 900
MHz machine. For 32-bit words, it shows 243.216 bits
expected, of course not as good as the 232-expected-bits
method mentioned above (where adjacency is not considered).
-jiw
.
- References:
- Better use of random number genator bits?
- From: DAC
- Re: Better use of random number genator bits?
- From: Ben Rudiak-Gould
- Re: Better use of random number generator bits?
- From: James Waldby
- Re: Better use of random number generator bits?
- From: DAC
- Better use of random number genator bits?
- Prev by Date: Re: trig question
- Next by Date: Posts being made in my name
- Previous by thread: Re: Better use of random number generator bits?
- Next by thread: Re: Better use of random number genator bits?
- Index(es):
Relevant Pages
|
