Subscribe for automatic updates: RSS icon RSS

Login icon Sign in for full access | Help icon Help
Advanced search

Pages: [1]
  Reply  |  Print  
Author Topic: Operator ** (exponentiation) is very slow  (Read 435 times)
Lu?s T.
Posts: 27


« on: December 16, 2019, 01:10:30 pm »

Hi,

When looking for some inefficiencies using the profiler we come to the conclusion that the operator "**" is more than 100 times slower than defining and calling a exponentiation function in C. You can see the C code for the function.

The problem is that the precision is not enough or what we are doing.

Does anyone is aware of the implementation of "**" being so inefficient? Do you know about a solution that keeps the precision?

Thanks
Luis

Code:
power(fgl_pcnt)
int fgl_pcnt;
{
    dec_t           base;
    dec_t           expoente;
    dec_t           resultado;
    double          baseinterno;
    double          expoenteinterno;
    double          resultadointerno;
    double          pow();
    mint            deccvdbl_return;

    popdec(&base);
    popdec(&expoente);

    dectodbl (&base, &baseinterno);
    dectodbl (&expoente, &expoenteinterno);

    resultadointerno = pow (baseinterno, expoenteinterno);

    deccvdbl_return = deccvdbl (resultadointerno, &resultado);

    retdec(&resultado);
    return(1);
}

Rene S.
Four Js
Posts: 84


« Reply #1 on: December 16, 2019, 02:25:47 pm »

The operator ** calls a decimal implementation of the function power.
Notice: the exponent is an int.
 
Code
  1. -- read
  2.     a ** b
  3. -- as
  4.    xxx(a, b)
  5. -- where xxx is the
  6.    FUNCTION xxx(x DECIMAL, y INT) RETURNS DECIAMAL

Decimal functions are usually slow compared with the same function using float or double parameters.
Compare the performance of decimal functions with the performance of float or double function before integrating the math coprocessor x87 into the CPU. In those days (before 80486, launched April 1996) those function were implemented by software.

Don't use the operator **.

Use util.Math.pow(x FLOAT, y FLOAT) returning FLOAT

Rene
Lu?s T.
Posts: 27


« Reply #2 on: December 16, 2019, 02:54:56 pm »

Thanks for the answer Rene.

The problem is that, if I call pow(), which is the same than calling the C function we defined, i will loose precision.

We detected the inefficiencies of ** when we migrated our application to Genero. At that moment we substituted ** to the C implementation but we went into a situation where our application didn't work as it worked in Informix 4GL. When we analysed the issue we come to the conclusion the reason was loss of precision. When we rollback to the ** operator, we solved the problem.

I have the idea that the Informix 4GL implementation of ** is quicker than the Genero's one. Don't you have that idea?

Luis

Rene S.
Four Js
Posts: 84


« Reply #3 on: December 16, 2019, 03:54:42 pm »

Hello Luis,
for my curiosity/better understanding: what values of the exponent do you use?
Please give an example reproducing the performance factor 100 comparing the operator ** with your c-function. I can't reproduce this with my values.

I made a quick test, comparing the performance with Informix c4gl. When using huge exponents (>16) then Informix is faster. If the exponent is less than 16 then Genero is faster.
Lu?s T.
Posts: 27


« Reply #4 on: December 16, 2019, 04:21:05 pm »

Hello Rene,

The expoents, in the situation we analysed, are allways negative and run from 0 to -1460.

This happens when we call IRR (Internar Return on Investment), using Newton method. We need to actualize each cash-flows of a loan to the number of days from the initial date of the loan. As we are calculating this in a dayly base, and the operation have 4 years duration, it makes around  1460 day for the last flow.

In the Newton method we do the calculation several times until we find the right rate. That's why the performance of ** is so relevant.

Hope this helps

Luis
Rene S.
Four Js
Posts: 84


« Reply #5 on: December 16, 2019, 04:37:21 pm »

Opps. Yes, this helps a lot!
Please wait for more details.
Rene S.
Four Js
Posts: 84


« Reply #6 on: December 17, 2019, 10:02:03 am »

Hello, I got this morning a mail Henri (thanks again).
See this url: https://en.wikipedia.org/wiki/Exponentiation_by_squaring
The 4gl operator ** uses integer exponents. This fit's exactly to the problem of computation of large positive integer powers of a number.

I've adapted exp_by_squaring_iterative to this function:
Code
  1. FUNCTION myExp(x, n)
  2.    DEFINE x DECIMAL(32)
  3.    DEFINE n INT
  4.    DEFINE y DECIMAL(32)
  5.  
  6.    IF x IS NULL OR n IS NULL THEN
  7.        RETURN NULL
  8.    END IF
  9.    IF n < 0 THEN
  10.        LET x = 1 / x
  11.        LET n = -n
  12.    END IF
  13.    IF n = 0 THEN
  14.        RETURN 1
  15.    END IF
  16.    LET y = 1
  17.    WHILE n > 1
  18.        IF (n MOD 2) == 0 THEN
  19.            LET x = x * x
  20.            LET n = n / 2
  21.        ELSE
  22.            LET y = x * y
  23.            LET x = x * x
  24.            LET n = (n - 1) / 2
  25.        END IF
  26.    END WHILE
  27.    RETURN x * y
  28. END FUNCTION

The function is fast and uses a provision of 32.
The internal implementation of ** should be adapted as soon as possible
Rene S.
Four Js
Posts: 84


« Reply #7 on: December 17, 2019, 10:04:34 am »

s/ a mail Henry / a mail from Henri /
s/ provision / precision /
Lu?s T.
Posts: 27


« Reply #8 on: December 17, 2019, 10:32:46 am »

Thanks Rene and Henry,

Yesterday my colleague Josť Virtuoso found a post in Stack Overflow discussing the theme: https://stackoverflow.com/questions/26860574/pow-implementation-in-cmath-and-efficient-replacement

They refer to the same algorithm and also point for an old post with a really deep discussion about efficient implementations of integer based power function: https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int

In the meanwhile we'll use your myExp() function!
Sebastien F.
Four Js
Posts: 413


« Reply #9 on: December 17, 2019, 12:06:34 pm »

Hello,
We have created the ticket FGL-5315 for this enhancement of the ** implementation.
Seb
Reuben B.
Four Js
Posts: 622


« Reply #10 on: December 18, 2019, 12:10:54 am »

...

This happens when we call IRR (Internar Return on Investment), using Newton method. We need to actualize each cash-flows of a loan to the number of days from the initial date of the loan. As we are calculating this in a dayly base, and the operation have 4 years duration, it makes around  1460 day for the last flow.

...
Luis

whilst this discussion is interesting around the merit and performance of ** versus fgl_decimal_power versus util.math.pow()  (I'd forgotten that the second argument of  ** is an integer, so 4**0.5 gives you 1, not 2 !!!) , what Luis had was a function calculating IRR or Internal Rate of Return.   if I was to guess Luis and other developers with financial software have similar functions written many years ago 

When I put together my example https://github.com/FourjsGenero/fgl_apache_poi showing how you can utilise the Java Apache POI libraries to interact with Word and Excel I had an example in https://github.com/FourjsGenero/fgl_apache_poi/blob/master/fgl_excel_calculation_test.4gl that showed you could create an Excel sheet in memory, populate the cells in memory, put a Excel formula in one cell, evaluate that formula, and return the value of the formula back to the 4gl program.  The example I used with IRR or Internal Rate of Return but any financial formula in Excel could've been similarly exposed and made available to a 4gl program.

I was curious how the performance would compare but then I thought what if I could do that without the overhead of creating an Excel workbook and worksheet in memory, do the Apache POI libraries expose those Excel formulas?.  Sure enough they do so I have added to the repository a 4gl module that exposes some of those functions and some quick tests
https://github.com/FourjsGenero/fgl_apache_poi/blob/master/fgl_financial.4gl
https://github.com/FourjsGenero/fgl_apache_poi/blob/master/fgl_financial_test.4gl

Code
  1. IMPORT FGL fgl_financial
  2. ...
  3.    CALL list_of_values.clear()
  4.    LET list_of_values[1] = -100000
  5.    FOR i = 1 TO 240
  6.        LET list_of_values[i+1] = 592.89
  7.    END FOR
  8.    LET irr = fgl_financial.irr(list_of_values,0.10/12)

In short you do not have to rewrite and maintain financial formulas from scratch in 4gl, you can utilise Java libraries that do the same thing.  I would be curious to know from a precision and performance point of view, how these stack up.  (Of course one day we could go one better and add a package e.g. IMPORT financial, that has these financial methods)

Reuben

Lu?s T.
Posts: 27


« Reply #11 on: December 18, 2019, 11:22:33 am »

Hi Reuben,

Thanks for your contribution. I didn't know the Apache POI Libraries and much less the fgl interface to it.

In any case, the corresponding Excel function for what I am doing is XIRR, which is not an Excel standard function but an Add-in. The difference is that in IRR you pass a list of values and in XIRR you pass a list of values and dates. To use IRR instead, in a 4 year loan for example, I'll have to pass around 1400 values, 95% of the being 0.

I could not find it i POI docs, I supposed because it is an Add-in.

Regards

Luis
Reuben B.
Four Js
Posts: 622


« Reply #12 on: December 18, 2019, 11:27:36 pm »

Luis,

Re: XIRR in Excel and not in ApachePOI I see what you mean.  Never the less there were a few interesting URLs

https://stackoverflow.com/questions/42422429/formula-evaluator-for-xirr-function-in-java
https://github.com/tinca/poi-xirr

plus this one !!! http://4js.com/fjs_forum/index.php?topic=1106.0

Reuben
Pages: [1]
  Reply  |  Print  
 
Jump to:  

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines