*Grails Finance 1.2*

Or indices if they have any, that is. I invented my own algorithm to approximate periods of waves. Of course, there is also the Fast Fourier transform, which is a much better algorithm so I used that too.

## Monte Carlo correlation averaging

This is the amazing algorithm I mentioned. These are the steps of the procedure

- Split up the list of timeseries data in pieces of the same size say 7.
- Shuffle the pieces randomly and construct a new list of timeseries data.
- Calculate the correlation of the original data and the shuffled data.
- Do this again, and again. Average it, and again, and so on etc..
- Do this for different numbers then say 7.

The idea is that if some repeating pattern exists, for instance a sine wave, then if the period of the wave is near the split size the correlation will be pretty strong. With large split size there are not so many pieces, so the accuracy is questionable and therefore I correct for it.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | ... def periods(close) { def totals = [:] def rand = new Random(System.currentTimeMillis()) def corr = new SpearmansCorrelation() for(j in 0..ITERATIONS) { shuffle(close, totals, corr, rand) } def sortedMap = totals.sort { a, b -> b.value <=> a.value } def normalized = [:] sortedMap.each { key, value -> normalized[key] = value/ITERATIONS } def top6 = normalized.keySet() as List return top6[0..5] } def hack(close, n) { def listOfLists = [] for(i in (0 ..<close.size()).step(n)) { def end = i + n if(end > close.size()) end = close.size() listOfLists << close[i..<end] } return listOfLists } def shuffle(close, totals, corr, rand) { for(n in 5..close.size()) { def listOfLists = hack(close, n) Collections.shuffle(listOfLists, rand) listOfLists = listOfLists.flatten() if(!totals[n]) { totals[n] = 0 } def correctionFactor = close.size()/n def val = corr.correlation(close as double[], listOfLists as double []) * correctionFactor totals[n] += val } } ... |

Here is the test using 3 wave components.

1 2 3 4 5 6 7 8 9 10 11 12 | ... void testPeriods() { def sinus = [] for(i in 0..2600) { sinus << 7 + Math.sin( Math.PI/6 + 2 * Math.PI * i / 23) - Math.cos( Math.PI/4 + 2 * Math.PI * i / 42 ) + Math.sin( 2 * Math.PI * i / 7 ) } def top6 = shuffleService.periods(sinus) assertTrue(top6.contains(23) && top6.contains(42) && top6.contains(7)) } ... |

## Fast Fourier transformation

Luckily Apache Commons Math has a FastFourierTransformer class.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | ... public int shift(int i, int l) { int shifted = 0; if (i < l / 2) { shifted = i + l / 2; } else { shifted = i - l / 2; } return shifted; } public List<Long> fft(double[] doubles) { FastFourierTransformer transformer = new FastFourierTransformer(); Complex[] transformed = transformer.transform(doubles); double[] shiftedAbs = new double[transformed.length]; double[] f = new double[transformed.length]; TreeMap<Double, Double> map = new TreeMap<Double, Double>(); for (int i = 0; i < transformed.length; i++) { shiftedAbs[shift(i, transformed.length)] = transformed[i].abs(); f[i] = -0.5 + i / (double) doubles.length; } for (int i = 0; i < shiftedAbs.length; i++) { map.put(shiftedAbs[i], f[i]); } List<Long> periods = new ArrayList<Long> (); for (Map.Entry<Double, Double> entry : map.entrySet()) { Double key = entry.getKey(); Double value = entry.getValue(); if(value > 0) { periods.add( Math.round(1/value) ); } } return periods; } ... |

and unit tests

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | ... public double f(double x) { return 7 + Math.sin(2 * Math.PI * x / 23) - Math.cos(2 * Math.PI * x / 42) + Math.sin(2 * Math.PI * x / 7); } @Test public void testShift() { assertEquals(2, fft.shift(0, 4)); assertEquals(3, fft.shift(1, 4)); assertEquals(0, fft.shift(2, 4)); assertEquals(1, fft.shift(3, 4)); } @Test public void testFft() { double[] doubles = new double[2048]; for (int i = 0; i < doubles.length; i++) { doubles[i] = f(i); } List<Long> periods = fft.fft(doubles); assertEquals( 23, periods.get(periods.size() - 1).intValue() ); assertEquals( 42, periods.get(periods.size() - 2).intValue() ); assertEquals( 7, periods.get(periods.size() - 3 ).intValue()); } ... |

## Moving average

A moving average is a filtering device, which accepts a period as parameter. This method calculates the simple moving average of a list of data.

1 2 3 4 5 6 7 8 9 10 11 12 | ... def sma(list, period) { def averages = [] for( i in (period - 1)..<list.size()) { def sublist = list[i..< Math.min(period + i, list.size() )] averages << StatUtils.mean(sublist as double[]) } return averages } ... |

## Spreadsheet

I calculated the periods of various stocks using FFT and my own algorithm. The result for close price and relative change ( [today – yesterday]/yesterday) of close price data can be found in the first two sheet. The last sheet shows a 1 year plot of relative changes of the close price and its simple moving average with period 3. We have to bear in mind that even with a large data set aliasing can occur.

My algorithm is slow and inaccurate, but at least it lets you use all of the data. FFT is more picky you need to offer it a number of data points, that is a power of 2, sor for instance 2048. So what I did was calculate the periods for the first 2048 points of the dataset and the last 2048 points. Because there is considerable overlap I decided to use the union of the respective top 9 periods found as end result. I found the results I found for the close price with FFT a bit suspect. It seems that the periods I got such as 228, 293, 683 describe standing waves on the 2048 set. I also got 1024, 2048 and 512 as results, but I rejected them immediately. The results for the relative change of the close price seem more trustworthy.

## Random links of interest

- Programming massively parallel processors with CUDA – Stanford lectures on Itunes.
- Sparql explorer for Wikipedia.
- Mathjax
- Calc functions by category
- Etfdb