Mail Archives: djgpp/1997/06/04/14:50:40
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 <mert0407 AT sable DOT ox DOT ac DOT uk>
Merton College, Oxford
- Raw text -