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>

1 files changed, 6 insertions, 0 deletions

diff --git a/formula/inc/core_resource.hrc b/formula/inc/core_resource.hrc
index 9d97fd771d9e..cd2baa334b52 100644
--- a/formula/inc/core_resource.hrc
+++ b/formula/inc/core_resource.hrc
@@ -466,6 +466,7 @@ const std::pair<const char*, int> RID_STRLIST_FUNCTION_NAMES_ENGLISH_ODFF[] =
     { "ORG.LIBREOFFICE.RAWSUBTRACT" , SC_OPCODE_RAWSUBTRACT },
     { "ORG.LIBREOFFICE.ROUNDSIG" , SC_OPCODE_ROUNDSIG },
     { "ORG.LIBREOFFICE.REGEX" , SC_OPCODE_REGEX },
+    { "ORG.LIBREOFFICE.FOURIER", SC_OPCODE_FOURIER },
     { nullptr,  -1 }
 };
 
@@ -909,6 +910,7 @@ const std::pair<const char*, int> RID_STRLIST_FUNCTION_NAMES_ENGLISH_OOXML[] =
     { "_xlfn.ORG.LIBREOFFICE.RAWSUBTRACT" , SC_OPCODE_RAWSUBTRACT },
     { "_xlfn.ORG.LIBREOFFICE.ROUNDSIG" , SC_OPCODE_ROUNDSIG },
     { "_xlfn.ORG.LIBREOFFICE.REGEX" , SC_OPCODE_REGEX },
+    { "_xlfn.ORG.LIBREOFFICE.FOURIER", SC_OPCODE_FOURIER },
     { nullptr,  -1 }
 };
 
@@ -1357,6 +1359,7 @@ const std::pair<const char*, int> RID_STRLIST_FUNCTION_NAMES_ENGLISH_PODF[] =
     { "RAWSUBTRACT" , SC_OPCODE_RAWSUBTRACT },
     { "ROUNDSIG" , SC_OPCODE_ROUNDSIG },
     { "REGEX" , SC_OPCODE_REGEX },
+    { "FOURIER", SC_OPCODE_FOURIER },
     { nullptr, -1 }
 };
 
@@ -1804,6 +1807,7 @@ const std::pair<const char*, int> RID_STRLIST_FUNCTION_NAMES_ENGLISH_API[] =
     { "RAWSUBTRACT" , SC_OPCODE_RAWSUBTRACT },
     { "ROUNDSIG" , SC_OPCODE_ROUNDSIG },
     { "REGEX" , SC_OPCODE_REGEX },
+    { "FOURIER", SC_OPCODE_FOURIER },
     { nullptr, -1 }
 };
 
@@ -2250,6 +2254,7 @@ const std::pair<const char*, int> RID_STRLIST_FUNCTION_NAMES_ENGLISH[] =
     { "RAWSUBTRACT" , SC_OPCODE_RAWSUBTRACT },
     { "ROUNDSIG" , SC_OPCODE_ROUNDSIG },
     { "REGEX" , SC_OPCODE_REGEX },
+    { "FOURIER", SC_OPCODE_FOURIER },
     { nullptr, -1 }
 };
 
@@ -2680,6 +2685,7 @@ const std::pair<const char*, int> RID_STRLIST_FUNCTION_NAMES[] =
     { NC_("RID_STRLIST_FUNCTION_NAMES", "FINDB") , SC_OPCODE_FINDB },
     { NC_("RID_STRLIST_FUNCTION_NAMES", "SEARCHB") , SC_OPCODE_SEARCHB },
     { NC_("RID_STRLIST_FUNCTION_NAMES", "REGEX") , SC_OPCODE_REGEX },
+    { NC_("RID_STRLIST_FUNCTION_NAMES", "FOURIER"), SC_OPCODE_FOURIER },
 
     { nullptr, -1 }
 };