* 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.
closes#4682
The self-hosted compiler is still bit rotted and still not compiling
successfully yet. I have a more serious rework of the code in a
different branch.
This change was mostly made with `zig fmt` and this also modified some whitespace. Note that in some files, `zig fmt` produced incorrect code, so the change was made manually.
