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

fix: lagrange interpolation #7440

Merged
merged 6 commits into from
Jul 12, 2024
Merged

fix: lagrange interpolation #7440

merged 6 commits into from
Jul 12, 2024

Conversation

iakovenkos
Copy link
Contributor

Fixed a bug in the method compute_efficient_interpolation, that is used, for example, in a constructor for objects in Polynomial class.
The case when interpolation domain contains 0 is now handled correctly. Added several tests that capture this behaviour.

@iakovenkos iakovenkos requested a review from Rumata888 July 11, 2024 12:12
@iakovenkos iakovenkos added the crypto cryptography label Jul 11, 2024
Copy link
Contributor

@Rumata888 Rumata888 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please add the description of why we need the special case and how we handle it and also remove the leftover lines

@iakovenkos iakovenkos enabled auto-merge (squash) July 12, 2024 15:54
Copy link
Collaborator

@AztecBot AztecBot left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

⚠️ Performance Alert ⚠️

Possible performance regression was detected for benchmark 'C++ Benchmark'.
Benchmark result of this commit is worse than the previous benchmark result exceeding threshold 1.05.

Benchmark suite Current: 426a292 Previous: 7dc34b0 Ratio
nativeClientIVCBench/Full/6 13449.637310000015 ms/iter 12177.532443000018 ms/iter 1.10
wasmClientIVCBench/Full/6 42494.44777599999 ms/iter 38612.369022000006 ms/iter 1.10

This comment was automatically generated by workflow using github-action-benchmark.

CC: @ludamad @codygunton

@iakovenkos iakovenkos merged commit 76bcd72 into master Jul 12, 2024
34 checks passed
@iakovenkos iakovenkos deleted the fix-lagrange-interpolation branch July 12, 2024 16:22
rahul-kothari pushed a commit that referenced this pull request Jul 15, 2024
🤖 I have created a release *beep* *boop*
---


<details><summary>aztec-package: 0.46.5</summary>

##
[0.46.5](aztec-package-v0.46.4...aztec-package-v0.46.5)
(2024-07-14)


### Miscellaneous

* **aztec-package:** Synchronize aztec-packages versions
</details>

<details><summary>barretenberg.js: 0.46.5</summary>

##
[0.46.5](barretenberg.js-v0.46.4...barretenberg.js-v0.46.5)
(2024-07-14)


### Miscellaneous

* **barretenberg.js:** Synchronize aztec-packages versions
</details>

<details><summary>aztec-packages: 0.46.5</summary>

##
[0.46.5](aztec-packages-v0.46.4...aztec-packages-v0.46.5)
(2024-07-14)


### Features

* Added barrett_reduction implementation into uintx
([#6768](#6768))
([abced57](abced57))
* Databus allows arbitrarily many reads per index
([#6524](#6524))
([f07200c](f07200c))
* Let LSP always work in a Noir workspace if there's any
(noir-lang/noir#5461)
([8403e84](8403e84))
* Multiple trace structuring configurations
([#7408](#7408))
([e4abe1d](e4abe1d))
* Verify ClientIVC proofs through Bb binary
([#7407](#7407))
([3760c64](3760c64))


### Bug Fixes

* Lagrange interpolation
([#7440](#7440))
([76bcd72](76bcd72))
* Move BigInt modulus checks to runtime in brillig
(noir-lang/noir#5374)
([8403e84](8403e84))
* Run macro processors in the elaborator
(noir-lang/noir#5472)
([8403e84](8403e84))


### Miscellaneous

* Keccak256 in Noir (noir-lang/noir#5316)
([8403e84](8403e84))
* Redo typo PR by omahs (noir-lang/noir#5487)
([8403e84](8403e84))
* Replace relative paths to noir-protocol-circuits
([e89bfd8](e89bfd8))
* Replace relative paths to noir-protocol-circuits
([fae353e](fae353e))


### Documentation

* Minor comments for private refunds/partial notes
([#7447](#7447))
([9bcbb6c](9bcbb6c))
</details>

<details><summary>barretenberg: 0.46.5</summary>

##
[0.46.5](barretenberg-v0.46.4...barretenberg-v0.46.5)
(2024-07-14)


### Features

* Added barrett_reduction implementation into uintx
([#6768](#6768))
([abced57](abced57))
* Databus allows arbitrarily many reads per index
([#6524](#6524))
([f07200c](f07200c))
* Multiple trace structuring configurations
([#7408](#7408))
([e4abe1d](e4abe1d))
* Verify ClientIVC proofs through Bb binary
([#7407](#7407))
([3760c64](3760c64))


### Bug Fixes

* Lagrange interpolation
([#7440](#7440))
([76bcd72](76bcd72))
</details>

---
This PR was generated with [Release
Please](https://github.com/googleapis/release-please). See
[documentation](https://github.com/googleapis/release-please#release-please).
AztecBot added a commit to AztecProtocol/barretenberg that referenced this pull request Jul 16, 2024
🤖 I have created a release *beep* *boop*
---


<details><summary>aztec-package: 0.46.5</summary>

##
[0.46.5](AztecProtocol/aztec-packages@aztec-package-v0.46.4...aztec-package-v0.46.5)
(2024-07-14)


### Miscellaneous

* **aztec-package:** Synchronize aztec-packages versions
</details>

<details><summary>barretenberg.js: 0.46.5</summary>

##
[0.46.5](AztecProtocol/aztec-packages@barretenberg.js-v0.46.4...barretenberg.js-v0.46.5)
(2024-07-14)


### Miscellaneous

* **barretenberg.js:** Synchronize aztec-packages versions
</details>

<details><summary>aztec-packages: 0.46.5</summary>

##
[0.46.5](AztecProtocol/aztec-packages@aztec-packages-v0.46.4...aztec-packages-v0.46.5)
(2024-07-14)


### Features

* Added barrett_reduction implementation into uintx
([#6768](AztecProtocol/aztec-packages#6768))
([abced57](AztecProtocol/aztec-packages@abced57))
* Databus allows arbitrarily many reads per index
([#6524](AztecProtocol/aztec-packages#6524))
([f07200c](AztecProtocol/aztec-packages@f07200c))
* Let LSP always work in a Noir workspace if there's any
(noir-lang/noir#5461)
([8403e84](AztecProtocol/aztec-packages@8403e84))
* Multiple trace structuring configurations
([#7408](AztecProtocol/aztec-packages#7408))
([e4abe1d](AztecProtocol/aztec-packages@e4abe1d))
* Verify ClientIVC proofs through Bb binary
([#7407](AztecProtocol/aztec-packages#7407))
([3760c64](AztecProtocol/aztec-packages@3760c64))


### Bug Fixes

* Lagrange interpolation
([#7440](AztecProtocol/aztec-packages#7440))
([76bcd72](AztecProtocol/aztec-packages@76bcd72))
* Move BigInt modulus checks to runtime in brillig
(noir-lang/noir#5374)
([8403e84](AztecProtocol/aztec-packages@8403e84))
* Run macro processors in the elaborator
(noir-lang/noir#5472)
([8403e84](AztecProtocol/aztec-packages@8403e84))


### Miscellaneous

* Keccak256 in Noir (noir-lang/noir#5316)
([8403e84](AztecProtocol/aztec-packages@8403e84))
* Redo typo PR by omahs (noir-lang/noir#5487)
([8403e84](AztecProtocol/aztec-packages@8403e84))
* Replace relative paths to noir-protocol-circuits
([e89bfd8](AztecProtocol/aztec-packages@e89bfd8))
* Replace relative paths to noir-protocol-circuits
([fae353e](AztecProtocol/aztec-packages@fae353e))


### Documentation

* Minor comments for private refunds/partial notes
([#7447](AztecProtocol/aztec-packages#7447))
([9bcbb6c](AztecProtocol/aztec-packages@9bcbb6c))
</details>

<details><summary>barretenberg: 0.46.5</summary>

##
[0.46.5](AztecProtocol/aztec-packages@barretenberg-v0.46.4...barretenberg-v0.46.5)
(2024-07-14)


### Features

* Added barrett_reduction implementation into uintx
([#6768](AztecProtocol/aztec-packages#6768))
([abced57](AztecProtocol/aztec-packages@abced57))
* Databus allows arbitrarily many reads per index
([#6524](AztecProtocol/aztec-packages#6524))
([f07200c](AztecProtocol/aztec-packages@f07200c))
* Multiple trace structuring configurations
([#7408](AztecProtocol/aztec-packages#7408))
([e4abe1d](AztecProtocol/aztec-packages@e4abe1d))
* Verify ClientIVC proofs through Bb binary
([#7407](AztecProtocol/aztec-packages#7407))
([3760c64](AztecProtocol/aztec-packages@3760c64))


### Bug Fixes

* Lagrange interpolation
([#7440](AztecProtocol/aztec-packages#7440))
([76bcd72](AztecProtocol/aztec-packages@76bcd72))
</details>

---
This PR was generated with [Release
Please](https://github.com/googleapis/release-please). See
[documentation](https://github.com/googleapis/release-please#release-please).
@iakovenkos iakovenkos self-assigned this Jul 19, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
crypto cryptography
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants