Mail Archives: djgpp/1997/06/05/03:13:58
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 <g>.
[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 <g>). 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 <g>.
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
- Raw text -