tdf#74664 : Adds FOURIER() formula

FOURIER(Array, GroupedByColumns, Inverse, Polar)
is a matrix formula that computes discrete Fourier transform[DFT]
of input array(first argument) via a radix-2, decimation-in-time
fast Fourier transform algorithm.

Unit test for this is coming up in a new commit.

The data in input array(first argument) can be :-

1) grouped by columns (needs to be indicated by flag GroupedByColumns = TRUE)
In this case the array can contain 1 or 2 columns, where the first column
contains the real part of input series and second column if present contains
the imaginary part of the input series. If there is only 1 column, the input
series is treated as purely real. If the number of rows is not a power of 2,
zeroes are appended to the input series internally to make the series length
equal to the next nearest power of 2.

2) grouped by rows (needs to be indicated by flag GroupedByColumns = FALSE)
In this case the array can contain 1 or 2 rows, where the first row
contains the real part of input series and second row if present contains
the imaginary part of the input series. If there is only 1 row, the input
series is treated as purely real. If the number of columns is not a power of 2,
zeroes are appended to the input series internally to make the series length
equal to the next nearest power of 2.

The third argument "Inverse" is a boolean flag to indicate whether an inverse
DFT needs to be computed. This argument is optional and the default value is
FALSE.

The fourth argument Polar is a boolean flag to indicate whether the final output
needs to be in polar coordinates. This argument is optional and the default value
is FALSE.

The result of DFT consists of two columns - first column contains the real parts (or
the magnitudes if Polar=TRUE) and second column contains the imaginary parts (or
the phases if Polar=TRUE).

Implementation:

A fairly straighforward non-recursive implementation of radix-2 FFT algorithm is
written from scratch.

Reference:

Heckbert, P., 1995. Fourier transforms and the fast Fourier transform (FFT) algorithm.
Computer Graphics, 2, pp.15-463.

The normalization factor used in DFT / and inverse DFT in this implementation matches that
of fft() and ifft() functions of Matlab/Octave. It also matches the one used in Wikipedia
article on DFT: https://en.wikipedia.org/wiki/Discrete_Fourier_transform.

Change-Id: If4a40a6ef62bce1f03c589ae5357b2049f66fe64
Reviewed-on: https://gerrit.libreoffice.org/67938
Tested-by: Jenkins
Reviewed-by: Eike Rathke <erack@redhat.com>

2 files changed, 4 insertions, 1 deletions

diff --git a/include/formula/compiler.hxx b/include/formula/compiler.hxx
index 09a507fc3d68..c5e5cfdf0da2 100644
--- a/include/formula/compiler.hxx
+++ b/include/formula/compiler.hxx
@@ -506,7 +506,8 @@
 #define SC_OPCODE_FINDB             495
 #define SC_OPCODE_SEARCHB           496
 #define SC_OPCODE_REGEX             497
-#define SC_OPCODE_STOP_2_PAR        498     /* last function with two or more parameters' OpCode + 1 */
+#define SC_OPCODE_FOURIER           498
+#define SC_OPCODE_STOP_2_PAR        499     /* last function with two or more parameters' OpCode + 1 */
 
 #define SC_OPCODE_STOP_FUNCTION     SC_OPCODE_STOP_2_PAR            /* last function's OpCode + 1 */
 #define SC_OPCODE_LAST_OPCODE_ID    (SC_OPCODE_STOP_FUNCTION - 1)   /* last OpCode */
diff --git a/include/formula/opcode.hxx b/include/formula/opcode.hxx
index d2c6548e286f..b969a0047007 100644
--- a/include/formula/opcode.hxx
+++ b/include/formula/opcode.hxx
@@ -500,6 +500,7 @@ enum OpCode : sal_uInt16
         ocErf_MS            = SC_OPCODE_ERF_MS,
         ocErfc_MS           = SC_OPCODE_ERFC_MS,
         ocEncodeURL         = SC_OPCODE_ENCODEURL,
+        ocFourier           = SC_OPCODE_FOURIER,
     // internal stuff
         ocInternalBegin     = SC_OPCODE_INTERNAL_BEGIN,
         ocTTT               = SC_OPCODE_TTT,
@@ -972,6 +973,7 @@ inline std::string OpCodeEnumToString(OpCode eCode)
     case ocErf_MS: return "Erf_MS";
     case ocErfc_MS: return "Erfc_MS";
     case ocEncodeURL: return "EncodeURL";
+    case ocFourier: return "Fourier";
     case ocTTT: return "TTT";
     case ocDebugVar: return "DebugVar";
     case ocDataToken1: return "DataToken1";