Skip to content

Increase sparsity of pippenger fixed window naf representation #506

@gmaxwell

Description

@gmaxwell

The current fixed window naf used in the pippenger never produces zeros in its representation, even though the code handles them fine and they're faster. The existing representation can be converted into one where there are more zeros by setting a coefficient to zero if it is 1 or -1 and the proceeding digit is strictly negative or strictly positive respectively.

For small windows (where pippenger is already slower than strauss) it's a pretty big speedup. For realistic window sizes it probably isn't a big speedup, but free performance is good.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions