Mapping a continuous range into discrete bins in C++

user_12926646 0
Viewed 453

I've inherited maintenance of a function that takes as parameter a value between 0 and 65535 (inclusive):

MyClass::mappingFunction(unsigned short headingIndex);

headingIndex can be converted to degrees using the following formula: degrees = headingIndex * 360 / 65536

The role of this function is to translate the headingIndex into 1 of 36 symbols representing various degrees of rotation, i.e. there is a symbol for 10 degrees, a symbol for 20 degrees etc, up to 360 degrees in units of 10 degrees.

A headingIndex of 0 would translate to displaying the 0 (360) degree symbol.

The function performs the following which I can't seem to get my head around:

const int MAX_INTEGER = 65536;
const int NUM_SYMBOLS = 36;
int symbolRange = NUM_SYMBOLS - 1;
int roundAmount = MAX_INTEGER / (symbolRange + 1) - 1;
int roundedIndex = headingIndex + roundAmount;
int symbol = (symbolRange * roundedIndex) / MAX_INTEGER;

I'm confused about the algorithm that is being used here, specifically with regard to the following:

  1. The intention behind roundAmount? I understand it is essentially dividing the maximum input range into discrete chunks but to then add it on to the headingIndex seems a strange thing to do.
  2. roundedIndex is then the original value now offset or rotated by some offset in a clockwise direction?

The algorithm produces results such as:

headingIndex of 0     --> symbol 0
headingIndex of 100   --> symbol 1
headingIndex of 65500 --> symbol 35

I'm thinking there must be a better way of doing this?

range math algorithm c++
3 Answers

The shown code looks very convoluted (it is possibly a guard against integer overflow). A far simpler way to determine the symbol number would be code like the following:

    symbol = (headingIndex * 36u) / 65536u;

However, if this does present problems with integer overflow, then the calculation could be done in double precision, converting the result back to int after rounding:

    symbol = static_cast<int>( ((headindIndex * 36.0) / 65536.0) + 0.5 ); // Add 0.5 for rounding.
user_108710730

You have 65536 possible inputs (0..65535) and 36 outputs (0..35). That means each output bin should represent about 1820 inputs if they are divided equally.

The above formula doesn't do that. Only the first 54 values are in bin 0, then they are equally divided across the remaining 35 bins (MAX_INTEGER/symbolRange). About 1872 per bin.

To show this, solve for the lowest value of heading where symbol is 1. 1 * 65536 = 35 * (headingIndex + 1819) so headingIndex == 53.

stark_12167760

If you want to keep the output the same but tidy it up. Walk away. There are odd features of that method that may or may not be what is desired.

The range for headingIndex of 0 - 53 gives a symbol of 0. That's a bucket (AKA bin) of 54 values. The range of 63717 - 65535 give 35. That bucket is 1819 values. All the other buckets are either 1872 or 1873 values so seem 'big'.

We can't have equal sized buckets because number of values is 65536 and 65536/36 is 1820 and 16 remainder. So we need to bury the 16 among the buckets. They have to be uneven in size.

Notice the constant MAX_INTEGER is a red herring. The max is 65535. 65536 is the range. The chosen name is misleading from the start.

Why:

int symbolRange = NUM_SYMBOLS - 1;
int roundAmount = MAX_INTEGER / (symbolRange + 1) - 1;

when the second line could be int roundAmount = MAX_INTEGER / MAX_SYMBOLS - 1;

It doesn't look quite thought through is all I'm saying. But looks can be deceptive.

What also bothers me is the 'obvious' method proposed in other answers works great!

int symbol=(NUM_SYMBOLS*headingIndex)/(MAX_INTEGER);

Gives us buckets of either 1820 or 1821 with an even distribution. I'd say that's the natural solution to the head question.

So why the current method? Is it some artefact of some measuring device? I'll put money the maximum value is 65535 because that's the maximum value of an unsigned 16-bit integer.

It's right to wonder about overflow. But if you're working in 16-bits it's already broken. So I wonder about a device that is recording 16-bits. That's quite realistic.

This is similar to what I know as "The Instalments Problem". We want to the customer to pay £655.36 over 36 months. Do they pay £18.20 a month totalling £655.20 and we forget the 16p? They won't pay £18.21 totalling £655.56 and overpay 20p. Bigger first payment of £18.36 and then 35 of £18.20? People wrestle with this one. The business answers are 'get the money' - bigger first payment. Avoid complaints if they owe you money (big last payment) and forget the pennies (all same - we're bigger than a few pence!).

In arithmetic terms for a measurement (such as degrees) I'd say the sprinkled method offered is the most natural, even and distributes the anomaly evenly.

But it's not the only answer. Up to you. Hint: If you haven't been ask to fix this and just think it's ugly - walk away. Walk away now.

user_42136620
Related