Efficient computation of scalar part in Clifford algebra $\DeclareMathOperator\Cl{Cl}$Problem: Let $\Cl(d)$ be the Clifford algebra corresponding to the vector space $\mathbb{R}^d$ with the usual inner product. Given $v_1, \dotsc, v_k \in \mathbb{R}^d$, compute
the scalar part of the product $v_1 \dotsm v_k \in \Cl(d)$ in an efficient way.
One (inefficient) approach would be to first write the $v_j$ in some (ordered) orthonormal basis $\{e_i\}_{1 \leq i \leq d}$, then expand and simplify the product using that $e_i e_j = -e_j e_i$ when $i > j$ and that $e_i^2 = -1$, and finally take the scalar part (constant term) of the result. The problem with this approach is that, when expanding the product, one gets a number of monomials that is exponential in $d$, since $\Cl(d)$ is of real dimension $2^d$ with basis given by ordered products of distinct $e_i$. (Note that in my case $k$ is allowed to be of the order of $d$.)
Since I am not interested in the full product of the $v_j$ but just on the scalar part of it, I wonder if  there is an efficient algorithm for its computation. So far, I have tried using some of the well known identities that hold in $\Cl(d)$, and taking a look at some of the software for doing calculations in Clifford algebras but I couldn't find this exact functionality.
 A: $
\newcommand\R{\mathbb R}
\newcommand\inv{^{-1}}
\newcommand\grade[1]{\langle#1\rangle}
\newcommand\rev\widetilde
\newcommand\conj[1]{#1^*}
\DeclareMathOperator\Re{Re}
\DeclareMathOperator\Spin{Spin}
$
Let $V_k = v_1\cdots v_k$ and $|V_k| = |v_1|\cdots|v_k|$.
When $k$ is odd,
the scalar part $\grade{V_k} = 0$
since $v_1\cdots v_k$ has to be an odd multivector.
When $k$ is even,
$\frac{V_k}{|V_k|} \in \Spin(d)$ and acts on $\R^d$ as a rotation through the action
$x \mapsto \frac{\rev V_kxV_k}{|V_k|^2}$, where $\rev V_k$ is the reversal of $V_k$.
We then have
$$
  \grade{V_k} = \pm|V_K|\cos(\theta_1/2)\cdots\cos(\theta_m/2)
$$
where $m = \lfloor\frac n2\rfloor$ and $\theta_i$
is the rotation angle within in $i^{\text{th}}$ plane
(recalling that in $d$ dimensions $m$ rotations
can happen independently in completely orthogonal planes).
We are not able to determine the sign since $-V_k$ acts identically to $V_k$, a manifestation of the double cover $\Spin(d) \to O(d)$ having kernel $\{\pm1\}$.
The problem is reduced to computing the sign and $|\cos(\theta_i/2)|$.

One possibility for computing $|\cos(\theta_i/2)|$ is the following:
The product $V_k$ represents this rotation as a sequence of reflections,
where e.g. $x \mapsto \frac{-v_1xv_1}{v_1^2}$
is the reflection of $x$ through the hyperplane orthogonal to $v_1$.
We can then compute the action of $V_k$ on any $x$
by applying each reflection individually:
$$\begin{aligned}
  x_1 &= \frac{-v_1xv_1}{v_1^2} = x - 2\frac{x\cdot v_1}{v_1^2}v_1, \\
  x_2 &= \frac{-v_2x_1v_2}{v_2^2} = x_1 - 2\frac{x_1\cdot v_2}{v_2^2}v_2, \\
      &\;\;\vdots \\
  x = x_k &= \frac{-v_kx_{k-1}v_k}{v_k^2} = x_{k-1} - 2\frac{x_{k-1}\cdot v_k}{v_k^2}v_k.
\end{aligned}
\tag{$*$}
$$
Hence any basis $\{e_i\}_{i=1}^d$ of $\R^d$ may be chosen,
the action of $V_k$ on this basis computed,
and a matrix $R$ computed; explicitly
$$
  R_{ij}
= e_i\cdot\left(\frac{\rev V_ke_jV_k}{|V_k|^2}\right)
= e_i\cdot(e_j)_k
$$
where $(e_j)_k$ is the result of apply the above process ($*$) to $e_j$.
The eigenvalues of $R$ are
$$
  \lambda_1,\conj\lambda_1,\dotsc,\lambda_m,\conj\lambda_m,
  \underbrace{1,\cdots,1}_{d-2m\text{ times}},
$$
where $\conj\lambda_j$ is complex conjugation
and where we may take $\lambda_j = \cos\theta_j + i\sin\theta_j$.
Note that $d - 2m$ is $0$ if $d$ is even and $1$ if $d$ is odd.
Since $|\cos(\theta/2)| = \sqrt{\frac12 + \frac12\cos\theta}$, we arrive at
$$
  \grade{V_k} = \pm|V_k|\prod_{j=1}^m\sqrt{\frac12 + \frac12\Re\lambda_j}.
$$
