• #### Anti-aliasing algorithms

From Rick C. Hodgin@21:1/5 to All on Thu Sep 13 12:10:02 2018
I have a situation where I have three values (v1, v2, v3) and they
have a max value each of 32, but more typically each will be 8 or less.

I need to scale up their values proportionally toward the next
largest multiple of 8 (if they don't already equal a multiple of 8).

For example:

v1 = 2
v2 = 3
v3 = 4

Here we have a total of 2+3+4 = 9, which would need to scale up to
16, being as it's the next multiple of 8.

I need the v1, v2, and v3 values to each scale up proportionally,
so that v3 gets the largest increase, v2 the second largest, and
v1 the smallest.

Mathematically I can determine how much they would scale with an
equation. But v1..v3 are integers, and they need to round to the
nearest integer values to be legitimate, which may require rounding
up in some cases, rounding down in others.

-----
I was thinking this problem seems like an anti-aliasing problem,
where perfect geometry is mapped into integer space, rounding up
to the next pixel, or down to the prior one.

I was wondering if anyone can think of an anti-aliasing algorithm
which would help in this case?

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From =?UTF-8?Q?Hans-Bernhard_Br=c3=b6ker@21:1/5 to All on Fri Sep 14 01:07:23 2018
Am 13.09.2018 um 18:10 schrieb Rick C. Hodgin:

I was thinking this problem seems like an anti-aliasing problem,

It's not.

Aliasing is what happens when you reduce the _number_ of spatially
structured values, rather than same number's scale or precision.

It's not even clear if your "three values" have any sort of spatial organization, which in the case at hand might simplify to ordering. Is
this an ordered tuple, or just three numbers where nobody cares which of
the three is labelled "v1", which v2 and which v3?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Rick C. Hodgin@21:1/5 to All on Fri Sep 14 01:00:05 2018
On 9/13/2018 7:07 PM, Hans-Bernhard Bröker wrote:
Am 13.09.2018 um 18:10 schrieb Rick C. Hodgin:

I was thinking this problem seems like an anti-aliasing problem,

It's not.

Aliasing is what happens when you reduce the _number_ of spatially structured values, rather than same number's scale or precision.

You project a perfect representation of floating point geometry
onto an integer "matrix" and have to approximate coloring of the
fringe pixels based on how much of their area is covered, with
a blend of the color in use, its alpha channel if any, and the
background color you're overwriting.

But the point is, you take floating point values and project
them to integer boundaries. In the case of anti-aliasing, you
use that fractional portion to determine rounding up/down.

It's not even clear if your "three values" have any sort of spatial organization, which in the case at hand might simplify to ordering.  Is this an ordered tuple, or just three numbers where nobody cares which of the three is labelled "v1", which v2 and which v3?

As I see it, the problem relates to the projection algorithm
used to take data from floating point paths to integer features.
And specifically, the math involved in how those values values
are approximated when no anti-aliasing is involved.

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Scott Hemphill@21:1/5 to Rick C. Hodgin on Fri Sep 14 09:47:25 2018
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:

I have a situation where I have three values (v1, v2, v3) and they
have a max value each of 32, but more typically each will be 8 or less.

I need to scale up their values proportionally toward the next
largest multiple of 8 (if they don't already equal a multiple of 8).

For example:

v1 = 2
v2 = 3
v3 = 4

Here we have a total of 2+3+4 = 9, which would need to scale up to
16, being as it's the next multiple of 8.

I need the v1, v2, and v3 values to each scale up proportionally,
so that v3 gets the largest increase, v2 the second largest, and
v1 the smallest.

Mathematically I can determine how much they would scale with an
equation. But v1..v3 are integers, and they need to round to the
nearest integer values to be legitimate, which may require rounding
up in some cases, rounding down in others.

-----
I was thinking this problem seems like an anti-aliasing problem,
where perfect geometry is mapped into integer space, rounding up
to the next pixel, or down to the prior one.

I was wondering if anyone can think of an anti-aliasing algorithm
which would help in this case?

This problem isn't completely specified, because sometimes there is
more than one way to choose which to round up and which to round down.
The case you gave (v1,v2,v3) = (2,3,4) is pretty easy, but how would you
want to round (v1,v2,v3) = (5,8,11) ?

One way to handle this problem does have some resemblence to
antialiasing. You could use "error diffusion". In your case, you would compute (v1,v2,v3) = 16/9 * (2,3,4) = (3.55,5.33,7.11). (I am truncating
the decimals. They repeat, of course.) Then round v1 up to 4. The
error is -0.44. Add that to v2, computing v2 = 5.33-0.44 = 4.88. When
you round v2 up to 5, the error is -0.11. Then compute v3 = 7.11-0.11 =
7. The resulting triple is (v1,v2,v3) = (4,5,7).

Scott
--
Scott Hemphill hemphill@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From =?UTF-8?Q?Hans-Bernhard_Br=c3=b6ker@21:1/5 to All on Sat Sep 15 00:28:54 2018
Am 14.09.2018 um 07:00 schrieb Rick C. Hodgin:
On 9/13/2018 7:07 PM, Hans-Bernhard Bröker wrote:
Am 13.09.2018 um 18:10 schrieb Rick C. Hodgin:

I was thinking this problem seems like an anti-aliasing problem,

It's not.

Aliasing is what happens when you reduce the _number_ of spatially
structured values, rather than same number's scale or precision.

You project a perfect representation of floating point geometry
onto an integer "matrix" and have to approximate coloring of the
fringe pixels based on how much of their area is covered, with
a blend of the color in use, its alpha channel if any, and the
background color you're overwriting.

I.e. exactly what I said: a reduction of the number of values, in this
case from infinitely many to a finite set.

But _nothing_ like that was even remotely hinted at in your actual
problem statement: no geometry, no floating-point data, nothing. Just
three integer numbers with no apparent relation to each other. So
there's no chance to get aliasing, and thus no way apply anti-aliasing.

But the point is, you take floating point values and project
them to integer boundaries.  In the case of anti-aliasing, you
use that fractional portion to determine rounding up/down.

The difference is whether your input data is just a shapeless set of
numbers, or a function of the coordinates in some geometric space: a
"field" Aliasing is an artefact that happens when you sub-sample the
geometric _coordinates_ of the field, quantization is what you reduce
the precision of the field's _values_.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Rick C. Hodgin@21:1/5 to All on Sun Sep 16 07:36:25 2018
On 09/14/2018 06:28 PM, Hans-Bernhard Bröker wrote:
Am 14.09.2018 um 07:00 schrieb Rick C. Hodgin:
On 9/13/2018 7:07 PM, Hans-Bernhard Bröker wrote:
Am 13.09.2018 um 18:10 schrieb Rick C. Hodgin:

I was thinking this problem seems like an anti-aliasing problem,

It's not.

Aliasing is what happens when you reduce the _number_ of spatially
structured values, rather than same number's scale or precision.

You project a perfect representation of floating point geometry
onto an integer "matrix" and have to approximate coloring of the
fringe pixels based on how much of their area is covered, with
a blend of the color in use, its alpha channel if any, and the
background color you're overwriting.

I.e. exactly what I said: a reduction of the number of values, in this
case from infinitely many to a finite set.

But _nothing_ like that was even remotely hinted at in your actual
problem statement: no geometry, no floating-point data, nothing.  Just
three integer numbers with no apparent relation to each other.  So
there's no chance to get aliasing, and thus no way apply anti-aliasing.

But the point is, you take floating point values and project
them to integer boundaries.  In the case of anti-aliasing, you
use that fractional portion to determine rounding up/down.

The difference is whether your input data is just a shapeless set of
numbers, or a function of the coordinates in some geometric space: a
"field" Aliasing is an artefact that happens when you sub-sample the geometric _coordinates_ of the field, quantization is what you reduce
the precision of the field's _values_.

I apologize for not explaining the problem well enough. I don't
know what you need to answer my question properly, and I'm not
sure I'm conveying it in a way you can receive properly to then

The problem (to me) is simple. I have three values (v1, v2, v3),
and they contain numbers. The goal is to get v1+v2+v3 up to the
next even multiple of 8 boundary, and to do so proportionally so
the biggest one gets the biggest increase, the next biggest the
next biggest increase, the smallest the smallest increase.

I was told by someone in comp.lang.c that this does have some
resemblance to a graphics algorithm. Scott writes:

"> As Anton mentioned, that does sound a lot like the
"> linear interpolation we use in graphics, or any quanti-
"> zation problem really."

I do not know graphics algorithms as by learning them. I have
written several graphics algorithms, but it's all been thinking
the problem through.

To my thinking, this problem seemed like one related to the way
anti-aliasing is handled when projecting true geometry to integer
boundaries.

I apologize if I do not use the correct terminology. I am not
schooled in these areas. I can only describe their function,
not their official names.

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Rick C. Hodgin@21:1/5 to Scott Hemphill on Sun Sep 16 07:43:58 2018
On 09/14/2018 09:47 AM, Scott Hemphill wrote:
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:
I have a situation where I have three values (v1, v2, v3) and they
have a max value each of 32, but more typically each will be 8 or less.

I need to scale up their values proportionally toward the next
largest multiple of 8 (if they don't already equal a multiple of 8).

For example:

v1 = 2
v2 = 3
v3 = 4

Here we have a total of 2+3+4 = 9, which would need to scale up to
16, being as it's the next multiple of 8.

I need the v1, v2, and v3 values to each scale up proportionally,
so that v3 gets the largest increase, v2 the second largest, and
v1 the smallest.

Mathematically I can determine how much they would scale with an
equation. But v1..v3 are integers, and they need to round to the
nearest integer values to be legitimate, which may require rounding
up in some cases, rounding down in others.

-----
I was thinking this problem seems like an anti-aliasing problem,
where perfect geometry is mapped into integer space, rounding up
to the next pixel, or down to the prior one.

I was wondering if anyone can think of an anti-aliasing algorithm
which would help in this case?

This problem isn't completely specified, because sometimes there is
more than one way to choose which to round up and which to round down.
The case you gave (v1,v2,v3) = (2,3,4) is pretty easy, but how would you
want to round (v1,v2,v3) = (5,8,11) ?

I don't see (2,3,4) as being easy. v1=2, v2=3, v3=4, total
of 9, rounding up to 16, means 7 can be added. How do you
distribute 7 amongst the 2,3,4 proportionally?

So long as the increase is proportional, it doesn't matter
too much which one receive the rounding up more.

One way to handle this problem does have some resemblence to
antialiasing. You could use "error diffusion". In your case, you would compute (v1,v2,v3) = 16/9 * (2,3,4) = (3.55,5.33,7.11). (I am truncating
the decimals. They repeat, of course.) Then round v1 up to 4. The
error is -0.44. Add that to v2, computing v2 = 5.33-0.44 = 4.88. When
you round v2 up to 5, the error is -0.11. Then compute v3 = 7.11-0.11 =
7. The resulting triple is (v1,v2,v3) = (4,5,7).

This is what I would expect the values to be rounded up to.

I had not considered factoring in the previous error in the
next value. Are you applying it by size? Or just left-to-
right in this example?

Thank you for your assistance. And for reference, these
integers refer to how many bits are used to encode some-
thing. A value of 2 means 2^2, meaning there are 00, 01,
10, 11 values for that position. A value of 4 means there
are 2^4, with 0000..1111, meaning 15 values, etc. And
these values are being used for storage space in a compact
structure, and by increasing the bits, we allow for the
values of 00..11 (4 values) to be increased to 7 values
by increasing it from 2 to 3 (meaning 2 bits of storage
to 3 bits of storage).

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From =?UTF-8?Q?Hans-Bernhard_Br=c3=b6ker@21:1/5 to That doesn't mean what the followin on Sun Sep 16 21:07:30 2018
Am 16.09.2018 um 13:36 schrieb Rick C. Hodgin:

I apologize for not explaining the problem well enough.  I don't
know what you need to answer my question properly, and I'm not
sure I'm conveying it in a way you can receive properly to then

I think that for starters, you must stop jumping to conclusions. Or if
you do, you need to be more open for the idea that such jumps might land
you in the wrong place --- at least after having been told so.

The problem (to me) is simple.  I have three values (v1, v2, v3),
and they contain numbers.

You just say "numbers", which begs the question: are these always
integer, too, or is that a requirement for your output only? I'll
assume integers throughout, for now.

The goal is to get v1+v2+v3 up to the
next even multiple of 8 boundary,

"Next" or "Next bigger"?

and to do so proportionally so

That doesn't mean what the following says:

the biggest one gets the biggest increase, the next biggest the
next biggest increase, the smallest the smallest increase.

That part cannot fully be satisfied, because there is not necessarily
"the" smallest or "the" next-biggest increase to assign. Think of cases
where the sum of the inputs, was 7 (modulo 8), so you only get to add
one in total. Same goes for the inputs, too: how would you work on three identical numbers for input?

"Proportional" would not just mean sorting, but scaling the increments
like the inputs. I.e. all outputs would be the rounded result from
multiplying each input by the target sum, then dividing it by the input sum.
I was told by someone in comp.lang.c that this does have some
resemblance to a graphics algorithm.  Scott writes:

"> As Anton mentioned, that does sound a lot like the
"> linear interpolation we use in graphics, or any quanti-
"> zation problem really."

I.e. even your source never claimed a relation to anti-aliasing, but
rather to quantization. Same as I did right away.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Rick C. Hodgin@21:1/5 to All on Sun Sep 16 15:48:05 2018
On 09/16/2018 03:07 PM, Hans-Bernhard Bröker wrote:
Am 16.09.2018 um 13:36 schrieb Rick C. Hodgin:

I apologize for not explaining the problem well enough.  I don't
know what you need to answer my question properly, and I'm not
sure I'm conveying it in a way you can receive properly to then

I think that for starters, you must stop jumping to conclusions.  Or if
you do, you need to be more open for the idea that such jumps might land
you in the wrong place --- at least after having been told so.

The problem (to me) is simple.  I have three values (v1, v2, v3),
and they contain numbers.

You just say "numbers", which begs the question: are these always
integer, too, or is that a requirement for your output only?  I'll
assume integers throughout, for now.

The goal is to get v1+v2+v3 up to the
next even multiple of 8 boundary,

"Next" or "Next bigger"?

I view them as the same, but if it's 9..15 it needs to go
to 16.

and to do so proportionally so

That doesn't mean what the following says:

the biggest one gets the biggest increase, the next biggest the
next biggest increase, the smallest the smallest increase.

That part cannot fully be satisfied, because there is not necessarily
"the" smallest or "the" next-biggest increase to assign.  Think of cases where the sum of the inputs, was 7 (modulo 8), so you only get to add
one in total. Same goes for the inputs, too: how would you work on three identical numbers for input?

You would add 1 to the biggest. If there isn't a biggest,
then pick one. However, in this particular the case the
v1..v3 values have real names and meanings, and the RN one
is the biggest, the TC is the second biggest, and the DC
is the smallest.

"Proportional" would not just mean sorting, but scaling the increments
like the inputs.  I.e. all outputs would be the rounded result from multiplying each input by the target sum, then dividing it by the input
sum.

My use of the word proportional means if the values are 2,
3, 4, then 4 would get the largest increase, 3 the middle,
and 2 the smallest.

I was told by someone in comp.lang.c that this does have some
resemblance to a graphics algorithm.  Scott writes:

"> As Anton mentioned, that does sound a lot like the
"> linear interpolation we use in graphics, or any quanti-
"> zation problem really."

I.e. even your source never claimed a relation to anti-aliasing, but
rather to quantization.  Same as I did right away.

Again, and for the final time, I apologize for using the
incorrect wording. I lump things this into the same
general category, and to me it seemed like an issue of
projecting real geometry onto integer boundaries.

I appreciate you correct my every mistake. Is the prob-
lem I have given not clear enough to help me out? If not,
that's fine. Thank you for attempting to help me.

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Rick C. Hodgin@21:1/5 to All on Tue Sep 18 10:17:57 2018
On 9/16/2018 3:07 PM, Hans-Bernhard Bröker wrote:
Am 16.09.2018 um 13:36 schrieb Rick C. Hodgin:
the biggest one gets the biggest increase, the next biggest the
next biggest increase, the smallest the smallest increase.

That part cannot fully be satisfied, because there is not necessarily "the" smallest or "the" next-biggest increase to assign.  Think of cases where the sum of the inputs, was 7 (modulo 8), so you only get to add one in total. Same goes for the inputs, too: how would you work on three identical numbers for input?

The solution I have uses floating point math. It computes the
steps of each:

v1s = v1 / (v1+v2+v3);
v2s = v2 / (v1+v2+v3);
v3s = v3 / (v1+v2+v3);

Those steps give the percentage of increase for each value,
and total 1.0 (sans rounding).

A loop is entered applying the values and checking their int-
rounded values after each, and when the target value is met
or exceeded, it exits out and begins a reduction algorithm
to reduce any overflows due to rounding.

It brings down the smallest value first, then the next, then
he biggest last.

It works. It's the logic I see to make this algorithm work.

"Proportional" would not just mean sorting, but scaling the increments like the inputs.  I.e. all outputs would be the rounded result from multiplying each input by the target sum, then dividing it by the input sum.

Correct. What I was hoping for was a way to accomplish the same
thing in a direct algorithm without iteration or the post-round-
down stage, an artifact of rounding.

I saw this as a similar type of math problem to the way anti-
aliasing algorithms have to deal with their overflows to update
an aliased pixel's color with fractional color data.

I was told by someone in comp.lang.c that this does have some
resemblance to a graphics algorithm.  Scott writes:

"> As Anton mentioned, that does sound a lot like the
"> linear interpolation we use in graphics, or any quanti-
"> zation problem really."

I.e. even your source never claimed a relation to anti-aliasing, but rather to quantization.  Same as I did right away.

I may have used the wrong term by applying it to anti-aliasing, but
are you truly prepared to completely discount the nature of the math
problem based on my nomenclature mistake?

To me that seems not only petty, but a flatly wrong thing to do. I
would even argue it's a type of bullying: "You need to do it /MY/
being that way when legitimate solutions are sought, and a willing-
ness to learn and grow by the person asking the question exists.

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Scott Hemphill@21:1/5 to Rick C. Hodgin on Tue Sep 18 17:14:02 2018
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:

[snip]

I don't see (2,3,4) as being easy. v1=2, v2=3, v3=4, total
of 9, rounding up to 16, means 7 can be added. How do you
distribute 7 amongst the 2,3,4 proportionally?

I view it as being easy, since rounding each of (3.55,5.33,7.11) to the
nearest integer produces a sum of 16, which is what was desired.

So long as the increase is proportional, it doesn't matter
too much which one receive the rounding up more.

One way to handle this problem does have some resemblence to
antialiasing. You could use "error diffusion". In your case, you would
compute (v1,v2,v3) = 16/9 * (2,3,4) = (3.55,5.33,7.11). (I am truncating
the decimals. They repeat, of course.) Then round v1 up to 4. The
error is -0.44. Add that to v2, computing v2 = 5.33-0.44 = 4.88. When
you round v2 up to 5, the error is -0.11. Then compute v3 = 7.11-0.11 =
7. The resulting triple is (v1,v2,v3) = (4,5,7).

This is what I would expect the values to be rounded up to.

I had not considered factoring in the previous error in the
next value. Are you applying it by size? Or just left-to-
right in this example?

I was just going left-to-right, but you can apply it in any order you
wish. (1,1,3) gets converted to (2,1,5), but (1,3,1) gets converted to (2,4,2). If you care about this difference, then you need to be very

Thank you for your assistance. And for reference, these
integers refer to how many bits are used to encode some-
thing. A value of 2 means 2^2, meaning there are 00, 01,
10, 11 values for that position. A value of 4 means there
are 2^4, with 0000..1111, meaning 15 values, etc. And
these values are being used for storage space in a compact
structure, and by increasing the bits, we allow for the
values of 00..11 (4 values) to be increased to 7 values
by increasing it from 2 to 3 (meaning 2 bits of storage
to 3 bits of storage).

--
Scott Hemphill hemphill@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Rick C. Hodgin@21:1/5 to Scott Hemphill on Tue Sep 18 17:53:56 2018
On 9/18/2018 5:14 PM, Scott Hemphill wrote:
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:
I don't see (2,3,4) as being easy. v1=2, v2=3, v3=4, total
of 9, rounding up to 16, means 7 can be added. How do you
distribute 7 amongst the 2,3,4 proportionally?

I view it as being easy, since rounding each of (3.55,5.33,7.11) to the nearest integer produces a sum of 16, which is what was desired.

Let's consider the possible range of values (we'll call them a,
b, and c instead of v1, v2, and v3).

If we consider a, b, c, all in the range from 1..32, we have a
4096 match exactly at the 8-bit boundary, and 28,672 need some
adjustment because their (a + b + c) % 8 does not equal 0.

If we apply projected increases and round, we find that of those
28,672 only 19,895 fall on an exact boundary using the project-
and-round logic, leaving 8,777 need post-project-and-round ad-
justment.

Here's the pseudo-code (written in Visual FoxPro, "ln" prefixes
mean "local numeric" and are just a convention):

lnMatch = 0 && Number that match exactly
lnMismatchType1 = 0 && Number that project exactly
lnMismatchType2 = 0 && Number that miss the projection

FOR lnA = 1 TO 32 && a = 1..32
FOR lnB = 1 TO 32 && b = 1..32
FOR lnC = 1 TO 32 && c = 1..32

* See where we are
lnABC = (lnA + lnB + lnC)

* Same as ((lnABC % 8) ? 0 : 8 - (lnABC % 8)) in C/C++:
lnTarget = lnABC + IIF(lnABC % 8 = 0, 0, 8 - (lnABC % 8))
lnDiff = lnTarget - lnABC

* Are we there?
IF lnDiff = 0
* Yes, it's on a boundary of 8
lnMatch = lnMatch + 1

ELSE
* Need to adjust up to next highest boundary of 8
lnAStep = lnA / lnABC
lnBStep = lnB / lnABC
lnCStep = lnC / lnABC

lnA2 = lnA + ROUND(lnDiff * lnAStep, 0) && Round to
lnB2 = lnB + ROUND(lnDiff * lnBStep, 0) && nearest
lnC2 = lnC + ROUND(lnDiff * lnCStep, 0) && whole number

* Compute our new total
lnABC2 = lnA2 + lnB2 + lnC2
lnDiff2 = lnTarget - lnABC2

IF lnDiff2 = 0
lnMismatchType1 = lnMismatchType1 + 1
ELSE
lnMismatchType2 = lnMismatchType2 + 1
ENDIF

ENDIF

NEXT
NEXT
NEXT

* Display the totals
? lnMatch, lnMismatchType1, lnMismatchType2

If I missed something, I'm open to correcting it.

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Scott Hemphill@21:1/5 to Rick C. Hodgin on Tue Sep 18 20:53:47 2018
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:

On 9/18/2018 5:14 PM, Scott Hemphill wrote:
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:
I don't see (2,3,4) as being easy. v1=2, v2=3, v3=4, total
of 9, rounding up to 16, means 7 can be added. How do you
distribute 7 amongst the 2,3,4 proportionally?

I view it as being easy, since rounding each of (3.55,5.33,7.11) to the
nearest integer produces a sum of 16, which is what was desired.

Let's consider the possible range of values (we'll call them a,
b, and c instead of v1, v2, and v3).

If we consider a, b, c, all in the range from 1..32, we have a
4096 match exactly at the 8-bit boundary, and 28,672 need some
adjustment because their (a + b + c) % 8 does not equal 0.

If we apply projected increases and round, we find that of those
28,672 only 19,895 fall on an exact boundary using the project-
and-round logic, leaving 8,777 need post-project-and-round ad-
justment.

Here's the pseudo-code (written in Visual FoxPro, "ln" prefixes
mean "local numeric" and are just a convention):

lnMatch = 0 && Number that match exactly
lnMismatchType1 = 0 && Number that project exactly
lnMismatchType2 = 0 && Number that miss the projection

FOR lnA = 1 TO 32 && a = 1..32
FOR lnB = 1 TO 32 && b = 1..32
FOR lnC = 1 TO 32 && c = 1..32

* See where we are
lnABC = (lnA + lnB + lnC)

* Same as ((lnABC % 8) ? 0 : 8 - (lnABC % 8)) in C/C++:
lnTarget = lnABC + IIF(lnABC % 8 = 0, 0, 8 - (lnABC % 8))
lnDiff = lnTarget - lnABC

* Are we there?
IF lnDiff = 0
* Yes, it's on a boundary of 8
lnMatch = lnMatch + 1

ELSE
* Need to adjust up to next highest boundary of 8
lnAStep = lnA / lnABC
lnBStep = lnB / lnABC
lnCStep = lnC / lnABC

lnA2 = lnA + ROUND(lnDiff * lnAStep, 0) && Round to
lnB2 = lnB + ROUND(lnDiff * lnBStep, 0) && nearest
lnC2 = lnC + ROUND(lnDiff * lnCStep, 0) && whole number

* Compute our new total
lnABC2 = lnA2 + lnB2 + lnC2
lnDiff2 = lnTarget - lnABC2

IF lnDiff2 = 0
lnMismatchType1 = lnMismatchType1 + 1
ELSE
lnMismatchType2 = lnMismatchType2 + 1
ENDIF

ENDIF

NEXT
NEXT
NEXT

* Display the totals
? lnMatch, lnMismatchType1, lnMismatchType2

If I missed something, I'm open to correcting it.

That looks right. First, a side comment. You're making the arithmetic slightly more complicated than it needs to be. You don't have to
calculate the difference between the target and the total and the value
of the individual steps. You can simply calculate:

lnA2 = ROUND(lnA * lnTarget/lnABC),

etc.

Now let's see what we can learn about the 8777 hard triples. If you
look at the number you (and I) are rounding, it consists of an integer
part and a fractional part. So I will call the fractional parts fA, fB,
and fC. Each fraction lies on the interval [0,1), i.e. it can be zero,
but it can't be one. Also, the total of fA, fB, and FC is an integer,
so it has to be either zero, one, or two. It can only be zero if all
three fractions are zero, so this already rounds exactly, and can't be a
hard triple. If two of the fractions are zero, then the third fraction
must also be zero in order for their sum to be an integer, so we can
never have just two fractions which are zero. If there is just one
fraction that is zero, then the sum of two other fractions must be one.
We can reorder the fractions if necessary and we have:

fA = 0
0 < fB < 1/2
1/2 < fC < 1

fB and fC can't be exactly one-half, since they were arrived at by
dividing a number which is a multiple of 8 by a number which is not a
multiple of 8. There are more factors of two in the numerator than in
the denominator, so after cancellation, there can't be any twos in the denominator. The sum of fB and fC is more than 1/2 and less than 3/2,
so it has to be one. After rounding fB down to zero and rounding fC up
to one, the total is still one. Therefore, rounding produces the
correct total, and this is not one of our hard triples

In summary, none of our hard triples involve rounding a number which has a fractional part of zero.

So we have the following cases left:

1) All three fractions are less than one-half
2) Two fractions are less than one-half, one is more than one-half
3) Two fractions are more than one-half, one is less than one-half
4) All three fractions are more than one-half

Case 1)

If all three fractions are less than one-half, then their sum lies
between zero and 3/2. Therefore their sum must be one, but they all
round down to zero. This is one of our hard triples.

Case 4)

If all three fractions are more than one-half, then their sum lies
between 3/2 and three, so it must be two. The fractions all round up to
one, totalling three instead of two. This is one of our hard triples.

Case 2)

The sum of the three fractions must lie between one-half and two, so it
must be one. After two fractions are rounded down to zero, and one
rounded up to one, the sum is still one. This is not a hard triple.

Case 3)

The sum of the three fractions must lie between one and 5/2, so it must
be two. After two fractions are rounded up to one, and one rounded down
to zero, the sum is still two. This is not a hard triple.

So there you have it. You will have to decide what to do with three
fractions that all lie between 0 and one-half, or three fractions that
all lie between one-half and one.

For example, fA=0.3, fB=0.3, fC=0.4. Their total is one. Do you
promote fC to one because it's the biggest of the fractions? What if
lnA is a lot bigger than lnB or lnC? It might be that rounding fA to
one might be a smaller proportional error than rounding fC to one.

Similarly with, fA=0.6, fB=0.7, fC=0.7. Their total is two, but you
can't round them all up, because their total would then be three. So
which one do you demote: fA? Does it depend on the relative size of
lnA, lnB, and lnC? Here's another consideration: suppose lnB and lnC
have the same value. Do you want to preserve that equality even though
it might mean a greater relative error by demoting fA?

Scott
--
Scott Hemphill hemphill@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Rick C. Hodgin@21:1/5 to Scott Hemphill on Tue Sep 18 22:26:20 2018
On 9/18/2018 8:53 PM, Scott Hemphill wrote:
That looks right. First, a side comment. You're making the arithmetic slightly more complicated than it needs to be. You don't have to
calculate the difference between the target and the total and the value
of the individual steps. You can simply calculate:

lnA2 = ROUND(lnA * lnTarget/lnABC),

etc.

I did that so I could observe the values in the debugger
while single-stepping.

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Rick C. Hodgin@21:1/5 to Scott Hemphill on Wed Sep 19 08:12:30 2018
On 9/18/2018 8:53 PM, Scott Hemphill wrote:
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:
So there you have it. You will have to decide what to do with three fractions that all lie between 0 and one-half, or three fractions that
all lie between one-half and one.

For example, fA=0.3, fB=0.3, fC=0.4. Their total is one. Do you
promote fC to one because it's the biggest of the fractions? What if
lnA is a lot bigger than lnB or lnC? It might be that rounding fA to
one might be a smaller proportional error than rounding fC to one.

Similarly with, fA=0.6, fB=0.7, fC=0.7. Their total is two, but you
can't round them all up, because their total would then be three. So
which one do you demote: fA? Does it depend on the relative size of
lnA, lnB, and lnC? Here's another consideration: suppose lnB and lnC
have the same value. Do you want to preserve that equality even though
it might mean a greater relative error by demoting fA?

I modified the code I have to count the number of digits the ones
that missed the target are off by. It resulted in:

missed by -1 = 5703
missed by +1 = 3074

So, now I need to analyze what the ones that missed by -1 have in
common, and what the ones that missed by +1 have in common, and
then I can possibly enter a branch /BEFORE/ I do the calculation

If I can figure out that pattern, I'll have a single algorithm
with no iteration that can handle all cases.

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)