Date: Wed, 4 Jun 1997 19:48:42 +0100 (BST) From: George Foot To: Chris Croughton cc: djgpp AT delorie DOT com Subject: Re: Random numbers In-Reply-To: <97Jun4.141151gmt+0100.16652@internet01.amc.de> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Precedence: bulk On Wed, 4 Jun 1997, Chris Croughton wrote: > There is/was a term for 10^9 - milliard. As far as I know it's not in > use in Britain now at all, but it does still exist and is used in German > (I assume that's where it entered the English language). It's in my dictionary as `Brit. (no longer in technical use)'....`[C19: from French]'. > Incidentally, why do you say that the old British definition is "more > logical"? I agree with you that it's better, but that's at least > partly prejudice on my part, I'm not aware of any logical basis for > preferring it. It's the similar to the difference between the arabic numbering system and the Roman system; in the Roman system they invent a new symbol for each new power of ten, so inevitably it gets very complex very quickly. In the Arabic system we can reuse symbols unambiguously, so we don't need so many different symbols. The analogy isn't perfect, I know. Expressing numbers with a thousand equal to 10^3, million=10^6, billion=10^12, etc. you can write the number (10^24)-1, while in the American system you only get up to (10^12)-1. Unfortunately the British system then defines a trillion as 10^18, which is inconsistent (should be 10^24). > Re: your 'ideal' function - that's about what I've come up with as > well, but it does tend to be rather slower. However, without an > infinite number of bits any other method does suffer from rounding > and 'edge condition' errors with moduli which aren't powers of 2. Yes, of course finding a number in the range [0,2^n] (inclusive) is around twice as slow as if it were only up to and including (2^n)-1 since it's rejecting half the results (for large n). It might be better to multiply the range by an odd number in some cases - then divide the number once you obtain it. The idea behind this multiplication is to push the top number as near as possible to the power of two above it. I haven't thought too much about this, but consider the following cases: You want numbers in the range [0..8]. Running the mentioned function would result in rejection of 7 out of 16 sttempts. Multiply the range by three giving [0..24]. Now we only reject 7 out of 32 Multiply by 5 giving [0..40]. Now we reject 23 out of 64 (bad) Multiply by 7 giving [0..56]. Now we reject 7 out of 64. Now consider finding a number in the range [0..9]. Normally we would reject 6 out of 16, or 3 out of 8. Multiplying by three gives [0..27], rejecting one in eight. Multiplying by seven gives [0..63], requiring no rejection at all. It seems to work best with numbers of the form (2^m)-1. I am not sure what the best way of finding these multipliers is (except trial and error). Clearly there is no point in using even numbers. If you were going to be taking a lot of numbers in a certain range, the calculation of the multiplier could be moved outside the function, and the only speed defecit in the function compared to picking in a range which is a power of two would be the occasional (minimised) rejection and a division before returning. I'm not sure, though, that this is the best place to discuss this sort of algorithm - people in mathematical groups probably already have stock answers to these questions :) -- George Foot Merton College, Oxford