Arbitrary (Precision) Integers (AINT)

Single-header C99 library for large integers.

While performance is likely not as good as compared to a library like GMP, it will (hopefully) give correct results.

Usage

Just simply include aint.h into your project and in one of its files, define AINT_IMPLEMENTATION

The basic API is given below. Make sure to read the function descriptions as well in aint.h

// create a new aint
aint * aint_new(uint32_t precision, int32_t init);
aint * aint_str_new(char * str);

// free an aint or multiple aint's
void aint_free(aint * a);
void aint_free_list(int count, ...);

// arithmetic
void aint_add(aint * result, const aint * a, const aint * b);
void aint_sub(aint * result, const aint * a, const aint * b);
void aint_mul(aint * result, const aint * a, const aint * b);
void aint_div(aint * result, const aint * a, const aint * b);
void aint_mod(aint * result, const aint * a, const aint * b);
void aint_neg(aint * result, const aint * a); 
void aint_abs(aint * result, const aint * a);
void aint_pow(aint * result, const aint * a, uint32_t k);
void aint_sqrt(aint * result, const aint * a);
void aint_kroot(aint * result, const aint * a, uint32_t k); // work in progress 

// comparision
int aint_compare(const aint * a, const aint * b); // like <=> operator in c++
bool aint_is_greater_than(const aint * a, const aint * b);
bool aint_is_less_than(const aint * a, const aint * b);
bool aint_is_equal(const aint * a, const aint * b);
// the 4 functions above have an abs variant as well
bool aint_is_pos(const aint * a);
bool aint_is_neg(const aint * a);

// print
void aint_fprint(const aint * a, FILE * fp);
void aint_print(const aint * a); // print to stdout

You can find more functions in aint.h, including useful precidates and helper functions.

Examples

Here is a basic example:

#define AINT_IMPLEMENTATION
#include "../aint.h"

int main()
{
    aint * a = aint_new(4, 1000);
    aint * b = aint_new(4, 2000);
    aint * c = aint_new(4, 0);
    aint_add(c, a, b); // c = a + b
    aint_print(c); // 3000
    aint_free_list(3, a, b, c); 
    // or use aint_free for each aint
}

And here is an example of multiplication and the use of aint_str_new:

#define AINT_IMPLEMENTATION
#include "../aint.h"

int main()
{
    aint * a = aint_str_new("3322255777");
    aint * b = aint_str_new("3323333323");
    aint * c = aint_new(10, 0);
    aint_mul(c, a, b); // c = a * b;
    aint_print(c); // 11040963331233356971
    aint_free_list(3, a, b, c);  
}

And here is an example of creating a file with the fibonacci numbers up to the 2000th fibonacci number:

#define AINT_IMPLEMENTATION
#include "../aint.h"

int main()
{
    FILE * fib_file = fopen("fib.txt", "w");
    aint * a = aint_new(256, 0);
    aint * n = aint_new(256, 1);
    aint * temp = aint_new(256, 0);
    fprintf(fib_file, "0 0\n1 1\n");
    for (int i = 2 ; i <= 2000; i++)
    {
        aint_copy(n, temp); 
        aint_add(n, n, a); 
        aint_copy(temp, a);  
        fprintf(fib_file, "%d ", i);
        aint_fprint(n, fib_file); 
        fprintf(fib_file, "\n");
    }
    fclose(fib_file);
    aint_free_list(3, a, n, temp);
}

More examples should be found in the examples folder. make can be used to compile them all.

Implementation details

We employ the sign-magnitude representation. A positive integer in this library is represented as $a=\sum_{i = 0}^{n-1}a_i\beta^i = a_0\beta^0 + a_1\beta^1 + \cdots + a_{n-1}\beta^{n-1}$, where $n$ is the chosen precision, $a_i$ is a coefficient where $0 \leq a_i \leq \beta-1$ and $\beta$ is the base (chosen to be 256).

Future Plans and Alternative Solutions

I'm thinking of adding a few new functions, specifically aint_set_precision, aint_pow, aint_sqrt, and aint_root. Along side this, I think we should try to lower the ammount of allocations that are happening.

Also something that might happen is a structure change of the aint. It is only after finalizing most the lib that I realized to be able to support automatic resizing, we require a pointer to the current aint *.

For now, the user must consider the precision of the numbers they wish to work with and size them accordingly (this will hopefully not be for long).

To caculate the required precision $n$ to store a base 10 number $b$, you must solve for $log(b)=log(\beta^n)$ (trivially $n=\lceil \log(b)/\log(\beta)\rceil$).

Since $\log(b)$ is already extremely tedious to calculate for large numbers, one trick would be to find an integer $m$ such that $b \leq 10^m$, so $n=\lceil m/\log(\beta) \rceil$. Note that $\log$ means $\log_{10}$ here. You can use other bases as well.

References

I relied heavily on the book Modern Computer Arithmetic written by Richard P. Brent and Paul Zimmermann. It contains many algorithms from basic to more advanced (i.e. lowering the time complexity) for each operation and is well organized and explained. If it matters, I used version 0.5.9 of the book.

I also used an algorithm for exponentiation from the book Handbook of Applied Cryptography written by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Chapter 14 infact covers many of the basic arithmetic algorithms found in Modern Computer Arithmetic but perhaps are a bit outdated (1996?).

License

This is free and unencumbered software released into the public domain.

Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.

In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

For more information, please refer to <https://unlicense.org/>