Skip to content

perf: introduce /% zkc operator #1876

Description

When there is division and a remainder:

  • within the same vector
  • with the same registers (or constants) input

The hint for a division already produces the quotient and the remainder. No need to compute it twice for the two operations.

Then instead of creating two divison / remainder lowering pass, we should do only one:


fn div_and_remain(a:u8, b:u8) -> (q:u8, r:u8) {
q = a / b
r = a % b
}

is now compiling to:

fn div_and_remain(u8 a, u8 b) -> (u8 q, u8 r) {
        u8 $4
        u8 $5
        u8 $6
        u0 $7
        u0 $8
        u8 $9
        u8 $10
        u8 $11
        u0 $12
        u0 $13
[0]     q, $4, $5 = hint(a, b) ; $6 = q * b * 0x1 ; $7 = a - $6 - $4 ; $8 = b - $4 - $5 - 0x1 ; $9, r, $10 = hint(a, b) ; $11 = $9 * b * 0x1 ; $12 = a - $11 - r ; $13 = b - r - $10 - 0x1 ; ret
}

but should be only:

fn div_and_remain(u8 a, u8 b) -> (u8 q, u8 r) {
        u8 $5
        u8 $6
        u0 $7
        u0 $8
[0]     q, r, $5 = hint(a, b) ; $6 = q * b * 0x1 ; $7 = a - $6 - $4 ; $8 = b - $4 - $5 - 0x1 ; ret
}

Metadata

Metadata

Labels

bciDeals with bci (Bytecode Intermediate Representation)constraintsIssues directly related to constraint generation.perf

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions