Re: Algorithm for inserting numbers in a list?

In article <7zk5j7igep.fsf@xxxxxxxxxxxxx>,
Torben ^Fgidius Mogensen <torbenm@xxxxxxxxxxxxx> wrote:
Use rational numbers. The first element you put into the list is
given the number 1/1. When you add new elements to the list, you use
the following rules:
- If inserting between elements with numbers a/b and p/q, assign the
number (a/b+p/q)/2 = (a*q+b*p)/(2*b*q). [...]

A simpler version of Torben's rules is to start with two
"virtual" members at 0/1 and 1/0; a new element between a/b and p/q
is assigned the number (a+p)/(b+q). The first "real" entry will be
assigned 1/1; the edge-cases work automatically; and numbers are
always in lowest terms with no further calculation. This is basically
the "Farey" construction of the [positive] rationals.

Torben's construction is also very similar to the "Conway"
construction of the surreals; the next entry between x and y is
the "simplest" number z such that x < z < y, where (a) binary
rationals [p/2^q with p, q integers] are simpler than other numbers,
(b) p/2^q is simpler than r/2^s [p, q, r, s integers] if q < s and
(c) p is simpler than s [p. s integers] if |p| < |s|. [This looks
much more complicated than it really is.]

If you represent the fractions as real numbers, you need unbounded
precision, as an inserted number requires more bits of precision than
the neighbouring numbers. Likewise, if you represent the fractions as
pairs of integers, you need unbounded integers, as the denominator of
the inserted number will be bigger than the neighbours.

Well, quite. If we are not allowed to change the numbers when
we "re-balance" the structure, then any scheme is going to require
unbounded precision; you are always defeated by a perverse "opponent"
who supplies the "next" element in the "smallest" [in the sense of
needing the most precision] extant gap.

OTOH, if the newcomers are supplied in batches, then you may
be able to do better, because you may know, by first sorting them,
that you need to insert [say] 5 elements between [say] 0.5 and 0.8, in
which case inserting them at 0.55, 0.6, 0.65, 0.7 and 0.75 makes more
sense than inserting the first at 0.65, the next at 0.775 and so on.
Adapting Torben's scheme to this scenario is left as an exercise ....

--
Andy Walker
Nottingham
.

Relevant Pages