Using Multiply High For Intermediate Values
Duane Degn
Posts: 10,588
I know the "**" operator returns the upper 32-bits of a 64-bit multiplication result but I don't know how to make use of this value to increase the precision of the final answer to an equation using large numbers.
For example, let's say I want to find the value of:
(25,123 * 2,001,234) / 50,000
Punching this in on a calculator gives me the result of 1,005,540 which easily fits in a 32-bit long.
One problem with performing this calculation in the Propeller is 25,123 * 2,001,234 = 50,277,001,782 which is greater than a 32-bit long can hold.
To test the "**" operator I used this program.
This is the output.
My question is how to make use of these values to compute this equation?
(25,123 * 2,001,234) / 50,000
or using the variables in the test program what's the equivalent code to:
When x * y can be larger than 32-bits but "result" will fit in a 32-bit long?
I think I have an idea of how this could be done with complicated bit shifting but all the techniques I can think of seem very messy and complex. I'm hoping there's a relatively easy solution I'm not aware of.
For example, let's say I want to find the value of:
(25,123 * 2,001,234) / 50,000
Punching this in on a calculator gives me the result of 1,005,540 which easily fits in a 32-bit long.
One problem with performing this calculation in the Propeller is 25,123 * 2,001,234 = 50,277,001,782 which is greater than a 32-bit long can hold.
To test the "**" operator I used this program.
CON
_clkmode = xtal1 + pll16x
_xinfreq = 5_000_000
BAUD = 115_200
CR = 13
VAR
long high, low
OBJ
Pst : "Parallax Serial Terminal"
PUB Main | x, y, z
Pst.Start(BAUD)
repeat
Pst.str(string(13, "Press any key to begin."))
result := Pst.RxCount
waitcnt(clkfreq / 4 + cnt)
until result
Pst.RxFlush
Pst.Clear
Pst.Home
x := 25_123
y := 2_001_234
z := 50_000 ' z isn't used yet
Pst.Char(CR)
Pst.Char(CR)
Pst.Dec(x)
Pst.str(string(" * "))
Pst.Dec(y)
Pst.str(string(" = "))
low := x * y
Pst.Dec(low)
Pst.Char(CR)
Pst.Dec(x)
Pst.str(string(" ** "))
Pst.Dec(y)
Pst.str(string(" = "))
high := x ** y
Pst.Dec(high)
repeat
This is the output.
25123 * 2001234 = -1262605770 25123 ** 2001234 = 11
My question is how to make use of these values to compute this equation?
(25,123 * 2,001,234) / 50,000
or using the variables in the test program what's the equivalent code to:
result := (x * y) / z
When x * y can be larger than 32-bits but "result" will fit in a 32-bit long?
I think I have an idea of how this could be done with complicated bit shifting but all the techniques I can think of seem very messy and complex. I'm hoping there's a relatively easy solution I'm not aware of.
Comments
-Phil
Beautiful!
Thank you very much Phil.
Pst.Char(CR) Pst.Char("(") Pst.Dec(x) Pst.str(string(" * ")) Pst.Dec(y) Pst.str(string(") / ")) Pst.Dec(z) Pst.str(string(" = ")) result := Math.div(high, low, z) Pst.Dec(result) Pst.str(string(" or ")) result := Math.multdiv(x, y, z) Pst.Dec(result)I wanted to try both the "div" method and the "multdiv" method. They of course both work.
Here's the new output.
I see the "div" method does take some serious bit shifting to come up with the answer (very cool BTW).
Thank you again Phil!
My method is this one formula, PUB BinNormal(.,.,.,) is this fast binary division loop, which renormalizes a proper fraction y/x into a fraction with implied binary denominator, y/x = f/(2*b):
[SIZE=1][FONT=courier new]PUB BinNormal (y, x, b) : f ' calculate f = y/x * 2^b ' b is number of bits ' enter with y,x: {x > y, x < 2^31, y <= 2^31} ' exit with f: f/(2^b) =< y/x =< (f+1) / (2^b) ' closest b-bit approximation to the original fraction repeat b y <<= 1 f <<= 1 if y => x ' y -= x f++ if y << 1 => x ' Round off. In some cases better without. f++[/FONT][/SIZE]Please let me know if you find discrepancies, incorrect answers, roundoff errors. My method sits on slightly shaky ground, so caveat, it might fail in boundary cases.
The method there is using Multiply High in its other role as Fractional Multiply. Any number N3 := N1 ** N2 can be thought of as the normal product of N1 and N2 divided by 2^32. In that interpretation, Fractional Multiply is the workhorse of fixed point math on the Prop.
Sometimes either N1 or N2 is a constant fraction. The multiplier to use with ** can be computed in advance. Say, N2=0.25123 is a constant calibration factor. Figure it in advance,
F = 0.25123 * 2^32 = 1079024634.
Then
result := N1 ** F.
If the constant is N2 = 2.5123 with an integer part, then,
F=0.5123 * (2^32) / 2 = 1100155873
Note the division by the factor of 2. Because N2 is greater than 1/2, the fraction would come out greater than 2^31, which the Prop would interpret as a negative number and throw things off. The next formula has account for that extra factor of two by multiplying it back in at some point...
result := (N1 * 2) + (N1 * 2 ** F)
Integer part (first factor of 2) plus fractional part (factor of 2 to compensate for F being half what it should be) The result has to come in less than 2*31 for this to work correctly.
The BinNormal method in post #5 is a way to calculate the factor F at run time. It is a method I have in most of my templates. It has other uses, for example, to calculate the value of a counter frqx given a desired frequency in Hz.
I think your technique is closer to the approach I had vaguely formulated in my mind.
My present application doesn't require a lot of speed (measuring flow using one of your objects) but I also have some personal projects determining speed with quadrature encoders. I was running into trouble with large numbers when dealing clock ticks to calculate speed (probably similar to your frequency application). Since I'm hoping to use these speed measurements in a PID loop, computation speed will be more of an issue than it is with the flow measuring application.
I'm sure I'll be comparing yours and Phil's techniques as I attempt to find a fast way to monitor speed in Spin.
I don't fully understand what you wrote in the last two posts but I think I will be able to understand it with a bit of study. Thanks for taking time to explain your technique.