Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add leading/trailing ones and zero count instructions #1133

Closed
bobbinth opened this issue Nov 2, 2023 · 4 comments
Closed

Add leading/trailing ones and zero count instructions #1133

bobbinth opened this issue Nov 2, 2023 · 4 comments
Assignees
Labels
assembly Related to Miden assembly
Milestone

Comments

@bobbinth
Copy link
Contributor

bobbinth commented Nov 2, 2023

Since #1115 has been merged, we have a bit more space to add some useful instructions. I think 4 of such instructions could be:

  • u32clz - count leading zeros.
  • u32ctz - count trailing zeros.
  • u32clo - count leading ones.
  • u32cto - count trailing ones.

We have some of these implemented in #874, and I also believe @bitwalker Implemented handling of these in the compiler somewhere. So, we may be able to re-use some of the logic.

In addition to these, I think we should add corresponding procedures to the std::math::u64 module. This would allow us to compute these values for field elements as well (i.e., first split the field element into low/high 32-bit values using u32split and then use std::math::u64 module to compute the desired value).

One open question: in #874 we also had an implementation of ilog2 instruction on field elements. I wonder if we should also implement this one - or if the above operations can be used somehow to emulate it relatively efficiently.

Implementing the above functionality should close #807 and #863.

@bobbinth bobbinth added the assembly Related to Miden assembly label Nov 2, 2023
@Fumuran Fumuran self-assigned this Dec 5, 2023
@Fumuran
Copy link
Contributor

Fumuran commented Dec 6, 2023

@bobbinth I have a couple of clarifying questions:

  1. Do we want these instructions to consume the value it is applied to? Judging by the mmr implementation — yes, but I want to make sure.
  2. Do we want to create corresponding decorators, as it was done in the Add trailing ones instruction #874? (It's quite a silly question because in order to effectively compute these values we'll need either a decorators, or new operations)

@bobbinth
Copy link
Contributor Author

bobbinth commented Dec 6, 2023

  1. Yes, to be consistent with other similar instructions, these instructions would work as "pop element off the stack and then push the result of the operation onto the stack.
  2. In cases where adding a decorator can make the operation more efficient, we should add it. But I would not introduce new operations in the VM.

@Dominik1999
Copy link
Contributor

Will this be closed this week?

@bobbinth
Copy link
Contributor Author

Closed by #1176 and #1179.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
assembly Related to Miden assembly
Projects
Status: Done
Development

No branches or pull requests

3 participants