Reduce this loop to an equation

Question

This function (written in C for convenience, but this is not important to the question) determines the size of an array. I'm sure it can be converted to an if-else chain or even to an equation, but I am not clever enough to see how. (I tried to write down the obvious if-else chain but got bogged down in cases.)

// 0 <= from <= 0x10FFFF
// 1 <= len <= 0x10FFFF
unsigned int size_for_block(unsigned int from, unsigned int len)
{
  unsigned int size = 0;
  for (unsigned int i = 0; i < len; i++) {
    unsigned int point = from + i;
    if (0xD800 <= point && point <= 0xDFFF)
      ;
    else if (point <= 0xFFFF)
      size += 1;
    else
      size += 2;
  }
  return size;
}

If there is a general, idiotproof technique for converting this kind of loop to arithmetic, that would be an ideal answer. Failing that, the solution for this instance would be fine.

score 2 · Answer 1 · answered Jan 24 '14 at 20:29

First, for simplicity:

to = from + len - 1

I think it could be broken into 3 equations, for each "section". That is:

A: 0 to 0xD800 - 1
B: 0xD800 to 0xDFFF
C: 0xDFFF + 1 to infinity

Section A and C are "worth" 2, and B is worth 1. Unless I have misinterpreted your code -- is there only 2 sections?

So multiply each section value by the length of the range that falls within it:

A: if (from < 0xD800) size += 2 * min((0xD800 - 1) - from + 1, len)

Assuming min is a function that returns the lesser of its arguments: The range is "from to the end of the section, or len, whichever is shorter". Range is (end - start + 1).

B: if (to > 0xD800) size += 1 * min(0xDFFF - 0xD800 + 1, to - D800 + 1)

The logic is similar here: "the full section, or the beginning of the section to to, whichever is shorter".

C: if (to > 0xDFFF + 1) size += 2 * (to - (0xDFFF + 1) + 1)

This is simpler because there is no end point: just count from the beginning to to.

I have no idea if this would be more efficient for a computer. It's definitely less efficient for my brain, though.

There are actually *four* regions: 0 to 0xD7FF, D800 to DFFF, E000 to FFFF, and 10000 on up, worth 1, 0, 1, and 2 respectively. I like the *idea* here, but the additional region makes it messier than I am entirely happy with. This is part of an automated test, and the test is too slow, which is why I was trying to optimize it, but I could be persuaded that it's easier to understand the way it is and that's more important... — zwol, Jan 24 '14 at 20:46

score 0 · Accepted Answer · answered Jan 25 '14 at 04:07

By combining nmclean's answer and the concept from this question, I now have this:

function overlap(min1, max1, min2, max2) {
  return Math.max(0, Math.min(max1, max2) - Math.max(min1, min2));
}
size = (overlap(from, from+len, 0x000000, 0x00D800) +
        overlap(from, from+len, 0x00E000, 0x010000) +
        overlap(from, from+len, 0x010000, 0x110000)*2);

which I have exhaustively tested to always produce the same results as the original, and which clearly shows how to do this sort of thing in the general case.

Reduce this loop to an equation

2 Answers2