tiehuis / zig-bn Goto Github PK

That is, ignoring division/modulus, also tracking a binary exponent 2^n (with fixed n < 0 if fixed-point?) to make a kind of rational number.

I can just wrap this library with exponent tracking for my use case, which doesn't need bit shifting.

This is currently not possible due to the way we instantiate the structs from a factory function. One way I think we can solve this would be to change how the factory generation works. Pre-define the Bn type first, with the factory function simply a wrapper struct which holds the allocator instead. This should allow zig to determine equality between separate Bn types with different allocators since they won't be anonymous.

Some motivation for this is for stack-allocating small bounded Bn items for internal functions where needed.

Tests currently assume 32-bit words are backing a Bn so changing the backing size results in errors. We should be able to change the backing size to any standard width type without compile errors.

If I think hard enough, we should be able to use mulWithOverflow and addWithOverflow to perform the carry and borrow primitive operations. The bonus this has is that we can then operate on 64-bit words on x64_64 instead of 32-bit words that we currently are (with DoubleLimb being a typedef for a 64-bit word).

i.e.

var a = %%Bn.init();
var a = %%Bn.init();
a.add(&a, &b);
Bn.add(&a, &a, &b);  // still works

The rationale being that we can still support the old style through the Bn namespace as a free function anyway. This just provides an alternative style. The consolidated Bn namespace is a bit more straight-forward, too.

We should drop using an ArrayList to handle resizing limbs and manual manage the capacity and memory in the BigInt itself. The initial reason is so we can better allocate specific memory sizes for small integers and not rely on the internal ArrayList implementations doubling (which we often do not want).

Further, for very large integers, it may be better to allocate exactly the memory required to save space, and given some of the operations that are performed, these often may require extra allocations depending on the circumstance anyway.

Bn.init() currently calls %%limbs.append(0);. instead it should %return limbs.append(0); so that clients can handle out of memory situations. similarly with other​ %% prefix operators.

in general, a library should never %% prefix another library's errors.

Hi, this reminded me of something a buddy of mine wrote. I'm not sure whether this will be useful, but I thought I'd drop the link just in case.

http://dustinjuliano.com/2016/6/

Currently a zero value is defined as any value of limb length 1 with a zero value limb. Alternatively, we can have a unique value of zero being defined as the value with a limb length of 0.

The main remaining issues are comptime problems on smaller limbs, and requiring too many branch evaluations for larger limb sizes.

Checklist for core functions to implement. There are more functions I would like to cover, namely achieving rough parity with GMP, but the following are a good start.

• mul
• add
• sub
• neg
• abs
• divMod (floor/mod)
• divRem (trunc/rem)
• cmp
• sign
• left shift
• right shift
• xor
• ior
• and
• set (integer)
• set (string)
• to (integer)
• to (string)