Re: [ANN] lua-bint - Arbitrary precision integer arithmetic library in pure Lua

Counting number of bits in what context? The library doesn't have this function, I do shift in one bit in integer pow functions but it's not much with the intention of counting bits.

What I would like to optimize more is the conversion from base 2 to base 10 in the library, it is used when printing big numbers in base 10 as string. My `tobase` function calls too many times `udivmod` (unsigned integer division with modulus) for really large integers (8192 bits or so) and this make tostring very slow for big numbers. If you have any ideas how I could optimize that base conversion (or perhaps udivmod) I would appreciate it.

Em sex., 10 de jul. de 2020 às 15:04, Philippe Verdy <verdyp@gmail.com> escreveu:

Counting the number of bits can be improved a lot instead of using successive shifts by 1 bit, you can at least compute the number of bits set in a 32 bit integer in a very few operations, without any loop.
See https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

Le ven. 10 juil. 2020 à 15:41, Eduardo Bart <edub4rt@gmail.com> a écrit :
That is a good point, thus I've slightly changed the library initialization APIs to avoid conflicts when using different precisions between different project parts, this is good now too because allows working with different integer precisions in the same project in case needed. Although mixing operations with integers of different sizes is not permitted and was a design choice from the beginning in favor of efficiency and simplicity. I've also added functions for bitwise rotation.

Em sex., 10 de jul. de 2020 às 07:50, Philippe Verdy <verdyp@gmail.com> escreveu:
The fact it uses the same fixed-width for all further operations (using a "static" storage from the initialization) limits the usability as a generic-purpose "library": you cannot reuse the library in projects that need different precision. Otherwise they will all use the same precision (256 bits by default) and any change (using different "initializations") will destroy the results with existing instances.
Ideally, the bigints should have a member containing their number of bits (and an indicator that unsigned arithmetic occurs), so that each instance carries it.
As well the library should include primitives to support "rotates"

Le ven. 10 juil. 2020 à 00:13, Eduardo Bart <edub4rt@gmail.com> a écrit :
In the last week I've been working on a new arbitrary precision integer
arithmetic library for Lua. I've mainly created it because
I needed a library that followed Lua 5.3+ integer semantics but could work
with large integers with efficiency in pure Lua, as none of the existing lua libraries
fitted my requirements I made this new one. Fully documented,
with a test suite covering all the code, with many examples and
being used already in some of my github projects.

Features:
* Small, simple and self contained
* Efficient (for a pure Lua integer library)
* Works with a fixed width integer
* Follows Lua 5.3+ integer arithmetic semantics by default
* All integer overflows wraps around
* Can work with large integer widths with reasonable speed (such as 1024bit integers)
* Implements all lua arithmetic operators (+, -, *, //, /, %) and bitwise operators (&, |, ~, <<, >>)
* Provide methods to work with unsigned arithmetic only
* Supports signed integers by default using two-complement arithmetic rules on unsigned operations
* Allow to mix any operation with lua numbers, promoting to lua floats where needed

For more information check the project page:
https://github.com/edubart/lua-bint/

And it's documentation:
https://edubart.github.io/lua-bint/

It is available in luarocks.

--
Eduardo Bart