{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.manongdao.com/data/attach/logo/logo.png', '推荐 再贱就再见 的问题《Cube root on x87 FPU using Newton-Raphson method》','https://www.manongdao.com/q-1281053.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
I am trying to write an assembly program using the 8086 processor that will find the cube root of a number. Obviously I am using floating points.
Algorithm based upon Newton-Raphson method:
root := 1.0;
repeat
oldRoot := root;
root := (2.0*root + x/(root*root)) / 3.0
until ( |root – oldRoot| < 0.001;
How do I divide (2*root + x) by (root*root)?
.586
.MODEL FLAT
.STACK 4096
.DATA
root REAL4 1.0
oldRoot REAL4 2.0
Two REAL4 2.0
inttwo DWORD 2
itThree DWORD 3
three REAL4 3.0
x DOWRD 27
.CODE
main PROC
finit ; initialize FPU
fld root ; root in ST
fmul two ; root*two
fadd x ; root*two+27
fld root ; root in ST
fimul root ; root*root
mov eax, 0 ; exit
ret
main ENDP
END
I guess I don't understand what is in the stack at what location. Does the product for line
fimul root ; root*root
go into ST(1)? EDIT No, it goes into st(0) what was in st(0) got pushed down the stack to st(1)
But I haven't figured out the answer to my question... How do I divide? Now I see I need to divide st(1) by st(0) but I don't know how. I tried this.
finit ; initialize FPU
fld root ; root in ST
fmul two ; root*two
fadd xx ; root*two+27
; the answer to root*two+x is stored in ST(0) when we load root st(0) moves to ST1 and we will use ST0 for the next operation
fld root ; root in ST previous content is now in ST1
fimul root ; root*root
fidiv st(1)
EDIT: I had the formula written wrong. This is what I am looking for.
(2.0*root) + x / (root*root)) / 3.0 That's what I need.
STEP 1) (2 * root)
STEP 2) x / (root * root)
STEP 3) ADD step one and step 2
STEP 4) divide step 3 by 3.0
root = (2.0*1.0) + 27/(1.0*1.0) / 3.0 ; (2) + 27/(1.0) / 3.0 = 11 ==> root = 11
EDIT2: NEW CODE!!
.586
.MODEL FLAT
.STACK 4096
.DATA
root REAL4 1.0
oldRoot REAL4 2.0
Two REAL4 2.0
three REAL4 3.0
xx REAL4 27.0
.CODE
main PROC
finit ; initialize FPU
fld root ; root in ST ; Pass 1 ST(0) has 1.0
repreatAgain:
;fld st(2)
fmul two ; root*two ; Pass 1 ST(0) has 2 Pass 2 ST(0) = 19.333333 st(1) = 3.0 st(2) = 29.0 st(3) = 1.0
; the answer to roor*two is stored in ST0 when we load rootSTO moves to ST1 and we will use ST0 for the next operation
fld root ; root in ST(0) previous content is now in ST(1) Pass 1 ST(0) has 1.0 ST(1) has 2.0 Pass 2 st(
fmul st(0), st(0) ; root*root ; Pass 1 st(0) has 1.0 st(1) has 2.0
fld xx ; Pass 1 st(0) has 27.0 st(1) has 1.0 st(2) has 2.0
fdiv st(0), st(1) ; x / (root*root) ; Pass 1: 27 / 1 Pass 1 st(0) has 27.0 st(1) has 2.0 st(2) has 2.0
fadd st(0), st(2) ; (2.0*root) + x / (root*root)) Pass 1 st(0) has 29.0 st(1) has 1.0 st(2) has 2.0
fld three ; Pass 1 st(0) has 3.0 st(1) has 29.0 st(2) has 1.0 st(3) has 2.0
fld st(1) ; Pass 1 st(0) has 3.0 st(1) has 29.0 st(2) = 1.0 st(3) = 2.0
fdiv st(0), st(1) ; (2.0*root) + x / (root*root)) / 3.0 Pass 1 st(1) has 9.6666666666667
jmp repreatAgain
mov eax, 0 ; exit
ret
main ENDP
END
Intel's insn reference manual documents all the instructions, including
fdivandfdivr(x/y instead of y/x). If you really need to learn mostly-obsolete x87 (fdiv) instead of SSE2 (divss), then this x87 tutorial is essential reading, esp. the early chapter that explains the register stack. Also see this x87 FP comparison Q&A. See more links in the x86 tag wiki.re: EDIT2 code dump:
You have 4
fldinstructions inside the loop, but nop-suffixed operations. Your loop will overflow the 8-register FP stack on the 3rd iteration, at which point you'll get a NaN. (specifically, the indefinite-value NaN, which printf prints as1#IND.I'd suggest designing your loop so an iteration starts with
rootinst(0), and ends with the next iteration'srootvalue inst(0). Don't load or store to/fromrootinside the loop. Usefld1to load 1.0 as your initial value outside the loop, andfstp [root]after the loop to popst(0)into memory.You picked the most inconvenient way to do tmp / 3.0
fdiv,fsub, etc. have multiple register-register forms: one wherest(0)is the destination, and one where it's the source. The form withst(0)as the source is also available with apop, so you couldIt's actually even simpler than that if you use a memory operand directly instead of loading it. Since you want
st(0) /= 3.0, you can dofdiv [three]. In that case, FP ops are just like integer ops, where you can dodiv dword ptr [integer_from_memory]to use a memory source operand.The non-commutative operations (subtract and divide) also have reverse versions (e.g.
fdivr), which can save you anfxchgor let you use a memory operand even if you'd needed 3.0/tmp instead of tmp/3.0Dividing by 3 is the same as multiplying by 1/3, and
fmulis much faster thanfdiv. From a code-simplicity point of view, multiply is commutative, so another way to implementst(0) /= 3is:Note that
1/3.0has no exact representation in binary floating point, but all integers between +/- about 2^23 do (size of mantissa of single-precision REAL4). You should only care about this if you were expecting to work with exact multiples of three.Comments on the original code:
You can hoist a division out of the loop by doing
2.0 / 3.0andx/3.0ahead of time. This is worth it if you expect the loop to run more than one iteration on average.You can duplicate the top of the stack with
fld st(0), so you don't have to keep loading from memory.fimul [root](integer mul) is a bug: Yourrootis inREAL4(32bit float) format, not integer.fidivis similarly a bug, and of course doesn't work with an x87 register as a source operand.Since you have
rootat the top of the stack, I think you can justfmul st(0)to usest(0)as both the explicit and implicit operand, resulting inst(0) = st(0) * st(0), with no change in the depth of the stack.You could also use sqrt as a better initial approximation than 1.0, or maybe
+/-1 * sqrtf(fabsf(x)). I don't see an x87 instruction for applying the sign of one float to another, justfchsto unconditionally flip, andfabsto unconditionally clear the sign bit. There is anfcmov, but it requires a P6 or later CPU. You mentioned 8086, but then used.586, so IDK what you're targeting.Better loop body:
Not debugged or tested, but your code full of repeated loads from the same data was making me crazy. This optimized version is here because I was curious, not because I think it's going to help the OP directly.
Also, hopefully this is a good example of how to comment the data flow in code where it's tricky. (e.g. x87, or vectorized code with shuffles).
32bit function calling-conventions return FP results in st(0), so you could do that, but then the caller probably have to store somewhere.
I'm going to answer this on a very basic level for those people new to x87 who may be faced with a calculation that needs to be done on the FPU.
There are two things to consider. If you are given a calculation (INFIX notation) like:
Is there a way to translate this into basic instructions that can be used by the x87 FPU? Yes, at a very basic level the x87 FPU is a stack that acts like a sophisticated RPN calculator. The equation in your code is INFIX notation. If you convert this to POSTFIX(RPN) notation, it can easily be implemented as a stack with operations.
This document provides some information on converting to POSTFIX notation. Following the rules your POSTFIX equivalent would look like:
You could literally put that into an old RPN calculator (HPs) like the HP 15C using these keys where
root=1andx=27:The online HP 15C should show the result of that calculation being 9.667. Translating this to basic x87:
*is fmulp (Multiply ST(1) by ST(0), store result in ST(1), and pop the register stack)/is fdivp (Divide ST(1) by ST(0), store result in ST(1), and pop the register stack)+is faddp (Add ST(0) to ST(1), store result in ST(1), and pop the register stack)-is fsubp (Subtract ST(0) from ST(1), store result in ST(1), and pop register stack)You can literally convert
2.0 root * x root root * / + 3.0 /to x87 instructions:Once you have the basics, you can move on to improving efficiency.
Regarding Edit 2 / Followup question
One thing to keep in mind is that if you don't use instructions that pop values off the stack, each iteration of the loop will consume more FPU stack slots. Generally the FPU instructions ending with
Ppop values off the stack. You don't use any instructions to remove items off the stack, the FPU stack keeps growing.Unlike the program stack in user space, the FPU stack is very limited as it only has 8 slots. If you put more than 8 active values on the stack you will get overflow errors in the form of
1#IND. If we analyze your code and view the stack after each instruction we'd find this:Observe that after the last FDIV instruction and before the JMP we have 5 items on the stack (st(0) through st(4)). When we entered the loop we only had 1 which was
rootin st(0). The best way to resolve this is to use instructions in such a way that values get popped (removed) from the stack as the calculation progresses.One other less efficient way is to free up the values we no longer want on the stack before repeating the loop. The FFREE instruction can used for this purpose by manually marking the entries unused starting from the bottom of the stack. If you add these lines after the code above, and before the
jmp repreatAgainthe code should work:With the use of the FFREE instruction we end the loop with only the new
rootin st(0).I've also added
fst rootbecause of the way you did your calculation. Your calculation includesfld rootwhich relies on the value inrootbeing updated when each loop is finished. There is a more efficient way of doing this but I'm providing a fix that works in your current code without much reworking.If you were to use the inefficient/simple code snippet I provided earlier to do the calculations you'd end up with code likes this:
This code doesn't require FFREE because elements are popped off the stack as the calculation progresses. The instruction FADDP, FSUBP, FDIVP, FADDP will additionally pop the value off the top of the stack. This has the side effect of keeping the stack clear of the partial intermediate calculations.
Integrate a Loop
To integrate the loop into the simple/inefficient code I created earlier, you can use a variant of the FCOM (Floating point compare) for comparison. The results of the floating point compare is then transferred/converted to the regular CPU flags (EFLAGS). One can then use the regular comparison operators to perform the conditional checks. The code could look like this:
Note: The usage of FCOMPP and manual transfer of x87 flags to CPU flags is driven by the fact that you have .586 directive at the top of your code. I'm making the assumption that because you didn't specify .686 or later that instructions like FCOMI are not available. If you were using
.686or later, then the bottom part of the code could have looked like:Quick method to creating RPN/Postfix from Infix notation
If learning to convert Infix notation to RPN/Postfix seems a bit daunting from the document I linked earlier in my question there is some relief. There are a number of websites that will do this work for you. One such site is MathBlog. Just enter your equation, click convert and it should show you the RPN/Postfix equivalent. It is limited to +-/*, parentheses and exponents with ^.
Optimizations
A big key to optimizing the code is to optimize the formula by separating the parts that remain constant between each loop from the parts that are variable. The constant parts can be computed before the loop begins.
Your original equation is this:
Separating the constants part we can arrive at:
If we replace the constants with identifiers where
twothirds= 2.0/3.0, andxover3= x/3 then we end up with a simplified equation that looks like this:If we convert that to POSTFIX/RPN then we get:
A similar optimization is what Peter is taking advantage of in his answer under the section Better loop body. He places the constants
TwothirdsandXover3onto the x87 FPU stack outside the loop, and references them as needed inside the loop. This avoids having to reread them unnecessarily from memory each time through the loop.A more complete example based upon the optimization above:
This code places these values on the stack prior to entering the loop:
Epsilonvalue (0.001)rootbefore calculations are done (effectivelyprevroot)Twothirds(2/3)Xover3(x/3)rootBefore the loop repeats, the stack will have the layout above.
The code at the end before exiting removes all the temporary values and simply leaves the stack with the value of
rooton the top in st(0).