Skip to content

Reimplement UInt256.limbs fully in Big endian instead of Little endian #9475

@lu-pinto

Description

@lu-pinto

Right now, the UInt256 implementation for mod, addmod, mul, etc, ... uses a number representation with mixed endian, little and big endian. Big endian is used for each integer of the limbs(int[]), naturally by how the JVM represents numbers. The Little endian ordering is used for the int[] array of the limbs where each index is ordered in little endian.

I believe we should just change to Big endian in both cases and make it consistent. I have some arguments in favor:

  • There is no performance degradation for preferring Big over Little endian. It's just a change in how we loop - number of indices traversed does not change.
  • JDK Arrays.mismatch, which supports vectorization, only operates forward and there's no reverse search. This unlocks efficient algorithms.
  • Currently length does not show the effective limb size, discounting zeros. Right now it's a best effort length. By tying length to the exact number of non zero limbs in the number I expect some performance fast paths, and resulting in less indices traversed in algorithms.
  • In terms of readability length is very misleading if one is not well versed in the code and is expected it to be the effective limb size.
  • For future proofing, in the case anyone reuses a UInt256 instance to compute 2 mods in sequence, or if we decide to use UInt256 in the EVM stack, length needs to be consistent all the time.

Metadata

Metadata

Type

No type

Projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions