Skip to content
LogoLogo

Arithmetic Shifts

Handling the high sign bits

To get an efficient evaluation algorithm for shift-ind~sra(I,J,S)\widetilde{\textsf{shift-ind}}_\mathsf{sra}(I, J, S), we can bootstrap off of shift-ind~srl(I,J,S)\widetilde{\textsf{shift-ind}}_\mathsf{srl}(I, J, S).

We first define the following auxiliary function, for each input (i,s)(i, s) in the cube B6×B6\mathcal{B}_6 \times \mathcal{B}_6:

ak(i,s)≔{1 if {i}≥64−{s}0 otherwise.\begin{equation*}\textsf{a}_k(i, s) \coloneqq \begin{cases} 1 & \text{ if $\{ i \} \geq 64 - \{s\}$} \\ 0 & \text{ otherwise} \end{cases}.\end{equation*}

We note that for each triple (i,j,s)(i, j, s) in the cube B6×B6×B6\mathcal{B}_6 \times \mathcal{B}_6 \times \mathcal{B}_6,

shift-indsra(i,j,s)=shift-indsrl(i,j,s)+∏k=05jk⋅a(i,s).\begin{equation*}\textsf{shift-ind}_\mathsf{sra}(i, j, s) = \textsf{shift-ind}_\textsf{srl}(i, j, s) + \prod_{k = 0}^5 j_k \cdot \mathsf{a}(i, s).\end{equation*}

So it suffices to construct an efficient circuit for a~(I,S)\widetilde{\mathsf{a}}(I, S).

The Auxiliary Functions

Once again, we define a sequence of auxiliary functions for each k∈{0,…,6}k \in \{0, \ldots , 6\}, now defined on Bk×Bk\mathcal{B}_k \times \mathcal{B}_k.

ak(i,s)≔{1 if {i}≥2k−{s}0 otherwise.\begin{equation*}\textsf{a}_k(i, s) \coloneqq \begin{cases} 1 & \text{ if $\{i \} \geq 2^k - \{s\}$} \\ 0 & \text{ otherwise} \end{cases}.\end{equation*}

Clearly, a=a6\mathsf{a} = \mathsf{a}_6, so it suffices to treat the latter.

Recursive Construction

Once again, we get a recursive substructure:

  • Base Case.

    • a0=0\mathsf{a}_0 = 0.

  • Inductive Case. For each k∈{1,…,6}k \in \{1, \ldots , 6\} and each input triple (i,j,s)∈Bk×Bk×Bk(i, j, s) \in \mathcal{B}_k \times \mathcal{B}_k \times \mathcal{B}_k:

    • ak(i,s)={1 if ik−1=1 and sk−1=1ak−1(i,s) if ik=1≠sk−10 otherwise.\begin{equation*}\textsf{a}_k(i, s) = \begin{cases} 1 & \text{ if $i_{k - 1} = 1$ and $s_{k - 1} = 1$} \\ \mathsf{a}_{k - 1}(i, s) & \text{ if $i_{k = 1} \neq s_{k - 1}$} \\ 0 & \text{ otherwise} \end{cases}.\end{equation*}

Here's a proof sketch. We want to know whether {i}+{s}≥2k\{i\} + \{s\} \geq 2^k overflows modulo 2k2^k. If both summands' most-significant bits are 1, then we definitely get an overflow; if neither are, then we definitely don't. If exactly one of the bits ik−1i_{k - 1} and sk−1s_{k - 1} equals 1, then we get an overflow if and only if the less-significant substrings (excluding the most-significant bits), when added together, produce an overflow.

The Arithmetizations

Using this substructure, we once again get arithmetizations for the multilinear extensions a~k(I,S)\widetilde{a}_k(I, S).

  • Base Case.

    • a~0=0\widetilde{\mathsf{a}}_0 = 0.

  • Inductive Case. For each k∈{1,…,6}k \in \{1, \ldots , 6\} and each (i,s)∈Bk×Bk(i, s) \in \mathcal{B}_k \times \mathcal{B}_k:

    • a~k(I,S)=Ik−1⋅Sk−1+(Ik−1+Sk−1)⋅a~k−1(I,J,S)\widetilde{\textsf{a}}_k(I, S) = I_{k - 1} \cdot S_{k - 1} + (I_{k - 1} + S_{k - 1}) \cdot \widetilde{\mathsf{a}}_{k - 1}(I, J, S).

This completes the efficient arithmetization of the shift indicator functions.