29 lines
1.8 KiB
TeX
29 lines
1.8 KiB
TeX
%root: main.tex
|
|
\begin{algorithm}[t]
|
|
\caption{\sampmon(\circuit)}
|
|
\label{alg:sample}
|
|
\begin{algorithmic}[1]
|
|
\Require \circuit: Circuit
|
|
\Ensure \vari{vars}: TreeSet
|
|
\Ensure \vari{sgn} $\in \{-1, 1\}$
|
|
\Comment{\Cref{alg:one-pass-iter} should have been run before this one}
|
|
\State $\vari{vars} \gets \emptyset$ \label{alg:sample-global1}
|
|
\If{$\circuit.\type = +$}\Comment{Sample at every $+$ node}
|
|
\State $\circuit_{\vari{samp}} \gets$ Sample from left input ($\circuit_{\linput}$) and right input ($\circuit_{\rinput}$) w.p. $\circuit.\vari{Lweight}$ and $\circuit.\vari{Rweight}$. \label{alg:sample-plus-bsamp} \Comment{Each call to \sampmon uses fresh randomness}
|
|
\State $(\vari{v}, \vari{s}) \gets \sampmon(\circuit_{\vari{samp}})$\label{alg:sample-plus-traversal}
|
|
\State $\Return ~(\vari{v}, \vari{s})$
|
|
\ElsIf{$\circuit.\type = \times$}\Comment{Multiply the sampled values of all inputs}
|
|
\State $\vari{sgn} \gets 1$\label{alg:sample-global2}
|
|
\For {$input$ in $\circuit.\vari{input}$}\label{alg:sample-times-for-loop}
|
|
\State $(\vari{v}, \vari{s}) \gets \sampmon(input)$
|
|
\State $\vari{vars} \gets \vari{vars} \cup \{\vari{v}\}$\label{alg:sample-times-union}
|
|
\State $\vari{sgn} \gets \vari{sgn} \times \vari{s}$\label{alg:sample-times-product}
|
|
\EndFor
|
|
\State $\Return ~(\vari{vars}, \vari{sgn})$
|
|
\ElsIf{$\circuit.\type = \tnum$}\Comment{The leaf is a coefficient}
|
|
\State $\Return ~\left(\{\}, \func{sgn}(\circuit.\val)\right)$\label{alg:sample-num-return}\Comment{$\func{sgn}(\cdot)$ outputs $-1$ for \circuit.\val $\geq 1$ and $-1$ for \circuit.\val $\leq -1$}\label{alg:sample-num-leaf}
|
|
\ElsIf{$\circuit.\type = var$}
|
|
\State $\Return~\left(\{\circuit.\val\}, 1\right) $\label{alg:sample-var-return}
|
|
\EndIf
|
|
\end{algorithmic}
|
|
\end{algorithm} |