Sitelet https://github.com/starkware-libs/cairo/pull/10050
Skip to content

bugfix(sierra-sim): Fixed u128_guarantee_mul simulation. - #10050

Merged
orizi merged 1 commit into
mainfrom
orizi/06-07-bugfix_sierra-sim_fixed_u128_guarantee_mul_simulation
Jun 7, 2026
Merged

orizi merged 1 commit into
mainfrom
orizi/06-07-bugfix_sierra-sim_fixed_u128_guarantee_mul_simulation

Conversation

@orizi

@orizi orizi commented Jun 7, 2026 •

Copy link
Copy Markdown
Collaborator

Summary

Fixes the u128_guarantee_mul simulation to correctly compute the high and low 128-bit limbs of a 128×128-bit multiplication. The division was previously using BigInt::one().pow(128) (which equals 1, not 2^128) instead of BigInt::one() << 128, causing incorrect limb splitting. Variable names are also updated from limb0/limb1 to high/low to match their semantic meaning, and the output order is corrected to [high, low, U128MulGuarantee]. Test cases are added to verify both the no-overflow case and the case where the product overflows into the high limb.


Type of change

Please check one:

  • Bug fix (fixes incorrect behavior)
  • New feature
  • Performance improvement
  • Documentation change with concrete technical impact
  • Style, wording, formatting, or typo-only change

Why is this change needed?

BigInt::one().pow(128) evaluates to 1 (one raised to the power of 128), not 2^128. This meant the div_rem was dividing by 1, producing a remainder of 0 and a quotient equal to the full product — making the high/low limb split completely wrong for any non-trivial multiplication.


What was the behavior or documentation before?

The simulation of u128_guarantee_mul produced incorrect high and low limb values due to the division being performed against 1 instead of 2^128.


What is the behavior or documentation after?

The simulation correctly splits the 256-bit product of two u128 values into a high 128-bit limb and a low 128-bit limb using a bitshift (<< 128) for the divisor, and returns them in the order [high, low, U128MulGuarantee].


Related issue or discussion (if any)

N/A


Additional context

U128MulGuarantee is also registered in the bijective type mapping in test_utils.rs to support the new simulation tests.

SIERRA_UPDATE_NO_CHANGE_TAG=Simulation change only.
@reviewable-StarkWare

Copy link
Copy Markdown

This change is Reviewable

orizi commented Jun 7, 2026

Copy link
Copy Markdown
Collaborator Author

This stack of pull requests is managed by Graphite. Learn more about stacking.

@orizi
orizi marked this pull request as ready for review June 7, 2026 10:10
@cursor

cursor Bot commented Jun 7, 2026 •

Copy link
Copy Markdown

PR Summary

Low Risk
Changes only affect offline Sierra simulation and test utilities, not compiler lowering or runtime execution paths.

Overview
Fixes Sierra interpreter behavior for u128_guarantee_mul: the 256-bit product is now split with divisor 2^128 (BigInt::one() << 128) instead of BigInt::one().pow(128) (which is 1), so high/low limbs match the real libfunc semantics. Outputs are returned as [high, low, U128MulGuarantee], with clearer high/low naming.

Adds simulation tests for a small product and for 2^64 × 2^64, and registers U128MulGuarantee in the test type mapping so those tests can specialize the libfunc.

Reviewed by Cursor Bugbot for commit 6997545. Bugbot is set up for automated code reviews on this repo. Configure here.

@TomerStarkware TomerStarkware left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

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

:lgtm:

@TomerStarkware reviewed 3 files and all commit messages, and made 1 comment.
Reviewable status: :shipit: complete! all files reviewed, all discussions resolved (waiting on eytan-starkware).

@orizi
orizi added this pull request to the merge queue Jun 7, 2026
Merged via the queue into main with commit ec69782 Jun 7, 2026
54 checks passed
@orizi
orizi deleted the orizi/06-07-bugfix_sierra-sim_fixed_u128_guarantee_mul_simulation branch June 7, 2026 14:17
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants