This function can be used to initialize a big integer to either the upper
or lower limit of a 2s-complement integer. Note that the result is still
in sign-magnitude representation, though in order to convert it into twos
complement all one has to do is take the absolute value.
lladd is now implemented in terms of lladdcarry, which returns the carry limb.
Similarly, llsub is implemented using llsubcarry, which returns the borrow limb.
We already have a LICENSE file that covers the Zig Standard Library. We
no longer need to remind everyone that the license is MIT in every single
file.
Previously this was introduced to clarify the situation for a fork of
Zig that made Zig's LICENSE file harder to find, and replaced it with
their own license that required annual payments to their company.
However that fork now appears to be dead. So there is no need to
reinforce the copyright notice in every single file.
After a right shift, top limbs may be all zero. However, without
normalization, the number of limbs is not going to change.
In order to check if a big number is zero, we used to assume that the
number of limbs is 1. Which may not be the case after right shifts,
even if the actual value is zero.
- Normalize after a right shift
- Add a test for that issue
- Check all the limbs in `eqlZero()`. It may not be necessary if
callers always remember to normalize before calling the function.
But checking all the limbs is very cheap and makes the function less
bug-prone.
* Add an optimized squaring routine under the `sqr` name.
Algorithms for squaring bigger numbers efficiently will come in a
PR later.
* Fix a bug where a multiplication was done twice if the threshold for
the use of Karatsuba algorithm was crossed. Add a test to make sure
this won't happen again.
* Streamline `pow` method, take a `Const` parameter.
* Minor tweaks to `pow`, avoid bit-reversing the exponent.
* Correctly scan all the exponent bits, this caused the incorrect result
to be computed for exponents being powers of two.
* Allocate enough limbs to make llmulacc stop whining.
Implemented following Knuth's "Evaluation of Powers" chapter in TAOCP,
some extra complexity is needed to make sure there's no aliasing and
avoid allocating too many limbs.
A brief example to illustrate why the last point is important:
consider 10^123, since 10 is well within the limits of a single limb we
can safely say that the result will surely fit in:
⌈log2(10)⌉ bit * 123 = 492 bits = 7 limbs
A naive calculation using only the number of limbs yields:
1 limb * 123 = 123 limbs
The space savings are noticeable.
Now there are 3 types:
* std.math.big.int.Const
- the memory is immutable, only stores limbs and is_positive
- all methods operating on constant data go here
* std.math.big.int.Mutable
- the memory is mutable, stores capacity in addition to limbs and
is_positive
- methods here have some Mutable parameters and some Const
parameters. These methods expect callers to pre-calculate the
amount of resources required, and asserts that the resources are
available.
* std.math.big.int.Managed
- the memory is mutable and additionally stores an allocator.
- methods here perform the resource calculations for the programmer.
- this is the high level abstraction from before
Each of these 3 types can be converted to the other ones.
You can see the use case for this in the self-hosted compiler, where we
only store limbs, and construct the big ints as needed.
This gets rid of the hack where the allocator was optional and the
notion of "fixed" versions of the struct. Such things are now modeled
with the `big.int.Const` type.
