Square root algorithm 1

[webrabbit]

Does anyone know the algorithm used by Micro Focus COBOL 3.4 to compute a square root (ROOT = SQUARE ** .5)? It seems to be very fast, even with 18-digit numbers.

 

[3gm]

I assume from your question that you're asking about the COMPUTE statement and not the SQRT intrinsic function? If so, then is the question one of how they do fractional exponentiation so quickly?

Glenn

PS - I always figured there was some little guy in there with a really fast slide rule ;-)

 

[k5tm]

Webrabbit,

The obvious answer to your question is, "Yes!"

There are some nifty numerical methods to do logarithms. Unfortunately, I don't have a ready list of references, nor the time to assemble a list.

Tom Morrison

http://www.liant.com

 

[webrabbit]

My question was not hypothetical. I was asking specifically what algorithm in used in the specific COMPUTE statement. Does the compiler recognize the "** .5" as a request for a square root and implement a different algorithm (which one) for this specific exponent, or does it use a standard fractional exponentiation algorithm (again, which one)? Again, the question is not hypothetical. Obviously "someone" knows the answer. My request is for (at least a pointer to) the specific algorithm used in either case.

I know that some compilers, for instance, recognize the multiplication/division of a binary number by a power of two and implement it as a register shift.

 

[PHV]

Have you tried to generate an assembler listing ?

Hope This Helps, PH.
Want to get great answers to your Tek-Tips questions? Have a look at FAQ219-2884 or FAQ222-2244

 

[k5tm]

Sorry, didn't mean to trivialize your question with my response.

You should be able to test some of these questions.

For example, to test for a compiler optimization you could time [tt]COMPUTE A = B ** 0.5[/tt] vs. [tt]COMPUTE A = B ** FRAC-PWR[/tt] where FRAC-PWR is defined PIC 9V9(17) and you MOVE 0.5 to FRAC-PWR (which might defeat a compiler optimization -- but you might have to bury the MOVE in a PERFORMed or CALLed procedure to defeat a really thorough optimizer).

You could also test for a runtime optimization (again, using the FRAC-PWR mechanism) for 0.5 vs. other, less-used fractional powers to see if 0.6, 0.7, 0.8, etc produce extremely different timings. If the timings are different, then you probably have shown that the runtime is using a special test for square root (perhaps to allow use of the same internal routine as the intrinsic).

Happy hunting.

Tom Morrison

http://www.liant.com

 

[salk61]

hello
try to make an external subroutine in "C" that makes the square root, then return the result to your cobol pogram

what release of cobol compiler do you have??
Do you know that micro focus cobol have functions to do that??

 

[webrabbit]

I am not asking how to optimize the code. I am asking what algorithm is used in that specific case. It is version 3.2.46.

I am aware the Micro Focus COBOL has intrinsic functions, but I was curious about that specific code.

Thank you Tom for the suggestions. I should have thought of that, but I was wondering what the specific algorithm was. I will try it.

Thank you PHV. I will look in the books on how to do that. I did it once a long time ago.

 

[TLeaders]

Webrabbit

Why don't you drop an email to Micro Focus and ask them. Unless you want to decompile the compiler I do not think that you will get the answer any other way.

Let us know what you find out.
Tom

 

[jmanj]

I was wondering about this too. Long time ago I was searching if Cobol does have an algorithm to find the root of a number. This is a very difficult thing to do in cobol and maybe that's why nobody can even give you an specific answer to this question. It would take many pages of codes just to write an algorithm for a square root. That also depending on the number of nearest decimal involved. One puzzling question is what is the square root of 2? Of course the answer is 2. But can you make an algorithm on it? There are lots of root algorithm in the internet which you can follow and make it into codes but it would not be easy.

The only real algorithm I was able to find was an algorithm that was written in C language. There are two classes of algorithm written for this purpose. One was for 16 bit processors and the other for the 32 bits. My big hunch is that Cobol intrinsic functions calls this C routines.

Calculator manufacturers are also another resource that may be able to shed some light on this issue.

 

[Glenn9999]

Actually the standard algorithm for powers (roots are fractional powers) usually is coded to be:

z = exp(y* ln(x)) where our original interest is z = x^y. where x > 0.

As was stated, there's many ways to approach this problem, but the one I mentioned is the standard way for computers, since it's very generic and faster compared to a lot of the other options. The only downside is the exp and ln opts take some CPU cycles beyond the normal ops. This is something like 21 cycles in the PC environment, which is still very fast compared to the other options, like Newton's approximation.

It depends, though, on the purpose. If y is always an integer or a known integer, it'd be very hard to argue this formula to be superior to a simple loop - if I had a sqr or cube function, I would tend to go for a z = x * x or x * x * x coding versus the formula above.

Anyway the formula above has served me quite well when a intrinsic power function wasn't available.