% Latex header for doxygen 1.9.1
\let\mypdfximage\pdfximage\def\pdfximage{\immediate\mypdfximage}\documentclass[twoside]{article}
%% moved from doxygen.sty due to workaround for LaTex 2019 version and unmaintained tabu package
\usepackage{ifthen}
\ifx\requestedLaTeXdate\undefined
\usepackage{array}
\else
\usepackage{array}[=2016-10-06]
\fi
%%
% Packages required by doxygen
\usepackage{fixltx2e}
\usepackage{doxygen}
\usepackage{graphicx}
\usepackage[utf8]{inputenc}
\usepackage{makeidx}
\PassOptionsToPackage{warn}{textcomp}
\usepackage{textcomp}
\usepackage[nointegrals]{wasysym}
\usepackage{ifxetex}
% Font selection
\usepackage[T1]{fontenc}
\usepackage[scaled=.90]{helvet}
\usepackage{courier}
\renewcommand{\familydefault}{\sfdefault}
\usepackage{sectsty}
\allsectionsfont{%
  \fontseries{bc}\selectfont%
  \color{darkgray}%
}
\renewcommand{\DoxyLabelFont}{%
  \fontseries{bc}\selectfont%
  \color{darkgray}%
}
\newcommand{\+}{\discretionary{\mbox{\scriptsize$\hookleftarrow$}}{}{}}
\usepackage{newtxtext, newtxmath}
\usepackage[scaled]{beramono}
\usepackage{tikz,url}
\usetikzlibrary{shapes.geometric, arrows}
\usetikzlibrary {arrows.meta}
\usetikzlibrary{positioning}
\tikzstyle{class} = [rectangle, text centered, draw=black, fill=blue!30]
\tikzstyle{process} = [rectangle, minimum width=2cm, minimum height=1cm, text centered, draw=black, text width=2.3cm, fill=orange!30]
\tikzstyle{decision} = [diamond, minimum width=1.5cm, minimum height=1cm, text centered, draw=black, text width=2cm, fill=green!30]
\tikzstyle{arrow} = [thick,->,>=stealth]
\newcommand{\FunC}{\texttt{FunC}}
\usepackage{listings}
\usepackage{xcolor}
\definecolor{codegreen}{rgb}{0.05,0.2,0.05}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.97,0.97,0.95}
\lstdefinestyle{mystyle}{
	backgroundcolor=\color{backcolour},
	commentstyle=\color{codegreen},
	keywordstyle=\color{magenta},
	numberstyle=\tiny\color{codegray},
	stringstyle=\color{codepurple},
	basicstyle=\ttfamily\footnotesize,
	breakatwhitespace=false,
	breaklines=true,
	captionpos=b,
	numbers=left,
	keepspaces=true,
	numbersep=5pt,
	showspaces=false,
	showstringspaces=false,
	showtabs=false,
	tabsize=2,
	escapechar=\&,
	language=C++,
	upquote=true,
}
\lstset{style=mystyle}
% Arguments of doxygenemoji:
% 1) ':<text>:' form of the emoji, already "LaTeX"-escaped
% 2) file with the name of the emoji without the .png extension
% in case image exist use this otherwise use the ':<text>:' form
\newcommand{\doxygenemoji}[2]{%
  \IfFileExists{./#2.png}{\raisebox{-0.1em}{\includegraphics[height=0.9em]{./#2.png}}}{#1}%
}
% Page & text layout
\usepackage{geometry}
\geometry{%
  a4paper,%
  top=2.5cm,%
  bottom=2.5cm,%
  left=2.5cm,%
  right=2.5cm%
}
\tolerance=750
\hfuzz=15pt
\hbadness=750
\setlength{\emergencystretch}{15pt}
\setlength{\parindent}{0cm}
\newcommand{\doxynormalparskip}{\setlength{\parskip}{3ex plus 2ex minus 2ex}}
\newcommand{\doxytocparskip}{\setlength{\parskip}{1ex plus 0ex minus 0ex}}
\doxynormalparskip
\makeatletter
\renewcommand{\paragraph}{%
  \@startsection{paragraph}{4}{0ex}{-1.0ex}{1.0ex}{%
    \normalfont\normalsize\bfseries\SS@parafont%
  }%
}
\renewcommand{\subparagraph}{%
  \@startsection{subparagraph}{5}{0ex}{-1.0ex}{1.0ex}{%
    \normalfont\normalsize\bfseries\SS@subparafont%
  }%
}
\makeatother
\makeatletter
\newcommand\hrulefilll{\leavevmode\leaders\hrule\hskip 0pt plus 1filll\kern\z@}
\makeatother
% Headers & footers
\usepackage{fancyhdr}
\pagestyle{fancyplain}
\renewcommand{\footrulewidth}{0.4pt}
%
\fancypagestyle{fancyplain}{
\fancyhf{}
\fancyhead[LE, RO]{\bfseries\thepage}
\fancyhead[LO]{\bfseries\rightmark}
\fancyhead[RE]{\bfseries\leftmark}
\fancyfoot[LO, RE]{\bfseries\scriptsize Generated by Doxygen }
}
%
\fancypagestyle{plain}{
\fancyhf{}
\fancyfoot[LO, RE]{\bfseries\scriptsize Generated by Doxygen }
\renewcommand{\headrulewidth}{0pt}}
%
\pagestyle{fancyplain}
%
\renewcommand{\sectionmark}[1]{%
  \markright{\thesection\ #1}%
}
% Indices & bibliography
\usepackage{natbib}
\usepackage[titles]{tocloft}
\setcounter{tocdepth}{2}
\setcounter{secnumdepth}{5}
\makeindex
\usepackage{newunicodechar}
  \newunicodechar{⁻}{${}^{-}$}% Superscript minus
  \newunicodechar{²}{${}^{2}$}% Superscript two
  \newunicodechar{³}{${}^{3}$}% Superscript three
% Hyperlinks (required, but should be loaded last)
\ifpdf
  \usepackage[pdftex,pagebackref=true]{hyperref}
\else
  \ifxetex
    \usepackage[pagebackref=true]{hyperref}
  \else
    \usepackage[ps2pdf,pagebackref=true]{hyperref}
  \fi
\fi
\hypersetup{%
  colorlinks=true,%
  linkcolor=blue,%
  citecolor=blue,%
  unicode%
}
% Custom commands
\newcommand{\clearemptydoublepage}{%
  \newpage{\pagestyle{empty}\cleardoublepage}%
}
\usepackage{caption}
\captionsetup{labelsep=space,justification=centering,font={bf},singlelinecheck=off,skip=4pt,position=top}
\usepackage{etoc}
\etocsettocstyle{\doxytocparskip}{\doxynormalparskip}
\renewcommand{\numberline}[1]{#1~}
%===== C O N T E N T S =====
\begin{document}
\raggedbottom
% Titlepage & ToC
\hypersetup{pageanchor=false,
             bookmarksnumbered=true,
             pdfencoding=unicode
            }
\pagenumbering{alph}
\begin{titlepage}
\vspace*{7cm}
\begin{center}%
{\Large \FunC \\[1ex]\large $2.2.1$}\\
\vspace*{1cm}
{\large Generated by Doxygen}\\
\end{center}
\end{titlepage}
\pagenumbering{roman}
\tableofcontents
\pagenumbering{arabic}
\hypersetup{pageanchor=true}
\doxysection{Main page}
\hypertarget{index}{}\label{index}\index{Main page@{Main page}}
\FunC{} (Function Comparator) is a C++ tool for approximating any univariate,
pure function (without any side-effects)  $f:\texttt{TIN}\to \texttt{TOUT}$
with a lookup table (LUT) over a closed interval $[a,b]$. $\texttt{TIN}$ and
$\texttt{TOUT}$ must be types with overloads for $\texttt{operator+,-}$, and
there must be a commutative
$\texttt{operator*:TIN}\times\texttt{TOUT}\to\texttt{TOUT}$ (so $\texttt{TOUT}$
approximately forms a vector space over the approximate field $\texttt{TIN}$).
We take a LUT as any piecewise approximation of $f$, so a LUT of $f$ takes the
following form.
\[
	L(x) =
	\begin{cases}
		p_0(x)       & \text{if } x_0 \leq x < x_1, \\
		p_1(x)       & \text{if } x_1 \leq x < x_2, \\
		\quad \vdots & \qquad \vdots \\
		p_{N-1}(x)   & \text{if } x_{N-1} \leq x \leq x_N,
	\end{cases}
\] 
where $p_k$ are usually (but not necessarily) polynomials. \FunC{} can
build LUTs where each $p_k$ in the equation above are interpolating polynomials
(up to degree 7 with Chebyshev nodes of the first kind or degree 6 with
Chebyshev nodes of the second kind), Taylor polynomials (up to degree 7), Pade
approximants, or degree 3 Hermite interpolating polynomials. The $x_k$ in the
equation above partition $[a,b]$, so $a = x_0 < x_1 < ... < x_n = b$. The $x_k$
can form a uniform partition (so $x_k=a+k(b-a)/N$) or be an automatically
generated nonuniform partition. The user has no control over the nonuniform
partition to ensure the hash only takes $6$ FLOPs and zero comparisons.
\FunC{} aims to streamline finding a good LUT of $f$ for a user's application. To
do so, we measure factors such as
\begin{DoxyItemize}
	\item absolute and relative tolerances for error
	\item domain usage (i.e. the inputs to $f$ during the runtime of the user's program)
	\item evaluation frequency (i.e. how much work is being done in between calls to $f$)
\end{DoxyItemize}
\FunC's DirectEvaluation class measures the first two, and a LookupTableGenerator optimizes a LUT's step size according to maximum tolerances for error.
Installation details are covered in the Readme.md on \FunC's GitHub \href{https://github.com/uofs-simlab/func}{\texttt{https://github.com/uofs-simlab/func}}.
% -----------------------
\doxysection{Example usage }
\hypertarget{md_motivation}{}\label{md_motivation}\index{Example usage@{Example usage}}
\label{md_motivation_autotoc_md2}%
\Hypertarget{md_motivation_autotoc_md2}%
Before delving into the details of each feature in FunC, we provide several
examples of replacing a mathematical function with a LUT. We then generalize
this process and summarize it as a workflow diagram. After this, we give a
brief overview of the class structure of FunC.
\hypertarget{md_motivation_autotoc_md3}{}
\doxysubsection{How to use FunC to replace a mathematical function with a LUT}
\label{md_motivation_autotoc_md3}
The following example illustrates how to use FunC to build a cubic LUT for an
exponential integral over $[0.01,2]$ with step size $h=0.1$.
\begin{lstlisting}
#include <boost/math/special_functions/expint.hpp>
#include <func/func.hpp>
#include <iostream>
&&
template <typename T> T f(T x){ return boost::math::expint(1,x); } // user function
int main(){ // build an approximation of f over [0.01,2] with uniform stepsize h=0.1
  func::FunctionContainer<double> fc {FUNC_SET_F(f,double)};
  func::UniformExactInterpTable<3,double> LUT {fc, {0.01,2.0,0.1}};
  double x; std::cin >> x;
  std::cout << "f(" << x << ")~" << LUT(x) << std::endl; // print piecewise cubic approx.
}
\end{lstlisting}
We observe the following:
\begin{DoxyItemize}
	\item The LUT is only used once.
	\item The approximation is built according to a step size. We do not
		currently know how much error the approximation has.
	\item It is impossible in principle to know what the user will input, so the
		subdomain $[0.01,2]$ is likely insufficient.
\end{DoxyItemize}
In this case, using a LUT is a poor choice because the overhead from building
the LUT is not balanced out by repeatedly calling the LUT, the LUT introduces
an unknown amount of error, and is only valid over a small subset of the
original domain of $f$. By default, \FunC's LUTs do not perform bounds checking
because doing so introduces nontrivial slowdown when calling {\ttfamily
operator()}. such, any user input outside the range $[0.01,2]$ is undefined
behavior. It is up to the user to guarantee this undefined behavior is not
possible. This is generally done by using a {\ttfamily LookupTable} container
(defined shortly), or making the interval $[a,b]$ larger.
We now consider the following improved example using the same $f$ as before. 
\begin{lstlisting}
int main(){
  // build an approximation of f over [0.01,2] with uniform stepsize h=0.1
  func::FunctionContainer<double> fc {FUNC_SET_F(f,double)};
  func::FailureProofTable<func::UniformEqSpaceInterpTable<3,double>> lut {fc, {0.01,2.0,0.1}};
  // compute max error of LUT
  func::LookupTableGenerator<double> gen(fc,{});
  std::cout << "error=" << gen.error_of_table(lut,1.0) << "\n";
&&
  // take two numbers from the user: max and nevals
  double max; std::cin >> max; int nevals; std::cin >> nevals;
  // print nevals random numbers in the range [0.01, max].
  std::mt19937 mt(0); std::uniform_real_distribution<double> unif(0.01,0.01+std::abs(max));
  for(int i=0; i<nevals; i++){
    double x = unif(mt);
    if(x < 2.0) std::cout << " f(" << x << ") ~ " << lut(x) << "\n";
    else std::cout << " f(" << x << ") = " << lut(x) << "\n";
  } std::cout << std::endl;
}
\end{lstlisting}
Sample input and output:
\begin{lstlisting}
error=0.0216333
3 3 # user input
 f(1.78261) ~ 0.0663324
 f(2.53435) = 0.0238136
 f(2.57526) = 0.0225693
\end{lstlisting}
This example is better suited for a LUT because it can involve numerous
repeated applications. The undefined behavior is gone because the {\ttfamily
FailureProofTable} resorts back to $f$'s defining mathematical formula if $x$
is out of the bounds of the {\ttfamily UniformExactInterpTable}. The {\ttfamily
LookupTableGenerator} provides an estimate of
\[
	E(L) = \max_{x\in[a,b]}\frac{|f(x) - L(x)|}{a_{\mathrm{tol}} + r_{\mathrm{tol}}|f(x)|},
\]
(by default with $a_{\mathrm{tol}}=r_{\mathrm{tol}}=1$ but these values are
adjustable). Whether this is an acceptable amount of error depends on the use
case. If the user provides $(a_{\mathrm{tol}},r_{\mathrm{tol}}) = (1,0)$, then
$E(L)$ is the absolute error of $f$. Similarly, if
$(a_{\mathrm{tol}},r_{\mathrm{tol}})=(0,1)$, then $E(L)$ is the relative error
of $f$. The user can provide any positive values for $a_{\mathrm{tol}}$ and
$r_{\mathrm{tol}}$, and if they are both nonzero then $E(L)<1$ does not
necessarily imply $L$ satisfies {\itshape both} the relative and absolute error
tolerances individually.
The following code shows an MWE of building a {\ttfamily DirectEvaluation}
and a LUT of a special function. A {\ttfamily DirectEvaluation} can record
every argument passed to its {\ttfamily operator()} in a histogram which is
critical for determining useful bounds $a,b$ for a LUT. A {\ttfamily
DirectEvaluation} can simulate error in a LUT by perturbing its arguments by
$r_{\mathrm{tol}},a_{\mathrm{tol}}$. So, the {\ttfamily DirectEvaluation} can
return {\ttfamily rtol*R*f(x)+A*atol} where $R$ and $A$ are uniformly
distributed random numbers in $[-1,1]$.
\begin{lstlisting}
/* User function here. Some LUT types require derivatives of the user
 * function, and this is provided though Boost's automatic differentiation
 * library. To use automatic differentiation, the definition of f must be
 * templated, and any function f calls must have overloads for Boost's autodiff_fvar */
#include <boost/math/special_functions/jacobi_elliptic.hpp>
template <typename T> T f(T x){ return boost::math::jacobi_cn(0.5, x); }
&&
/* If FUNC_DEBUG is defined before including func.hpp, then any DirectEvaluation or 
 * FailureProofTable will have a histogram that stores each argument passed to their
 * operator() during program runtime */
// #define FUNC_DEBUG
#include <func/func.hpp>
#include <iostream>
int main(){
    /* FUNC_SET_F is a macro required to take advantage of Boost's automatic differentiation.
     * - If f is templated on two types, call as FUNC_SET_F(f,TIN,TOUT)
     * - If f cannot be templated as shown FunctionContainer can be constructed with f<double>
		 *   but autodiff will not be available */
    func::FunctionContainer<double> fc {FUNC_SET_F(f,double)};
&&
    /* Arguments to a DirectEvaluation are
		 * (FunctionContainer fc, TIN min=0, TIN max=1, uint nbins=10, TOUT aerr=0, TIN rerr=0)
     * where min,max are used as bounds for the histogram */
    func::DirectEvaluation<double> de {fc,0,2,10,1,1};
    /* Call the function on line 7 with T=double and x=1.011.
		 * If FUNC_DEBUG is defined, then f(x)(1+R*rerr)+A*aerr is returned instead,
		 * where A,R are random numbers sampled from a uniformly distributed random variable over [-1,1] */
    std::cout << de(1.011) << "\n"; 
    std::cout << de << std::endl; // print histogram to stdout if FUNC_DEBUG is defined
&&
    /* build a LUT of f over [0,2] with a step size of h=0.1. Each subinterval will use degree 3
		 * Chebyshev interpolating polynomials */
    func::UniformChebyInterpTable<3,double> lut {fc, {0.0,2.0,0.1}};
    std::cout << lut(1.011) << "\n"; // use a piecewise cubic polynomial to return an approx of f(1.011)
&&
    std::cout << lut << "\n"; // print info about lut
}
\end{lstlisting}
Instead of building a LUT according to a step size, it is better to build a LUT
according to tolerances for error that are as large as possible for the user's
purpose. 
\begin{lstlisting}
int main(){
		auto tableTol = 1e-2;
    func::FunctionContainer<double> fc {FUNC_SET_F(f,double)};
    LookupTableGenerator<TYPE> gen(func_container,0.1,2.0);
    /* Use a LUT factory to build according to a string. Using a NonUniform LUT */
    auto lut = gen.generate_by_tol("NonUniformChebyInterpTable<3>",tableTol);
}
\end{lstlisting}
Any member function of the \texttt{LookupTableGenerator} class that returns a
\texttt{std::unique\_ptr<LookupTable>} (\texttt{generate\_by\_step},
\texttt{generate\_by\_impl\_size}, \texttt{generate\_by\_tol}) can take an
optional \texttt{std::string filename}. When given a \texttt{filename}, that
member function returns the result of \texttt{generate\_by\_file(filename)} if
\texttt{filename} exists. Otherwise, that member function saves its result to
\texttt{filename} before returning. As such, the code used to generate a LUT is
automatically optimized for future runs of the user's program.
\hypertarget{md_motivation_autotoc_md4}{}\doxysubsection{A general workflow}\label{md_motivation_autotoc_md4}
The following is the general workflow we suggest for replacing a mathematical
function with a LUT using \FunC.
\begin{DoxyItemize}
\item The user identifies a mathematical function whose evaluation consumes a
	substantive proportion of total runtime. Further, the mathematical function
	itself must be complicated enough to warrant the use of a LUT. For example,
	it is unlikely that a LUT will speed up an elementary function such as
	$\sin(x)$, $e^x$, etc. because those functions have been continually
	optimized for decades. Good candiates for a LUT include deeply nested
	function compositions, long summations/products, and special functions. Also,
	the process of building a LUT is not without expense. \FunC{} must either
	evaluate the user's function a set number of times or read the LUT from a
	file (both are potentially slow). So, the user's code must evaluate $f$ a
	sufficiently large number of times for construction of a LUT to be
	appropriate.
\item The user determines an interval of approximation $[a,b]$ and tolerances
	for error in their LUT. LUTs over smaller domains and with coarser error
	tolerances perform faster and use less memory.
\item The user should experiment with a wide variety of different LUTs in
	isolation, each constructed according to the user's tolerances for error.
	\FunC{} provides the {\ttfamily	LookupTableGenerator} to test each LUT in
	isolation.
\item After determining 1--2 ideal LUTs, the user should still benchmark their
	code after using those LUTs. Use of a LUT necessarily increases memory usage
	and that can result in overall slowdown compared to the original code.
\end{DoxyItemize}
We note that the above process does not put any emphasis on the specific
approximation used on each subinterval. Again, most LUTs perform similarly
because they share much of the same source code. The main determining factor
for a LUT's performance is its \emph{order} of convergence. For a user to
determine a suitable order for their application, they must experiment with
several LUTs in isolation. 
\begin{figure}[htbp]
%\footnotesize
\scriptsize
\centering
\begin{tikzpicture}[node distance=0.78cm]
	\node (start) [process] {Use a profiler to identify a bottleneck};
	\node (bound) [decision, below right=of start, text width=35mm] {Determine LUT \\ bounds $a,b$ and tolerances \\ $a_{\mathrm{tol}},r_{\mathrm{tol}}$ with a \texttt{DirectEvaluation}};
	\node (failu) [process,  above right=of bound, text width=30mm] {Use a \texttt{LookupTable} Container};
	\node (prove) [process,  below right=of bound, text width=30mm] {Guarantee the suggested bounds are large enough};
	\node (gener) [process,  right=1.85cm of bound, text width=35mm] {Generate several \texttt{LookupTable} implementations according to $a_{\mathrm{tol}}$ and $r_{\mathrm{tol}}$ with a \texttt{LookupTableGenerator}};
	\node (time) [process, right=1.4cm of prove, text width=38mm] {Time each LUT with a \texttt{LookupTableComparator}};
	\draw [arrow] (start) -- (bound);
	\draw [arrow] (bound) -- (failu);
	\draw [arrow] (bound) -- (prove);
	\draw [arrow] (prove) -- (gener);
	\draw [arrow] (failu) -- (gener);
	\draw [arrow] (gener) -- (time);
\end{tikzpicture}
\caption{Suggested \FunC{} workflow}
\label{fig:workflow}
\end{figure}
% ---------------------------------------------------
\doxysection{FunC\textquotesingle{}s class structure }
\hypertarget{md_classstructure}{}\label{md_classstructure}\index{FunC\textquotesingle{}s class structure@{FunC\textquotesingle{}s class structure}}
\label{md_classstructure_autotoc_md0}%
\Hypertarget{md_classstructure_autotoc_md0}%
With this workflow in mind, we now present a brief summary of \FunC's debugging
tools and important classes. To visualize how each of these classes relate to
one another, \FunC's UML class diagram is provided. Each of \FunC's classes are
related to {\ttfamily LookupTable} because they either implement {\ttfamily
LookupTable}, encapsulate a {\ttfamily LookupTable} implementation, or
construct {\ttfamily LookupTable} implementations.
\begin{DoxyItemize}
\item Classes implementing the {\ttfamily LookupTable} interface implement a
	useful set of functions for approximating a mathematical function with a
	piecewise function. The most important member function of a {\ttfamily
	LookupTable} implementation is its {\ttfamily operator()} (because it returns
	approximations of $f(x)$).
\item The {\ttfamily MetaTable} class provides all the mechanisms required to
	approximate a mathematical function with an array of {\ttfamily Polynomial}.
	{\ttfamily MetaTable} exists to reduce code redundancy and as such is
	templated on several parameters: the number of polynomial coefficients for
	each subinterval, {\ttfamily TIN},{\ttfamily TOUT}, and whether the partition
	of $[a,b]$ is uniform. Currently, every class that \emph{constructs} a
	piecewise approximation of $f$ inherits from {\ttfamily MetaTable}.
\item The {\ttfamily LookupTableGenerator} class uses the factory design
	pattern and provides several member functions for building any supported LUT
	according to a step size, data size, or tolerances for relative and absolute
	error.
\item The {\ttfamily DirectEvaluation} class is used for profiling or debugging
	as per the preprocessor macro {\ttfamily FUNC\_DEBUG}. When this macro is
	defined, it helps determine useful LUT bounds (by recording each argument it
	is given before returning $f(x)$) and tolerances for relative and absolute
	error (by perturbing its outputs).
\item The {\ttfamily FailureProofTable} class passes each of its arguments $x$
	to the LUT it encapsulates after checking whether $x$ is within its LUT's
	bounds. If $x$ is not within the LUT's bounds, then the {\ttfamily
	FailureProofTable} computes $f(x)$ using the defining mathematical formula
	for $f$. This makes LUTs safe and straightforward to incorporate into
	existing code, especially if it is impossible/impractical to ensure each
	argument lies within a LUT's bounds.
\item The {\ttfamily ArgumentRecord} class only exists in \FunC if the
	preprocessor macro {\ttfamily FUNC\_DEBUG} is defined. If {\ttfamily
	FUNC\_DEBUG} is defined, then every argument passed to a {\ttfamily
	DirectEvaluation} and any out of bounds arguments passed to a {\ttfamily
	FailureProofTable} are also passed to {\ttfamily ArgumentRecord} to save in a
	histogram before computing $f(x)$. When the destructor of an {\ttfamily
	ArgumentRecord} is called, it prints its histogram to a provided {\ttfamily
	std::ostream*} (but does nothing if the pointer is null).
\item The {\ttfamily CompositeLookupTable} class builds a LUT of $f$ over
	several pairwise disjoint intervals. This enables users to build a LUT over
	custom partitions. When performing interval search, a {\ttfamily
	CompositeLookupTable} must perform binary search over a sorted tree of
	endpoints in $O(\log(N))$ time. If binary search fails, $f(x)$ is returned.
	This class is ideal for piecewise continuous functions and can interact
	nicely with nonuniform LUTs.
\item The {\ttfamily LookupTableComparator} class can compare the time taken to
	apply a set of LUTs to a uniformly distributed random vector.
\end{DoxyItemize}
Every class in \FunC{} with an {\ttfamily operator()} implements {\ttfamily
LookupTable}. Only three classes that implement {\ttfamily LookupTable} do not
also inherit from {\ttfamily MetaTable}. Of these, {\ttfamily
FailureProofTable} and {\ttfamily CompositeLookupTable} are what we call
{\itshape LUT containers}. They resort back to the defining mathematical
formula for $f$ if their interval search fails. LUT containers notably slow the
LUT they encapsulate only because their interval search is slower. The only
other class implementing {\ttfamily LookupTable} that does not also inherit
{\ttfamily MetaTable} is the {\ttfamily DirectEvaluation} class. A {\ttfamily
DirectEvaluation} does not provide an approximation of $f$ for any inputs.
Rather, it evaluates $f$ using the defining mathematical formula. The
{\ttfamily DirectEvaluation} class is provided for the convenience of debugging
and profiling mathematical functions (depending on whether the preprocessor
macro {\ttfamily FUNC\_DEBUG} is defined). 
\begin{figure}[htbp]
\scriptsize
\centering
\begin{tikzpicture}[node distance=0.5cm]
	\node (lutint) [class, text width=2cm,fill=blue!30] {\texttt{<{}<Interface>{}> LookupTable}};
	\node (metata) [class, above=2.3cm of lutint,fill=green!50] {\texttt{MetaTable}};
	\node (eqspac) [class, left=of metata, xshift=-0.2cm,fill=green!30] {\texttt{ExactInterpTable}};
	\node (chebyt) [class, above=0.2cm of eqspac,xshift=0.5cm,fill=green!30] {\texttt{ChebyInterpTable}};
	\node (linraw) [class, above=0.2cm of chebyt,xshift=0.7cm,fill=green!30] {\texttt{LinearRawInterpTable}};
	\node (hermit) [class, right=of metata,xshift=0.2cm,fill=green!30] {\texttt{CubicHermiteTable}};
	\node (taylor) [class, above=0.2cm of hermit,xshift=-0.7cm,fill=green!30] {\texttt{TaylorTable}};
	\node (padeta) [class, above=0.2cm of taylor,xshift=-0.9cm,fill=green!30] {\texttt{PadeTable}};
	\node (polyno) [class, below left=of metata,fill=green!15] {\texttt{Polynomial}};
	\node (transf) [class, below right=of metata,fill=green!15] {\texttt{TransferFunction}};
	\node (failur) [class, left=1.2cm of lutint,fill=orange!30] {\texttt{FailureProofTable}};
	\node (direct) [class, above=of failur, xshift=0.3cm,fill=orange!30] {\texttt{DirectEvaluation}};
	\node (compos) [class, below=of failur, xshift=0.3cm,fill=orange!30] {\texttt{CompositeLookupTable}};
	\node (argrec) [class, left=of direct, yshift=-0.2cm,fill=orange!15] {\texttt{ArgumentRecord}};
	\node (lutgen) [class, right=1.6cm of lutint,fill=red!30] {\texttt{LookupTableGenerator}};
	\node (lutcom) [class, below=of lutgen, xshift=-0.3cm,fill=red!30] {\texttt{LookupTableComparator}};
	\node (lutfac) [class, above=of lutgen=-0.6cm,fill=red!15] {\texttt{LookupTableFactory}};
	\draw [thick,-{Triangle[open]}] (eqspac) -- (metata);
	\draw [thick,-{Triangle[open]}] (chebyt.south east) -- (metata.north west);
	\draw [thick,-{Triangle[open]}] (linraw.south east) -- (metata);
	\draw [thick,-{Triangle[open]}] (hermit) -- (metata);
	\draw [thick,-{Triangle[open]}] (taylor.south west) -- (metata.north east);
	\draw [thick,-{Triangle[open]}] (padeta) -- (metata);
	\draw [thick,-{Diamond[open]}] (polyno.north east) -- (metata.south west);
	\draw [thick,-{Diamond[open]}] (transf.north west) -- (metata.south east);
	\draw [thick,-{Diamond[open]}] (argrec) -- (direct.west);
	\draw [thick,-{Diamond[open]}] (argrec) -- (failur.north west);
	\draw [thick,-{Diamond[open]}] (lutint) -- (failur.south east);
	\draw [thick,-{Diamond[open]}] (lutint) -- (compos.south east);
	\draw [thick,-{Diamond[open]}] (lutfac) -- (lutgen);
	\draw [thick,-{Diamond[open]}] (lutint.south east) -- (lutcom.north west);
	\draw [dashed, thick, ->] (metata) -- (lutint);
	\draw [dashed, thick, ->] (direct.south east) -- (lutint.north west);
	\draw [dashed, thick, ->] (failur.north east) -- (lutint);
	\draw [dashed, thick, ->] (compos.north east) -- (lutint.south west);
	\draw [thick, -] (lutgen) -- node[text width=1cm] {factory pattern}(lutint);
\end{tikzpicture}
\caption{\FunC's Class Diagram}
\label{fig:class_diagram}
\footnotesize
\raggedright
Arrow legend:
\begin{itemize}
	\item Arrows with a triangular tip mean "inherits." For example,
		\texttt{ChebyInterpTable} inherits \texttt{MetaTable}.
	\item Arrows with a diamond tip mean "is a member variable of." For example,
		\texttt{Polynomial} is a member variable of \texttt{MetaTable}.
	\item Dotted arrows mean "implements the interface." For example,
		\texttt{MetaTable} implements the interface \texttt{LookupTable}.
\end{itemize}
\end{figure}
\doxysection{FunC\textquotesingle{}s Lookup\+Table implementations }
\hypertarget{md_lookuptables}{}\label{md_lookuptables}\index{FunC\textquotesingle{}s LookupTable implementations@{FunC\textquotesingle{}s LookupTable implementations}}
\label{md_lookuptables_autotoc_md1}%
\Hypertarget{md_lookuptables_autotoc_md1}%
The practical differences between any two LUTs is the error in the
approximation they use for each subinterval (the $p_k$ from the equation on the
main page) and the number of coefficients it uses to represent its $p_k$.
Categorizing every {\ttfamily LookupTable} implementation based on how they
compute their $p_k$ results in the following four distinct families and two
special cases. The following table shows each family of {\ttfamily LookupTable}
supported in \FunC{} along with some properties.
% I would remake this table from scratch if it has to change...
\tabulinesep=1mm
\begin{longtabu}spread 0pt [c]{*{4}{|X[-1]}|}
\hline
\PBS\centering \cellcolor{\tableheadbgcolor}\textbf{ Name  }&\PBS\centering \cellcolor{\tableheadbgcolor}\textbf{ Necessarily continuous?  }&\PBS\centering \cellcolor{\tableheadbgcolor}\textbf{ Requires derivative?  }&\PBS\centering \cellcolor{\tableheadbgcolor}\textbf{ Non\+Uniform Support  }\\\cline{1-4}
\endfirsthead
\hline
\endfoot
\hline
\PBS\centering \cellcolor{\tableheadbgcolor}\textbf{ Name  }&\PBS\centering \cellcolor{\tableheadbgcolor}\textbf{ Necessarily continuous?  }&\PBS\centering \cellcolor{\tableheadbgcolor}\textbf{ Requires derivative?  }&\PBS\centering \cellcolor{\tableheadbgcolor}\textbf{ Non\+Uniform Support  }\\\cline{1-4}
\endhead
Cheby\+Interp\+Table$<$n$>$  &No  &No  &Yes  \\\cline{1-4}
Exact\+Interp\+Table$<$n$>$  &$C^0$  &No  &Yes  \\\cline{1-4}
Taylor\+Table$<$n$>$  &No  &Yes  &Yes  \\\cline{1-4}
Pade\+Table$<$m,n$>$  &No  &Yes  &No  \\\cline{1-4}
Cubic\+Hermite\+Table  &$C^1$  &Yes  &Yes  \\\cline{1-4}
Linear\+Raw\+Interp\+Table  &$C^0$  &No  &No  \\\cline{1-4}
\end{longtabu}
Notes\+:
\begin{DoxyItemize}
\item Every nonuniform LUT requires derivatives of $f$ to construct their
	nonuniform partition.
\item An {\ttfamily ExactInterpTable<0>} is a piecewise constant LUT, so it is
	likely not continuous.
\end{DoxyItemize}
Overview of each LUTs
\begin{DoxyItemize}
\item By default, a {\ttfamily ChebyInterpTable<n>} takes each $p_k$ to be the
	polynomial of degree $n$ interpolating $f$ on $n+1$ Chebyshev nodes of the
	first kind in $[x_k,x_{k+1}]$. This class depends on Armadillo to solve
	Vandermonde systems. Armadillo only supports matrices with entries in
	{\ttfamily float} or {\ttfamily double}. \FunC{} takes the working precision
	to be {\ttfamily double} because that is the most accurate type available to
	Armadillo. When using a {\ttfamily ChebyInterpTable<n>} with other types,
	\FunC{} statically casts {\ttfamily TIN} or {\ttfamily TOUT} to {\ttfamily
	double}, solves the linear system with Armadillo, and then casts back to the
	original types.
\item An {\ttfamily ExactInterpTable<n>} takes each $p_k$ to be the polynomial
	of degree-$n$ interpolating $f$ on $n+1$ Chebyshev nodes of the {\itshape
	second kind} in $[x_k,x_{k+1}]$ (these are equally spaced nodes for
	$n\in\{0,1,2\}$). These LUTs are deemed ``exact'' because their source code
	contains a hard-coded symbolic expression for $V^{-1}$. The coefficients are
	accurate to the precision of {\ttfamily TIN}. {\ttfamily ExactInterpTable<n>}
	is the only {\ttfamily LookupTable} implementation that can be built over any
	types where {\ttfamily TOUT} forms an approximate vector space over an
	approximate field {\ttfamily TIN}.
\item A {\ttfamily TaylorTable<n>} takes each $p_k$ to be a degree $n$
	truncated Taylor series of $f$ centered at the midpoint of $[x_k,x_{k+1}]$.
	This class uses Boost's automatic differentiation library to
	compute derivatives from the source code defining $f$.
\item A {\ttfamily PadeTable<m,n>} takes each $p_k$ to be the $[m/n]$ Pade
	approximant of $f$ centered at the midpoint of $[x_k,x_{k+1}]$. We require $m
	\geq n > 0$. This class depends on both Armadillo and Boost. As such, the
	working precision is {\ttfamily double}.
\end{DoxyItemize}
There are two classes that are not templated on an unsigned integer.
\begin{DoxyItemize}
\item A {\ttfamily CubicHermiteTable} takes each $p_k$ to be the cubic
	Hermite spline over the data
	\[
		\{(x_k,f(x_k)), (x_k,f\prime(x_k)), (x_{k+1}, f(x_{k+1})), (x_{k+1},f\prime(x_{k+1}))\}.
	\]
	These LUTs are $C^1[a,b]$ and depend on Boost to compute derivatives.
\item A {\ttfamily UniformLinearRawInterpTable} builds the same $p_k$ as a
	{\ttfamily UniformExactInterpTable<1>} with the same parameters, but a
	{\ttfamily UniformLinearRawInterpTable} saves memory by only storing $f(x_0),
	f(x_1),...,f(x_n)$. Its {\ttfamily operator()} must then compute the two
	coefficients of $p_k$ from $f(x_k)$ and $f(x_{k+1})$ before returning
	$p_k(x)$. For comparison, a {\ttfamily UniformExactInterpTable<1>} stores
	both coefficients of each $p_k$, so it uses approximately twice as much
	memory as a {\ttfamily UniformLinearRawInterpTable} with the same parameters.
	The overhead in a {\ttfamily UniformLinearRawInterpTable}'s {\ttfamily
	operator()} is not large. There is no nonuniform variant of {\ttfamily
	UniformLinearRawInterpTable} because it does not allow for quick interval
	search.
\end{DoxyItemize}
We recommend users try to choose a particular family with properties that are
conducive to best approximate $f$. For example, if the LUT must be continuous,
then an {\ttfamily ExactInterpTable} or {\ttfamily CubicHermiteTable} are best. 
\doxysection{Lookup Tables over nonuniform partitions of \mbox{[}a,b\mbox{]} }
\hypertarget{md_comparenonuniform}{}\label{md_comparenonuniform}\index{Lookup Tables over nonuniform partitions of \mbox{[}a,b\mbox{]}@{Lookup Tables over nonuniform partitions of [a,b]}}
\FunC{} provides two methods for constructing a LUT over a nonuniform partition
of $[a,b]$. First, many of \FunC's LookupTable implementations have built-in
support for a nonuniform partition, but such a construction does not allow for
custom partitions of $[a,b]$ from the user. This way, we ensure \FunC{} can
hash its nonuniform LUTs in $6$ FLOPs and zero comparisons. If a custom
partition is required then the other option is to use a {\ttfamily
CompositeLookuptable}, although the resulting LUT will be much slower.
Let $L_1,L_2,...,L_M$ be LUTs of $f$ over the pairwise disjoint intervals
$[a_1,b_1], [a_2,b_2], ..., [a_M,b_M]$, respectively (not necessarily
partitioning the domain of $f$). A {\ttfamily CompositeTable} of
$L_1,L_2,...,L_M$ is a piecewise function of the form
\[
	C(x) =
	\begin{cases}
		L_1(x),      & \text{if } a_1\leq x\leq b_1, \\
		L_2(x),      & \text{if } a_2\leq x\leq b_2, \\
		\quad \vdots & \qquad \vdots \\
		L_M(x),      & \text{if } a_M\leq x\leq b_M, \\
		f(x),        & \text{otherwise.}
	\end{cases}
\]
A {\ttfamily CompositeLookupTable} allows users to build LUTs over arbitrary
nonuniform partitions. This is useful if $f$ has discontinuities, $f$ is
difficult to accurately approximate on some subset of its domain, or the
user's program requires that $f$ is exact at certain other special points
(roots, extrema, inflection points, etc). The downside is that this requires
$O(\log n)$ comparisons each time the class's {\ttfamily operator()} is called.
We can reduce the relative error in a LUT by building a {\ttfamily
CompositeLookupTable} over $f$'s roots. Doing so with $f(x)=\ln|\Gamma(x)|$
over $[0.1,3]$, $L=\texttt{UniformExactInterpTable<3>}$, and $30$ subintervals
reduces $E(L)$ with $a_{\mathrm{tol}}=r_{\mathrm{tol}}=1$ from
$1.19805\times10^{-4}$ to $5.7253\times10^{-6}$ ($21$ times less error).
As for the nonuniform LUTs, they tend to perform best when $f\prime$ is largest at
its endpoints $a,b$. For example, the nonuniform LUT will have almost the exact
same partition as a uniform LUT for the function $f(x)=e^{x^2}$ because
$f\prime(a)=-f\prime(b)\approx10^{-10}$ is very small. To remedy this issue, we can build
a {\ttfamily CompositeLookupTable} over $f$'s inflection points (extremum of
$f\prime$) as shown in the following figure. The constituent nonuniform LUTs use a
nontrivial partition of $[-5,5]$, and the overall composite LUT is $28$ times
more accurate than a single nonuniform LUT and has the same memory usage the
other LUTs.
Building a {\ttfamily CompositeLookupTable} of $e^{-10x^2}$ and including
inflection points in the partition of $[-5,5]$:
\begin{lstlisting}
FunctionContainer<double> func_container{FUNC_SET_F(MyFunction,double)}; auto step = 0.05;
UniformExactInterpTable<3,double>       uniformlut(func_container, {min,max,step});
NonUniformExactInterpTable<3,double> nonuniformlut(func_container, {min,max,step});
/* Build a Composite LUT over the inflection points of exp(-10*x*x) with the same error
 * as uniformlut. Using rtol = atol = 1.0 with E(L) */
LookupTableGenerator<double> gen(func_container, min, max);
auto err = gen.error_of_table(uniformlut); auto a = 0.035;
CompositeLookupTable<double> nonunifcom(func_container, {
	/* {tableKey, left, right, atol, rtol}, */
	{"NonUniformExactInterpTable<3>",min,-1.0/sqrt(2.0*10.0),                       a*err,a*err},
	{"NonUniformExactInterpTable<3>",    -1.0/sqrt(2.0*10.0),1.0/sqrt(2.0*10.0),    a*err,a*err},
	{"NonUniformExactInterpTable<3>",                        1.0/sqrt(2.0*10.0),max,a*err,a*err},
});
&&
/* Verify nonuniformlut and uniformlut are approx. equal and compare with the composite LUT */
std::cout << "Error in uniform LUT:    " << err << std::endl;
std::cout << "Error in nonuniform LUT: " << err << " + " 
	<< gen.error_of_table(nonuniformlut) - err << std::endl;
std::cout << "Error in nonuniform composite LUT: " << gen.error_of_table(nonunifcom) << std::endl;
std::cout << "Memory usage of uniform LUT: " << uniformlut.size() << std::endl;
std::cout << "Memory usage of nonuniform composite LUT: " << nonunifcom.size() << std::endl;
\end{lstlisting}
Output:
\begin{lstlisting}
Error in uniform LUT:    1.05229e-06
Error in nonuniform LUT: 1.05229e-06 + -3.83676e-14
Error in nonuniform composite LUT: 3.52733e-08
Memory usage of uniform LUT: 6432
Memory usage of nonuniform composite LUT: 6496
\end{lstlisting}
The following figure shows how long it takes to apply each LUT from the
previous figure to a random vector of length $1\,000\,000$. We see that the
{\ttfamily CompositeLookupTable}'s {\ttfamily operator()} is about $12$ times
slower than individual LUTs. The {\ttfamily CompositeLookupTable}'s improvement
in accuracy comes at a cost.
Average time to apply the {\ttfamily operator()} of each LUT from the previous
figure ten times to a random vector of size $1\,000\,000$
\begin{lstlisting}
----------------------------------------------------------------------------
Table input and output types: d -> d
Number of trials performed: 10
Number of evaluations used: 1 000 000
----------------------------------------------------------------------------
| LookupTable:      NonUniformExactInterpTable<3> -5 5 0.05 200
| Memory usage (B): 6432
| Timings:          Min 0.00310616s Max 0.00320847s Mean 0.00313021s
----------------------------------------------------------------------------
| LookupTable:      UniformExactInterpTable<3> -5 5 0.05 200
| Memory usage (B): 6432
| Timings:          Min 0.00259926s Max 0.00672951s Mean 0.0030255s
----------------------------------------------------------------------------
| LookupTable:      CompositeLookupTable -5 5 0.0154212 200
| Memory usage (B): 6496
| Timings:          Min 0.0371598s Max 0.0372521s Mean 0.0371988s
----------------------------------------------------------------------------
\end{lstlisting}
\doxysection{Note on templates }
\hypertarget{md_templates}{}\label{md_templates}\index{Note on templates@{Note on templates}}
\label{md_templates_autotoc_md5}%
\Hypertarget{md_templates_autotoc_md5}%
One can theoretically use LUTs with any types such that {\ttfamily TOUT} forms
an approximate vector space over {\ttfamily TIN} (addition and scalar
multiplication accurate to machine epsilon exists). This generality is possible
for the {\ttfamily ExactInterpTable} because the solution to its Vandermonde
system is hard-coded. We cannot currently offer this level of generality for
{\ttfamily PadeTable}s and {\ttfamily ChebyInterpTable}s because they depend on
Armadillo to solve linear systems of equations (possibly also LUTs requiring
derivatives because it is difficult to work out the theory in that case).
Armadillo only supports matrices with entries in {\ttfamily float} or
{\ttfamily double} (which is typical for high-performance linear algebra
libraries). The generality allowed by \FunC{}'s templates is typical of
header-only libraries, but \FunC{} is not a header-only library. Template
values {\ttfamily TIN}$=${\ttfamily TOUT}$=${\ttfamily float} and {\ttfamily
TIN} $=${\ttfamily TOUT} $=${\ttfamily double} are explicitly instantiated for
the {\ttfamily LookupTableFactory}. These are then compiled into a dynamic
library. This way, the user can link their project with {\ttfamily libfunc.so}
(avoiding the increase in compile time from templates) if they use LUTs with
the two most common numeric types. Doing this has resulted in a $1.75$ times
speedup compared to headers only when compiling all the example code on our
GitHub.  This test does not include the time taken to compile {\ttfamily
libfunc.so}, but the user need only compile {\ttfamily libfunc.so} once
anyways. Linking with a dynamic library makes it much easier to quickly
experiment with different LUTs and debug the user code. If user code
instantiates other values of {\ttfamily TIN} and {\ttfamily TOUT}, then those
LUTs are compiled from scratch with those template values at the same time as
the user's code. Similarly, the rest of \FunC's code is header-only. 
%--- Begin generated contents ---

\newpage
\doxysection{Topic Documentation}
\input{topics}
\input{group__MetaTable}
\input{group__Utils}
\newpage

\doxysection{Class Documentation}
\input{annotated}
\input{classfunc_1_1ArgumentRecord}
\newpage
\input{classfunc_1_1ChebyInterpTable}
\newpage
\input{classfunc_1_1CompositeLookupTable}
\newpage
\input{classfunc_1_1CubicHermiteTable}
\newpage
\input{structfunc_1_1curriedLUT}
\newpage
\input{structfunc_1_1curriedLUT_3_010_00_01TIN_00_01TOUT_00_01classname_01_4}
\newpage
\input{classfunc_1_1DirectEvaluation}
\newpage
\input{classfunc_1_1ExactInterpTable}
\newpage
\input{classfunc_1_1FailureProofTable}
\newpage
\input{classfunc_1_1FuncMutex}
\newpage
\input{classfunc_1_1FuncScopedLock}
\newpage
\input{classfunc_1_1FunctionContainer}
\newpage
\input{structfunc_1_1ImplTimer}
\newpage
\input{classfunc_1_1LinearRawInterpTable}
\newpage
\newpage
\input{classfunc_1_1LookupTable}
\newpage
\input{classfunc_1_1LookupTableComparator}
\newpage
\input{structfunc_1_1LookupTableGenerator_1_1LookupTableErrorFunctor}
\newpage
\input{classfunc_1_1LookupTableFactory}
\newpage
\input{classfunc_1_1LookupTableGenerator}
\newpage
\newpage
\input{structfunc_1_1LookupTableParameters}
\newpage
\input{classfunc_1_1MetaTable}
\newpage
\input{structfunc_1_1nth__differentiable}
\newpage
\input{structfunc_1_1nth__differentiable_3_01TIN_00_01TOUT_00_010_01_4}
\newpage
\input{structfunc_1_1LookupTableGenerator_1_1OptimalStepSizeFunctor}
\newpage
\input{classfunc_1_1PadeTable}
\newpage
\input{structfunc_1_1polynomial__helper}
\newpage
\input{structfunc_1_1polynomial__helper_3_01TOUT_00_01N_00_01false_01_4}
\newpage
\input{structfunc_1_1polynomial__helper_3_01TOUT_00_01N_00_01true_01_4}
\newpage
\input{classfunc_1_1RngInterface}
\newpage
\input{classfunc_1_1StdRng}
\newpage
\input{classfunc_1_1TaylorTable}
\newpage
\input{classfunc_1_1Timer}
\newpage
\input{classfunc_1_1TransferFunction}
\newpage

\doxysection{File Documentation}
\input{files}
\input{FunctionContainer_8hpp}
\newpage
\input{Polynomial_8hpp}
\newpage
\input{cxx17utils_8hpp}
\newpage
\input{todo}
% Latex footer for doxygen 1.9.1
%--- End generated contents ---
% Index
%\newpage
%\phantomsection
%\clearemptydoublepage
%\addcontentsline{toc}{section}{\indexname}
%\printindex
\end{document}
