Fix expacc #1676
Fix expacc #1676
Conversation
456f1c9 to
91e8a02
Compare
docs/src/design/stack/field_ops.md
Outdated
| The `EXPACC` operation pops top $4$ elements from the top of the stack, performs a single round of exponent aggregation, and pushes the resulting $4$ values onto the stack. The diagram below illustrates this graphically. | ||
| The `EXPACC` operation computes one round of the expression $base^{exp}$. It is expected that `Expacc` is called at least `num_exp_bits` times, where `num_exp_bits` is the number of bits required to represent `exp`. | ||
|
|
||
| It pops top $4$ elements from the top of the stack, performs a single round of exponent aggregation, and pushes the resulting $4$ values onto the stack. The diagram below illustrates this graphically. |
There was a problem hiding this comment.
nit: feels like some redundancy with the word " top" in "It pops top
There was a problem hiding this comment.
ah yes, removed the first "top"
docs/src/design/stack/field_ops.md
Outdated
|
|
||
|  | ||
|
|
||
| Expacc is based on the observation that the exponentiation of a number can be computed by repeatedly squaring the base and multiplying the accumulator by the base when the least significant bit of the exponent is 1. |
There was a problem hiding this comment.
nit: the usage of base to signify the original base and the accumulated base holding the intermediate results is a bit confusing
There was a problem hiding this comment.
Good point. Renamed base -> base_acc, and acc -> result_acc (to disambiguate with the new base_acc).
Even with this change though, I find the English version of the algorithm written here still hard to read, so hopefully the example is enough to make things more clear.
docs/src/design/stack/field_ops.md
Outdated
|
|
||
|  | ||
|
|
||
| Expacc is based on the observation that the exponentiation of a number can be computed by repeatedly squaring the base and multiplying the accumulator by the base when the least significant bit of the exponent is 1. | ||
|
|
||
| For example, take $b^5 = (b^2)^2 \cdot b$. Over the course of 3 iterations ($5$ is $101$ in binary), the algorithm will compute $b$, $b^2$ and $b^4$ (placed in `base`). Hence, we want to multiply `base` in `acc` when $base = b$ and when $base = b^4$, which occurs on the first and third iterations (corresponding to the $1$ bits in the binary representation of 5). |
There was a problem hiding this comment.
nit: same as the previous remark with respect to base
There was a problem hiding this comment.
fixed as above (and in the implementation of op_expacc)
| @@ -208,7 +214,7 @@ The `acc` in the next frame is the product of `val` and `acc` in the current fra | |||
| s_2' - s_2 * h_0 = 0 \text{ | degree} = 2 | |||
| $$ | |||
|
|
|||
There was a problem hiding this comment.
some of the variable names in the remaining constraints should be updated as well
There was a problem hiding this comment.
I left those as-is, since this is the convention that the rest of the file adopts (i.e. use "real names" in the diagram, but then use "stack indices" in the constraints description).
91e8a02 to
fcbd022
Compare
Fixes the docs and edge case of the
EXPACCinstruction. Specifically,expandbasevariables were reversed (inbase^exp)base = 0would fail withinteger underflow