Sender: crough45 AT amc DOT de Message-Id: <97Jun5.090644gmt+0100.16654@internet01.amc.de> Date: Thu, 5 Jun 1997 08:04:36 +0100 From: Chris Croughton Mime-Version: 1.0 To: george DOT foot AT merton DOT oxford DOT ac DOT uk Cc: djgpp AT delorie DOT com Subject: Re: Random numbers Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Precedence: bulk George Foot wrote: > It's in my dictionary as `Brit. (no longer in technical > use)'....`[C19: from French]'. I don't have my Concise OED here in Germany to check such things, unfortunately, or I could have looked it up myself. Quite possibly it entered German from French, then, there's a surprising number of words which have done that. > 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). Hmm, the exponent is itself exponential. I hadn't looked at it like that. It's a pity that there's that 3 in there, though, I'd have preferred 2 . [big snip] > Multiply the range by three giving [0..24]. Now we only > reject 7 out of 32 Err, not correct. The range [0..8] is 9 numbers, not 8, so you need to use your calculations for 9 (best fit 9*7=63). But the principle is right. If you take your figures, although you do generate all numbers in the range the top one only has one 'hit'. In the general case, for a range of n results, you need a multiplier m such that: n * m <= 2^k for integral k <=0. Thus for a range of 8 ([0..7] for instance) setting k=3 and m=1 is sufficient, for a range of 9 k=6 and m=7 (as above), a range of 10 gives k=5 and m=3 etc. > 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). It does look as though there ought to be a general solution (says the person who dropped out of university maths to do just computing ). But although (2^m)-1 multipliers seem to work for ranges just over 2^n, for ones much bigger they seem to be not as good (11*11 is 121 which is close to 128, for instance, or even better 11*23=253 or 11*93=1023 which gives a 'perfect' match, one reject in 1024). For an efficient function where the ranges are known it would probably be best to pass the constants in as parameters. Something like: int randomInRangeByMultiplier(int range, int k, int m); Or even better do it as an inline function. > 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 :) Probably. But according to your .sig you seem to be in an ideal place to find out - Oxford University has a very good maths department as I recall . I'd be interested in continuing by email, though. In fact if there's interest I'd be willing to set up a mailing list (nothing like as sophisticated as DJ's, I don't have permanent net connection!). Unfortunately I don't have newsgroup access here. Chris C