As mentioned earlier, for the sake of simplicity, we’ll just deal with integers when talking
about fixed point numbers.
We’ve already looked at addition in the previous section, and it's simple right, we
take two binary numbers, and do a bit wise addition.
If both bits are 1, we carry the excess over to the next bit position.
Simple.
Fixed point subtraction is the same as addition, there's no difference in the operation.
If we are subtracting 7 from 10 for example, we first convert 7 into its 2’s complement
form, that's the same as taking the negative of the number, once we do that, the bitwise
operation is the same as addition.
Multiplication of fixed point numbers is essentially the long form multiplication method that we’ve
been taught at school for decimal numbers.
For instance, take 2 numbers 10 and 5.
This is their binary equivalent.
Perform a multiplication step for each digit of the multiplier, and sum up all the properly
shifted results.
The bitwise multiplication step itself is a logical AND operation.
The result is 1, only when both the multiplier and the multiplicand are 1, and it’s zero
the rest of the time.
There’s a few observations that we can make here.
The number of add operations required to multiply 2 n-bit numbers is 2n.
And then there is the logical AND operations required to generate the partial sums in the
first place.
The individual operations may be trivial but the time complexity for the multiplication
operation to finish is O(n2).
Obviously, modern processors are optimized to multiply fast.
For example, modern processors can multiply two 64-bit numbers with 6 additions (rather
than 64), and can do several steps in parallel.
Another important note here is that the product requires more number of bits to be represented
when compared to either the multiplier or the multiplicand.
Look at our example here, we have 10, which is a 4 bit number, and 5, which is technically
a 3 bit number.
The resultant product of the 2 numbers, which is 50 is a 6 bit number.
In general, we can say that a multiplication between an m-bit number and an n-bit number
results in a number which has at most m+n bits.
Now this is a problem with fixed point numbers.
Overflow is always a possibility when multiplying 2 fixed point numbers when representing the
product within the same sized container as the multiplier.
For fractional numbers, there could be loss of precision, and for integer numbers there
could be a loss of a significant digit.
Dealing with overflow during multiplication is also really expensive.
A common way to avoid overflow in intermediary steps of multiplication operation is to have
an extended width register, when summing the partial products.
If the width of the register computing the partial sums of a multiplication between 2
32 bit numbers is 64bits, overflow would never happen within these intermediary steps.
This avoids potential loss of precision at every step.
Ofcourse in the end, the value from the extended width register has to be pushed into the normal
sized registers, and this is where the overflow would essentially happen, there is no avoiding
that.
Alright, so multiplication involves a fair few steps.
But there are certain values of multiplier for which the multiplication operation can
be highly optimized.
This is when the multiplier is a power of 2.
We’ll see why when we explore a couple of new operators.
The binary bit shift left, and binary bit shift right operators.
The idea behind them is quite simple.
Take the bit shift left operator.
It’s essentially shifting all of the bits by 1 position to the left.
When you do that, the position index 0 is no longer occupied by any bit, so it’s initialized
to zero.
And the last position index on the left, is pushed out of the container, and so, an overflow
happens and any value that bit previously had is now discarded.
Alright, but how does this actually change the value of the binary number.
Take a simple example of the decimal number 50 in binary.
If you perform the shift left operation once, you end up with this state.
The decimal equivalent of this number is 100.
Let’s perform the shift again, and we get this number.
This is the decimal equivalent of 200.
So what’s happening here?
Every time you bit shift left by 1, we end up with the value times 2.
If you bit shift twice, you end up with the value times 4.
More simply, it’s a power of 2 operation.
Bit shift left 5 times, and you end up with value time 2^5.
As you can imagine, the bit shift right operation behaves pretty much the opposite.
If you shift the bits to the right, the bit that replaces the MSB on the left is initialized
to zero.
And the bit that was present at the LSB on the right, is shifted off, and is discarded.
An overflow would never happen with bit shift right operations, but it could result in the
loss of accuracy.
Take the same example as before.
The number 50.
Bit shift right once, will result in this state, which is the decimal equivalent of
25.
So it’s essentially a division by 2 operator.
Do it again, and the state is this.
Logically, the value should’ve been 12.5, since you’re dividing 25 by 2.
But as you can see, the LSB which contained 1 in the previous step is discarded, which
essentially resulted in a loss of accuracy.
Because of this, the resultant number is the decimal equivalent of 12.
So clearly the operation resulted in an imprecise number.
This is one of the big problems with fixed point arithmetic.
Especially with division operation, when the result cannot be represented accurately within
the fixed number of bits that the number format can represent.
We either have to truncate the result, where the fractional part is completely discarded,
and only the integer is retained.
Or the result can be rounded, where an additional check is required to round the number to the
nearest integer value.
Since the range is linear, the loss of precision is much greater on smaller numbers when division
and multiplication operations are involved.
We’ll discuss this later.
So clearly bit shifting is the way to go when we want to multiply and divide numbers by
powers of two right?
So should we rethink our approach and handle different numbers differently when writing
code, and go back and refactor all of our existing code?
No.
Compiled languages like C++ go through an intense list of possible optimizations and
it will do this for you!
Let’s check this out.
We’ll go to a webpage called godbolt.org, which is a popular compiler explorer, a tool
for determining the assembly instructions a compiler would output.
Every compiler is built differently, they all have their own optimizations built in,
and for the purposes of this demo, I’m gonna select the clang compiler, and I’m gonna
write some code.
I’m just going to declare an unsigned integer, assign to 10, and multiply it by 32.
These are the assembly instructions generated by the compiler, and assembly instructions
are essentially the lowest level programmable instructions to a computer.
An assembler would then convert these instructions into machine code or byte code, and this would
just be pure binary data.
Anyway, in the list of instructions is this: shl or shift left, and it’s for 5 times.
We didn’t explicitly write a shift left operation, the compiler optimization handled
it for us.
Divide it by 4, let’s say, and we get the shift right operation this time.
If you multiply by any other non power of 2 number, like 15, the compiler resorts to
the unoptimized multiplication operation.
Because of the binary number system and how numbers are organized in storage units, there
is quite often an advantage of using power of 2 numbers.
Especially in multi dimensional arrays, and size of audio buffers, and for reasons slightly
different, in FFT buffers where the Fast Fourier Transforms algorithms generally always prefer
a power of 2 sized buffer for computational efficiency.
But there can be unintended consequences while using power of 2 sized data structures.
A cache miss could cause significant performance hits to a running application, if the data
structure cannot be fully held within a CPU cache, which is also a power of 2 structure.
If the caching cannot be done, the program would have to fetch the data from a higher
level cache or from memory, which can be slow.
It’s beyond the scope of this video, but I’ve linked a couple of articles below which
talk about cache misses.
As a general guideline, if you’re an application developer, don’t worry about optimising
code.
Worry instead about writing clean and maintainable code.
Only ever think about optimising when you notice a need for one.
And never assume that a preferred optimisation strategy would work for your code.
Compilers and the hardware underneath have subtle ways of not working the way you want
them to.
Always test and profile your code to find out how long it takes, and to see if you’ve
got a performance advantage from one method over the other.