We help IT Professionals succeed at work.

Check out our new AWS podcast with Certified Expert, Phil Phillips! Listen to "How to Execute a Seamless AWS Migration" on EE or on your favorite podcast platform. Listen Now

x

Really tricky algorithm question

enray
enray asked
on
Medium Priority
428 Views
Last Modified: 2008-02-20
My job unfortunatly just got rid of some really talented programmers, and i am left to do this. We are working with a new system we are developing which takes an input (stock quotes) from a database (could even be excel file) and returns a specific answers based on the following function:
The function to be evaluated is this:  P.S. the 'E' means Summation (Sigma).

         N-1                    L-1         M-1
y(n) = E a(k) x(n-k) +     E     +     E  b(l,m) x(n-1)  x(n-m)
        K=0                     I=0        m=0


Now, i have no idea why the algorithm has to be based on the above function, (remember, i am taking over a half completed job and im not even a real programmer) but this is what was in the old programmers notes. I need some sort of java or c++ code to evaluate the above function. I know that we are going to be working with 200 stock quotes at a time, so let x(n) be 200 values, choosing some variable (a and b) to be real constant coefficiants.
Comment
Watch Question

Unlock this solution and get a sample of our free trial.
(No credit card required)
UNLOCK SOLUTION
I assumed there are already values loaded in arrays a,x,b
What's the name of the formula?

Author

Commented:
Im not sure what the name is, remember i am reading a programmers notes, but i looked online and it seems like part of an Finitie Impulse Response Filter.
In that case, you would want to have a look at the following file:
http://www.dspguru.com/sw/lib/fir_algs_1-0.c

It is an implementation in C and the fir_basic() function is pretty straight forward to re-implement in Java, like so:

public class FIR {

/**   These functions use most or all of the following input parameters:
*
*       input    - the input sample data
*       ntaps    - the number of taps in the filter  
*       h[]      - the FIR coefficient array
*       z[]      - the FIR delay line array
*/

/****************************************************************************
* fir_basic: Does the basic FIR algorithm: store input sample, calculate      
* output sample, move delay line                                          
*****************************************************************************/
public static double firBasic(double input, int ntaps, doubleh[], double z[])      
{
    int ii;
    double accum;
   
    /* store input at the beginning of the delay line */
    z[0] = input;

    /* calc FIR */
    accum = 0;
    for (ii = 0; ii < ntaps; ii++) {
        accum += h[ii] * z[ii];
    }

    /* shift delay line */
    for (ii = ntaps - 2; ii >= 0; ii--) {
        z[ii + 1] = z[ii];
    }

    return accum;
}
}

You then call the method by: FIR.firBasic(startValue, numTaps, doubleArray1, doubleArray2);

Replace "startValue", "numTaps", "doubleArray1", "doubleArray2" with the appropriate variables.

Commented:
Well here's an idea, treat each function as a function, in other words convert each function in a java function.

Random example not based on anything:
a(k)
 public float a(k)
{
   \\does some work
    returns n;
}

do that for each function, then make a function to handle the entire summation.

You probably want to research the function to understand what it does in order to code it
 
Deuel47, please keep in mind that enray is a self-proclaimed non-programmer.

Commented:
yeah your right orangehead....sorry about that
no worries! :-)

Author

Commented:
Thanks guys... let me try out these code examples, then i will reward points. Thank you all so much!

Author

Commented:
yenkateshwarr, what does t1 refer to? Also, which is the array which will hold the initial values loaded from the external file??
I doubt that yenkateshwarr's example implements the actual algorithm. The source file link that I provided contains implementations of the algorithm with a bunch of variations.
t1 is just a temporary double/float value...
this value is returned after the final calcuation is done

Author

Commented:
Orangeheaed911, what are the nTaps???  
It's the number of applications of the filter. I.e. the size of the arrays.

Author

Commented:
Allright guys, this is what i have: I think it will be good for testing purposes of a specific FIR, but i am now getting indexoutofbounds errors.  Please advise:

class fir2 {
static public float y(int n)
{
int a[] = new int[200];
int x[] = new int[3];
int b[][]=  new int[4][3];

for(int i=0; i<199; i++) { // load array
      a[i] = i+1;
}

for(int i = 0;i<2;i++){ // load array
      x[i]=i+1;
}

for (int i = 0; i < 4; i++){ // load 2d array
       for (int j = 0; j < 3; j++){
              b[i][j] = i*j;
    }
}      

int t1=0;

for(int k=0;k<=n-1;k++)

{
   t1=t1+a[k]*x[n-k];
}

for(int l=0; l <= l-1; l++)
for(int m=0;l<=m-1;m++)
{
   t1=t1+ b[l][m]*x[n-1]*x[n-m];
}
return n;
}
public static void main(String[] args) {
      y(2);
      System.out.println("y100="+y(100));
}

Author

Commented:
Thank you all... points to venkateshwarr
enray, there is such a thing as a point split.

Btw, the reason why you're getting an ArrayIndexOutOfBoundsException is the fact that the array's are defined with a fixed size whereas the input value of n is not bound. This makes the line;
   t1=t1+a[k]*x[n-k];
break when n is larger than the size of a. Also, x is only 3 in size and the index in the earlier referenced line will go from n to n-k, which in your code is from 100 to 0, which is way outside the bounds of that array.
Unlock the solution to this question.
Thanks for using Experts Exchange.

Please provide your email to receive a sample view!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.