Can someone prove this? (using A+(B-A)/2 instead of (A+B)/2 to avoid overflow errors)

SMcNeill

New member
Joined
Jan 26, 2018
Messages
7
As a computer programmer, sometimes I have to deal with data-size limits when working with numbers, and I have to be careful of "OVERFLOW ERRORS" where my data is too large to process. It sounds a bit complex, but it's simple enough to understand with a few examples.

FOR EXAMPLE: I have a variable which is defined in my program as being an UNSIGNED BYTE. In computers, this is 8 bits of binary data (0s and 1s), and represents the range from 0 to 255. For those who don't understand computers at all, let's just say I have an egg-crate which can hold from 0 to 255 eggs in it...

Now, in one crate, I have 200 eggs. In the second crate, I have 150 eggs. (UNSIGNED BYTE variables, in my programs, but visualize it as egg crates, if you want.)

Now, to find the average number of eggs in the crates, we simply add the numbers together and divide by 2.

The problem with computers is that sometimes we solve things step by step. First, we add the numbers together and store them in a new crate (variable): Crate3count = Crate1count + Crate2count. Then we divide by 2: Answer = Crate3count / 2

Where the problem arises is when we try and put 350 eggs into Crate3count which only holds 255 eggs... It generates an "OVERFLOW ERROR" and causes our program to crash. We're putting more eggs into that third crate than what it was built to hold....

So, here's a solution which I discovered which works without overflowing bounds, with the problem being, I can't prove that it works 100% of the time.

Instead of (A+B)/2 to get the solution, I've found that A + (B - A)/ 2 will give the proper results, without causing overflow issues with the variables. My question is: Can someone show proof that these two statements will always be functionally equivalent?

In this case, let's plug in the information from our dataset:
(A + B) / 2
(200 + 150) / 2
350 / 2
175

OR

A + (B - A) / 2
200 + (150 - 200) / 2
200 + (-50) /2
200 + (-25)
175

This seems like a simple enough algebra problem to me, but its solution eludes me everytime I try and prove it. Can someone show me proof that (A + B) / 2 = A + (B - A) / 2?

Experience shows me that it works. My poor brain however, just can't seem to figure out WHY it works. (And if this isn't a problem for Advanced Algebra people, feel free to move it to wherever it belongs. I simply posted here because it seemed like advanced algebra to me. ;) )


Thanks for advance, and kindly don't laugh at me if this is something so simple it can be shown in two obvious steps and I'm just obliviously overlooking the solution to the proof. :D
 
1) (A+B)/2 may or may not be equivalent to A + (B-A)/2. It depends on a couple of things?
1a) How does your programming interpret the expression? Does it use algebraic logic (order of operations)? Strictly left-to-right? My primary language interprets strictly right-to-left.
1b) What happens when B < A? Can your unsigned egg carton handle negative eggs?

2) Why not just notice that \(\displaystyle \dfrac{A+B}{2} = \dfrac{A}{2}+\dfrac{B}{2}\)? Unless you have some terrible premium on CPU Cycles for integer division, this would seem the most prudent solution.

Note: The most help I can suggest to you is a recommendation to brush up on your algebra. It will serve you well.
 
Last edited by a moderator:
1) (A+B)/2 may or may not be equivalent to A + (B-A)/2. It depends on a couple of things?
1a) How does your programming interpret the expression? Does it use algebraic logic (order of operations)? Strictly left-to-right? My primary language interprets strictly right-to-left.
1b) What happens when B < A? Can your unsigned egg carton handle negative eggs?

2) Why not just notice that \(\displaystyle \dfrac{A+B}{2} = \dfrac{A}{2}+\dfrac{B}{2}\)? Unless you have some terrible premium on CPU Cycles for integer division, this would seem the most prudent solution.

Note: "Advanced Algebra"? Not laughing at all. We ARE here to help. The most help I can suggest to you is a recommendation to brush up on your algebra. It will serve you well.

1a) Algebraic Logic is in use. (Brackets, powers, multiplication/division, addition/subtraction).

1b) Honestly, we shouldn't have a case of B < A as these values should be sorted incrementally elsewhere in the program. If there is an instance where B < A, then tossing an error is a good thing and is the desired result for us.

2) The problem with \(\displaystyle \dfrac{A}{2}+\dfrac{B}{2}\) is that we're trying to work almost exclusively with integer division here. 11 \ 2 + 13 \ 2 would solve to 5 + 6 = 11. (Integer Division always rounds down in this case.) A + (B - A) \ 2 would result in 11 + (13 - 11) \2 which solves to become 12.

Integer Division ( \ sign ) operates about 3-5 times faster than Real Division ( / sign ), and when called recursively thousands of times in a routine, it can make one heck of a difference in speed and performance in certain programs. And in terms of CPU calculation time, addition/subtraction is several degrees faster than even integer division. It's all about trying to find the proper solution, as fast as possible, in this case. ;)



\(\displaystyle \dfrac{A+B}{2} = \dfrac{A}{2}+\dfrac{B}{2}\) is the Distributive Property of Division, so we know it's true by definition. The root question still stands though: Is there some way to prove that \(\displaystyle \dfrac{A + B}{2} = A + (B - A) / 2\)?
 
The root question still stands though: Is there some way to prove that \(\displaystyle \dfrac{A + B}{2} = A + (B - A) / 2\)?

Yes, you came very close to it! Start on your RHS and distribute, then recombine:

\(\displaystyle A + \dfrac{B - A}{2} = A + \dfrac{B}{2} - \dfrac{A}{2} = A - \dfrac{A}{2} + \dfrac{B}{2} = \dfrac{A}{2} + \dfrac{B}{2} = \dfrac{A + B}{2}\)

Or, if you prefer,

\(\displaystyle A + \dfrac{B - A}{2} = \dfrac{2A}{2} + \dfrac{B - A}{2} = \dfrac{2A + B - A}{2} = \dfrac{A + B}{2}\)

In fact, the idea you are using comes up all the time: the average of two numbers is the lower number, plus half their difference. It's "obvious", if you picture it on a number line.
 
Yes, you came very close to it! Start on your RHS and distribute, then recombine:

\(\displaystyle A + \dfrac{B - A}{2} = A + \dfrac{B}{2} - \dfrac{A}{2} = A - \dfrac{A}{2} + \dfrac{B}{2} = \dfrac{A}{2} + \dfrac{B}{2} = \dfrac{A + B}{2}\)

Or, if you prefer,

\(\displaystyle A + \dfrac{B - A}{2} = \dfrac{2A}{2} + \dfrac{B - A}{2} = \dfrac{2A + B - A}{2} = \dfrac{A + B}{2}\)

In fact, the idea you are using comes up all the time: the average of two numbers is the lower number, plus half their difference. It's "obvious", if you picture it on a number line.

I see it now. The solution seems rather simple when working backwards (from A + (B - A) / 2), and I've been pounding my head trying to work from the other direction ((A-B)/2) instead. Seeing your solution makes the other rather obvious to me now as well:

(A + B) / 2
A / 2 + B / 2
A - A / 2 + B / 2 ........ Takes a little logic at this point, but A - A/2 is A/2. And from here, it's just some reordering and factoring.
A + B / 2 - A / 2
A + (B - A) / 2

Experience showed me it worked -- even if my poor brain just couldn't seem to sort out the why in how it worked for me. Thanks guys. You honestly wouldn't believe how many times I've tried to sort this little trick out so I could prove it worked.

Why I never started from the other side and worked backwards, I'll never know... Just too mule-headed to run the maze from the exit to the entrance, when I've already decided to start from the other side, I guess. LOL!

Nice to know that it does always hold true. ;)
 
Since Dr. Peterson proved it, I'll ask an off-topic question. Is there some reason you need to use uint8 as your data type for this application?

I don't know what language you code in, but I know Python uses 32-bit signed ints for integers by default, and converts automatically to long ints (apparently no upper limit on number of bits) as needed.
 
I see it now. The solution seems rather simple when working backwards (from A + (B - A) / 2), and I've been pounding my head trying to work from the other direction ((A-B)/2) instead. Seeing your solution makes the other rather obvious to me now as well:

(A + B) / 2
A / 2 + B / 2
A - A / 2 + B / 2 ........ Takes a little logic at this point, but A - A/2 is A/2. And from here, it's just some reordering and factoring.
A + B / 2 - A / 2
A + (B - A) / 2

Experience showed me it worked -- even if my poor brain just couldn't seem to sort out the why in how it worked for me. Thanks guys. You honestly wouldn't believe how many times I've tried to sort this little trick out so I could prove it worked.

Why I never started from the other side and worked backwards, I'll never know... Just too mule-headed to run the maze from the exit to the entrance, when I've already decided to start from the other side, I guess. LOL!

Nice to know that it does always hold true. ;)
Working backwards is a technique that math types and programmer types BOTH use.

In programming, I want to get result A. I can do that if I start with B. I can do that if I start with C. Can I get C from Z? Mathematicians do that too. Of course , that gives a backwards proof. So you have to test whether each step works in reverse.
 
Since Dr. Peterson proved it, I'll ask an off-topic question. Is there some reason you need to use uint8 as your data type for this application?

I don't know what language you code in, but I know Python uses 32-bit signed ints for integers by default, and converts automatically to long ints (apparently no upper limit on number of bits) as needed.

The main reason I'd normally use uint8 is just to reduce resources needed for a program. uint8 variables use a single byte in memory, whereas uint32 use 4-bytes each. If we're dealing with a 256 color screen image, it simply makes more sense to store, save, and use that image as unsigned bytes, rather than 32-bit integers.

For example, let's say we're going to make a video for a 1280x720 screen monitor. (720p HD resolution)
With a single byte per pixel, that's 1280 * 720 = 921,000 bytes used for a single image. If we're playing at 24 frames per second, that's 22,118,400 bytes of raw data (uncompressed) which we need to transfer and work with every second.

Now, if we were to use 32-bit integers, each one of them would take 4 times as much memory to store, transfer, and work with. From less than 1MB to store that single image in memory, to more than 3.5MB. If we have a game which loads and uses dozens of sprite sheets, the simple change can drastically affect how much memory our game ends up using.

*****************

Python uses 32-bit integers by default, but they're hardware supported. Your OS runs either in 32 or 64 bit natively (unless you have a much older OS like DOS, Windows 3.1/98, ect.) Behind the scenes, the PC is transfering data in 32-bit (or 64-bit) chunks of information. Python's INT class uses this native hardware calculation for you, but when your values get too large for hardware to handle (from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 for signed 64-bit integers and from -2,147,483,648 to 2,147,483,647 for signed 32-bit integers), it then has to do the processing at the software level -- which is quite a bit slower. If you're writing a FPS game (First Person Shooter), you want to keep the graphic's FPS (Frames Per Second) as high as possible -- which means you want to avoid the usage of LONG types in Python as much as humanly possibly.

Normally, I tend to program in some variation of C anymore, and/or QB64 (if you remember BASIC from back in the days of DOS, you'd be at home with the QB64 environment/language, which I've had the pleasure to help develop and modernize to support old BAS programs on modern 32/64-bit machines -- http://www.qb64.net/ if you're interested), but over the years I've worked with multiple programming languages.


*****************

Another thing to keep in mind with computers is the internal hardware limitations (64-bit numbers on most modern machines). Many calculations go on inside the PC that we simply take for granted and never pay attention to. (A + B) /2 is solved in 2 steps by the computer, but we hardly even think of this as we write whatever code our programming language uses to compile into an executable for us. The problem is how the computer handles the (A + B) calculation; after it adds it, it has to store than answer somewhere in memory -- and if A is a large 64-bit value and B is a large 64-bit value, how does the PC store the answer in its native 64-bit memory??

Many times, one of two things might happen: 1) The computer tosses an OVERFLOW ERROR and the program will pop up an error message on the screen and then close afterwards, or 2) It'll convert the answer to 64-bit scientific notation, which will basically round the answer to a close power of 10 and lose precision.

The solution I've found, to prevent this type memory error, is to write a function for averages which looks like the following:

FUNCTION Average (A AS INT64, B AS INT64)
IF B < A THEN SWAP B, A
Average = A + (B - A) \ 2
END FUNCTION

Same answer for an end result, but we never have to worry about any internal step in the calculations being larger than what the user's hardware can handle and tossing an exception to our math. ;)
 
Cool, thanks for the explanation. I understand the difference between integer and floating-point arithmetic, as well as the difference between 32-bit and 64-bit architectures. I just wasn't sure of your application. But given what you described of it, it makes sense that you have to work with integer data types, and that you need to minimize their size.

I used to code in C fluently, and hence paid a lot of attention to both memory allocation and to data types. Nowadays I code mostly in Python, and as a result have become quite lax about both.
 
Top