feat: add a partition selector #486
Conversation
|
tests that fail: |
We want to handle the case when `Partition` needs to select the whole input.
It seems that handling pivot points at the end of the array was not a good idea. That will introduce the overhead of one more nonlinear constraint, while in many cased it is not needed.
|
|
|
I'll close this for now. Later it could be reopened, if needed. |
|
Sorry for not reviewing the PR in time. We definitely appreciate the contribution. Skimming through the implementation it seems to be of high quality and I wouldn't mind merging. I was just postponing the review after other tasks :) From my side, it can stay open because imo otherwise the PR will be buried into other closed (and merged) PRs. |
|
No worries, actually I realized that you guys were busy and because it wasn't something high priority, I didn't want to keep the PR list crowded, so I closed it to reopen later. |
Also removes a todo about a failing test, since that test is not failing anymore.
ivokub
left a comment
ivokub
left a comment
There was a problem hiding this comment.
Thanks for the contribution! I think that the gadget is useful and implementation seems very good.
I have some few inline comments though. I think error should be handled but I'm not sure if would be good to add new methods.
Signed-off-by: aybehrouz <[email protected]>
Apparently, Go runs all the init functions of a package when the package is imported. So, there is no point in having multiple init functions in different source files.
|
Suggested edit: diff --git a/std/hints.go b/std/hints.go
index a5a2a9bc..a570d762 100644
--- a/std/hints.go
+++ b/std/hints.go
@@ -31,6 +31,6 @@ func registerHints() {
solver.RegisterHint(bits.NNAF)
solver.RegisterHint(bits.IthBit)
solver.RegisterHint(bits.NBits)
- selector.RegisterAllHints()
+ solver.RegisterHint(selector.GetHints()...)
solver.RegisterHint(emulated.GetHints()...)
}
diff --git a/std/selector/multiplexer.go b/std/selector/multiplexer.go
index 25a8b149..c9611a0f 100644
--- a/std/selector/multiplexer.go
+++ b/std/selector/multiplexer.go
@@ -14,23 +14,22 @@ package selector
import (
"fmt"
- "github.com/consensys/gnark/constraint/solver"
"math/big"
+ "github.com/consensys/gnark/constraint/solver"
+
"github.com/consensys/gnark/frontend"
)
func init() {
// register hints
- RegisterAllHints()
+ solver.RegisterHint(GetHints()...)
}
-// RegisterAllHints registers all the hint functions that are used by this package by calling
-// solver.RegisterHint.
-func RegisterAllHints() {
- solver.RegisterHint(stepOutput)
- solver.RegisterHint(muxIndicators)
- solver.RegisterHint(mapIndicators)
+// GetHints returns all hint functions used in this package. This method is
+// useful for registering all hints in the solver.
+func GetHints() []solver.Hint {
+ return []solver.Hint{stepOutput, muxIndicators, mapIndicators}
}
// Map is a key value associative array: the output will be values[i] such that keys[i] == queryKey. If keys does not
|
ivokub
left a comment
ivokub
left a comment
There was a problem hiding this comment.
Changes wrt. hints. See also the comment vs Slice/Partition.
|
I agree with changes wrt. hints. Let's all packages have the same method for handling hints. |
This commit adds a `Slice` function which is a wrapper for a cascade of two `Partition` calls. It also makes StepMask unexported.
ivokub
left a comment
ivokub
left a comment
There was a problem hiding this comment.
Hmm. I think it almost looks perfect. How many constraints we add when we also want to handle pivot at beginning of end of the slice? If it is two contstraints per partition then I would definitely add (just add boundary cases).
Now we handle the case when pivotPosition is at the start or end of the input array. Signed-off-by: aybehrouz <[email protected]>
ivokub
left a comment
ivokub
left a comment
There was a problem hiding this comment.
Looks good! Merge ahead!
3 participants
This is a simple partition selector. It selects the first count number of the input array, keeps them and zeros all other entries or vice versa. By cascading these gadgets a slice can be selected. It works using a step function as a mask.
I just had this idea and tried to implement it. I'm not sure if my implementation is good or if this is useful. Currently some tests are failing for a specific curve. I have no idea why, and I don't know how I can fix that!