Jeremy Leach
Senior Member
On RexLan's topic I've explained a way to calculate Word1 * Word2 / Word3 avoiding overflow. As it's a general method I thought I'd put it into it's own topic so someone might be able to find it in the future ! It's pretty heavy stuff, but if it solves an overflow problem then it's worth doing...
<code><pre><font size=2 face='Courier'>
MSW = Word1 ** Word2
LSW = Word1 * Word2
ResultWord = LSW/Word3
ResultWord = -1 // Word3 /X * MSW / Word3 * X + ResultWord
ResultWord = -1/Word3 * MSW + ResultWord
ResultWord = MSW/Word3 + ResultWord
</font></pre></code>
The explanation of this code is:
MSW and LSW are the most and least significant words that result from the multiplication of Word1 * Word2. So Word1 * Word2 = (65536 * MSW) + LSW
So the division is :
[(65536 * MSW) + LSW]/Word3
=[((655535 + 1) * MSW) + LSW]/Word3
=[(655535 * MSW) + MSW + LSW]/Word3
=(LSW/Word3) + [(655535 * MSW)/Word3] + (MSW/Word3)
<b>=(LSW/Word3) + [(-1/Word3)*MSW] + (MSW/Word3) </b>
Note that -1 means the same as 65535 in word maths but takes up less program space.
The [(-1/Word3)*MSW] term can result in loss of accuracy, and so can be broken down further to :
(-1/Word3) * MSW = (WholePart * MSW) + [(RemainderPart/Word3) * MSW]
In PICAXE code the WholePart of the division is -1/Word3 and the
RemainderPart of the division is -1//Word3.
So the whole expression for Word1 * Word2 / Word3 now becomes:
<b>=(LSW/Word3) + [(-1/Word3) * MSW] + [(-1//Word3) * MSW / Word3] + (MSW/Word3) </b>
But we've also got to watch for overflow within each term:
(LSW/Word3) won't cause overflow so is ok.
[(-1/Word3) * MSW] can cause overflow. So this limits the minimum value Word3 can take without overflow.
[(-1//Word3) * MSW / Word3] can cause overflow too and limits the maximum value Word3 can take. A way to counteract this one is to add another constant X ...[(-1//Word3) /X * MSW / Word3 * X]. This reduces the accuracy of the calculation but is a simple way of preventing the overflow. Giving the final expressionj as ...
<b>=(LSW/Word3) + [(-1/Word3) * MSW] + [(-1//Word3) /X * MSW / Word3 * X] + (MSW/Word3) </b>
Which is what the code at the start represents !
The value of X has to be carefully chosen so that [the maximum of (-1//Word3)] /X * MSW doesn't cause overflow. Best to make X as small as possible though.
Edited by - jeremy leach on 08/09/2006 09:22:19
<code><pre><font size=2 face='Courier'>
MSW = Word1 ** Word2
LSW = Word1 * Word2
ResultWord = LSW/Word3
ResultWord = -1 // Word3 /X * MSW / Word3 * X + ResultWord
ResultWord = -1/Word3 * MSW + ResultWord
ResultWord = MSW/Word3 + ResultWord
</font></pre></code>
The explanation of this code is:
MSW and LSW are the most and least significant words that result from the multiplication of Word1 * Word2. So Word1 * Word2 = (65536 * MSW) + LSW
So the division is :
[(65536 * MSW) + LSW]/Word3
=[((655535 + 1) * MSW) + LSW]/Word3
=[(655535 * MSW) + MSW + LSW]/Word3
=(LSW/Word3) + [(655535 * MSW)/Word3] + (MSW/Word3)
<b>=(LSW/Word3) + [(-1/Word3)*MSW] + (MSW/Word3) </b>
Note that -1 means the same as 65535 in word maths but takes up less program space.
The [(-1/Word3)*MSW] term can result in loss of accuracy, and so can be broken down further to :
(-1/Word3) * MSW = (WholePart * MSW) + [(RemainderPart/Word3) * MSW]
In PICAXE code the WholePart of the division is -1/Word3 and the
RemainderPart of the division is -1//Word3.
So the whole expression for Word1 * Word2 / Word3 now becomes:
<b>=(LSW/Word3) + [(-1/Word3) * MSW] + [(-1//Word3) * MSW / Word3] + (MSW/Word3) </b>
But we've also got to watch for overflow within each term:
(LSW/Word3) won't cause overflow so is ok.
[(-1/Word3) * MSW] can cause overflow. So this limits the minimum value Word3 can take without overflow.
[(-1//Word3) * MSW / Word3] can cause overflow too and limits the maximum value Word3 can take. A way to counteract this one is to add another constant X ...[(-1//Word3) /X * MSW / Word3 * X]. This reduces the accuracy of the calculation but is a simple way of preventing the overflow. Giving the final expressionj as ...
<b>=(LSW/Word3) + [(-1/Word3) * MSW] + [(-1//Word3) /X * MSW / Word3 * X] + (MSW/Word3) </b>
Which is what the code at the start represents !
The value of X has to be carefully chosen so that [the maximum of (-1//Word3)] /X * MSW doesn't cause overflow. Best to make X as small as possible though.
Edited by - jeremy leach on 08/09/2006 09:22:19