Best search algorithm to find condition within a range

[Grant Edwards]

On 2015-04-09, Chris Angelico <rosuav at gmail.com> wrote:
> On Fri, Apr 10, 2015 at 2:53 AM, Grant Edwards <invalid at invalid.invalid> wrote:
>> On 2015-04-09, Chris Angelico <rosuav at gmail.com> wrote:
>>
>>> For application work, it's usually much better to have an integer
>>> type like Python's or Pike's int - a signed integer that can never
>>> overflow. For low-level bit manipulation work, you usually want an
>>> *unsigned* integer of specific size, with well defined wrap-around
>>> behaviour. When do you actually want a signed integer with
>>> well-defined overflow behaviour?
>>
>> http://en.wikipedia.org/wiki/Binary_scaling#Binary_angles
>
> Huh, interesting. (Trust the list to have an answer to a rhetorical
> question, though to be honest, I should have expected that there'd be
> some.) A cursory glance at that Wikipedia page suggests that unsigned
> wrap-around can be used just as effectively, though, so I'm not sure
> this is at all an argument for standardizing the behaviour of signed
> wrap-around.

Applications that use BAMs depend on the fact that you can treat them
as either signed or unsigned values and get correct results.

Relative headings are often treated as signed values with 0 meaning
"straight ahead" with deltas to the right/starboard as positive and
deltas to the left/port as negative. If I were to add three (or seven,
or eleven) -90 degree deltas to my heading of 0, I'd expect end up
with a relative heading of +90.  That depends on signed overflow
working correctly.

Absolute headings (e.g. relative to North), are often treated as
unsigned values.  If I start with a heading of 300, add 90 degrees, I
would expect to get an answer of 30.

That means you can freely mix signed and unsigned BAM values, and then
treat the result as either signed or unsigned, and you still get the
right answer.

With most 2's compliment ALU hardware, you get the desired signed
overflow/underflow "for free" because at the gate level it's exactly
the same as the unsigned behavior.

And back in the day, if you let the Navy pick the CPU, there was even
a single machine instruction that would convert a register pair from a
cartesian (X,Y) tuple to a polar (t,r) tuple (or vice versa).  And the
t value was in BAMs.  The various trig transcendental instructions
worked with angles in BAMs.

Python was not availble for that platform, so this is a bit of a
digression. :)

-- 
Grant Edwards               grant.b.edwards        Yow! Do you think the
                                  at               "Monkees" should get gas on
                              gmail.com            odd or even days?