TritonVM / triton-vm

Triton is a virtual machine that comes with Algebraic Execution Tables (AET) and Arithmetic Intermediate Representations (AIR) for use in combination with a STARK proof system.
https://triton-vm.org
Apache License 2.0
241 stars 36 forks source link

Change `xy_dot_step` instructions for use in combination with `recurse_or_return` #302

Open Sword-Smith opened 3 months ago

Sword-Smith commented 3 months ago

Currently the xy_dot_step instructions treat the top-two stack elements as pointers and the subsequent three stack elements as an XFieldElement. If instead these instructions had the XFieldElement on top of the stack, and the pointers below, the instructions could be used very efficiently in combination with recurse_or_return.

This change would save 3/26 instructions from the snippet for barycentric evaluation, and be roughly neutral in the two other places where these instructions are used.

These four instructions in the barycentric evaluation snippet could be reduced to one:

                xx_dot_step
                // _ *ptec *partial_terms[n] [acc'] *codeword[n'] *partial_terms[n']

                dup 0
                swap 6
                pop 1
                // _ *ptec *partial_terms[n'] [acc'] *codeword[n'] *partial_terms[n']