Big integer arithmetic library

[cosh]

  Hi, there
I wrote a library for big integer arithmetic here: https://github.com/coshcage/pbint
It's called pbint means portable big integer library.
The difference between pbint and gnu gmp is that you don't need to control memory manually in pbint, pbint combined heap memory management functions to arithmetic functions together. pbint is smaller and faster. If you are interested in high precision calculation and large integer arithmetic, pbint is suitable for you.

I also tested and compiled pbint with Pelles C compiler. Before compiling pbint with Pelles C you need to alter pbint according to the following instructions:
Delete line 568 register qualifier in pbk.c.
Delete line 621 register qualifier in pbk.c. But don't delete variable declaration clause.

Testing shows to calculate factorial 2000 on an Intel Core i9 9 Gen microprocessor only needs 0.01 seconds.
Here's the code that I used for testing:

Code: [Select]

#include <stdio.h>
#include <Windows.h>
#include "pbk.h"
#include "pbm.h"

int main()
{
P_BINT pc;
P_BNUM p;
LARGE_INTEGER la, lb, lc;


pc = pbkCreateBint(0);
p = pbkCreateBnum(10);

QueryPerformanceFrequency(&lc);
QueryPerformanceCounter(&la);

pbmUbFactorial(pc, 2000); // 2000!

QueryPerformanceCounter(&lb);
printf("%lf\n", (double)(lb.QuadPart - la.QuadPart) / (double)lc.QuadPart);

pbkBintToDecimalBnum(p, pc);

pbkPrintBnum(p);

return 0;
}

Kind regards,
Cosh.

[frankie]

 

[WiiLF23]

Nice work! Very appreciated.

Cheers!

[TimoVJL]

pbint.def

Code: [Select]

LIBRARY pbint.dll
EXPORTS
pbkInitBint
pbkReallocBint
pbkFreeBint
pbkCreateBint
pbkDeleteBint
pbkMoveBint
pbkCopyBint
pbkIbToBint
pbkBintToIb
pbkCompareBint
pbkAddBint
pbkSubtractBint
pbkLeftShiftBint
pbkRightShiftBint
pbkMultiplyBint
pbkDivideBint
pbkInitBnum
pbkReallocBnum
pbkFreeBnum
pbkCreateBnum
pbkDeleteBnum
pbkMoveBnum
pbkIbToBnum
pbkDecimalSzToBnum
pbkPrintBnum
pbkBintToDecimalBnum
pbkDecimalBnumToBint
pbmBintPower
pbmUbFactorial
pbmBintSquareRoot
pbmBintGreatestCommonDivisor
pbxLoadBint
pbxSaveBint

[jack]

hello cosh 
I ran your test, if compiled with -O2 the time was about .0043, if compiled with -O3 .0058, it's not uncommon that -O3 is a bit slower than -O2
but I don't like the license at all, LGPL for a library is ok but not GPL, although I much prefer the MIT type of license

[jack]

hello cosh
if you implement a multiply BigInt by 32-bit integer then your factorial would be about 3 times faster

[cosh]

pbint.def

Code: [Select]

LIBRARY pbint.dll
EXPORTS
pbkInitBint
pbkReallocBint
pbkFreeBint
pbkCreateBint
pbkDeleteBint
pbkMoveBint
pbkCopyBint
pbkIbToBint
pbkBintToIb
pbkCompareBint
pbkAddBint
pbkSubtractBint
pbkLeftShiftBint
pbkRightShiftBint
pbkMultiplyBint
pbkDivideBint
pbkInitBnum
pbkReallocBnum
pbkFreeBnum
pbkCreateBnum
pbkDeleteBnum
pbkMoveBnum
pbkIbToBnum
pbkDecimalSzToBnum
pbkPrintBnum
pbkBintToDecimalBnum
pbkDecimalBnumToBint
pbmBintPower
pbmUbFactorial
pbmBintSquareRoot
pbmBintGreatestCommonDivisor
pbxLoadBint
pbxSaveBint

Hi, TimoVJL
Thanks for your def file, it is useful to export functions for a dll.

[cosh]

hello cosh
if you implement a multiply BigInt by 32-bit integer then your factorial would be about 3 times faster

Hello, jack
In the file pbk.h there are some macros to define block integers:
/* Predefined data type. */
typedef int                _ib;      /* Integer block. */
typedef unsigned int       _ub;      /* Unsigned integer block. */
typedef long long          _idb;     /* Integer double block. */
typedef unsigned long long _udb;     /* Unsigned integer double block. */

On a 64-bit machine, int usually be a 32bits integer.

[cosh]

hello cosh 
I ran your test, if compiled with -O2 the time was about .0043, if compiled with -O3 .0058, it's not uncommon that -O3 is a bit slower than -O2
but I don't like the license at all, LGPL for a library is ok but not GPL, although I much prefer the MIT type of license

Yes, it is unusually that -O3 optimization shows a poorer speed than -O2.
I will consider altering license after your notice in the future. Thank you. Now, I think GPLv3 is better for this library.

[jack]

cosh
I think that you misunderstood me about "multiply BigInt by 32-bit integer", anyway, here's a very simple factorial function to illustrate my point

[cosh]

cosh
I think that you misunderstood me about "multiply BigInt by 32-bit integer", anyway, here's a very simple factorial function to illustrate my point

Hello, jack
It's my mistake. I misunderstood you. However, I think multiply BigInt by 32-bit integer won't accelerate this(pbint) algorithm's speed. Cuz, theoretically, pbkMultiplyBint needs two operations: 1st is add, 2nd is left shift. For this method, the complexity of multiplying by a bigint is similar to multiplying by a 32-bit int. I tested your package(Thank you for providing it.), And 2000! by using pbkMultiplyBint only needs 0.001s but converting from base 2 Bint to base 10 Bnum needs more time. Your package performs also well, that is 0.002s.

Thank you for your reply, jack.
John C. Cage.

[cosh]

hello cosh
if you implement a multiply BigInt by 32-bit integer then your factorial would be about 3 times faster

And this is the code to do factorial:

Code: [Select]

_boolean pbmUbFactorial(P_BINT r, _ub n)
{
BINT R = { 0 }, N = { 0 };

pbkInitBint(&R, 0);
pbkInitBint(&N, 0);

SETFLAG(r, 1);
r->data[0] = 1;

SETFLAG(&N, 1);

while (n - 1)
{
if (!pbkMoveBint(&R, r))
{
pbkFreeBint(&R);
pbkFreeBint(&N);
return FALSE;
}
N.data[0] = n; // Please notice here, it is directly insert a 32-bit integer to bigint.
if (!pbkMultiplyBint(r, &N, &R))
{
pbkFreeBint(&R);
pbkFreeBint(&N);
return FALSE;
}
--n;
}

pbkFreeBint(&R);
pbkFreeBint(&N);
return TRUE;
}


[cosh]

Hi, fellows
I finished a big integer calculator.
You guys may download it here: https://github.com/coshcage/pbint/blob/main/Samples/05-24-24_13-09.c
The calculator supports +-*/^(power) and brackets.
I also paste this code here:

Code: [Select]

#include <stdio.h>
#include <string.h>
#include "pbm.h"
#define MAXLEN 100

P_BINT CatchFirstNumber();
P_BINT CalcBrackets();
P_BINT CalcAdditional();
P_BINT CalcAdvanced();
P_BINT CalcPrimary();

char * expr;

P_BINT CalcPrimary()
{
P_BINT x, y = NULL, r;
int c;
r = pbkCreateBint(0);
x = CalcAdvanced(expr);
c = expr[0];
while ('+' == c || '-' == c)
{
++expr;
y = CalcAdvanced(expr);
if ('+' == c)
{
pbkAddBint(r, x, y);
pbkMoveBint(x, r);
}
else if ('-' == c)
{
pbkSubtractBint(r, x, y);
pbkMoveBint(x, r);
}
c = expr[0];
}
if (expr[0] == ')')
++expr;
pbkDeleteBint(r);
if (NULL != y)
pbkDeleteBint(y);
return x;
}

P_BINT CalcAdvanced()
{
P_BINT x, y = NULL, r, k;
int c;
r = pbkCreateBint(0);
k = pbkCreateBint(0);
x = CalcAdditional(expr);
c = expr[0];
while ('*' == c || '/' == c)
{
++expr;
y = CalcAdvanced(expr);
if ('*' == c)
{
pbkMultiplyBint(r, x, y);
pbkMoveBint(x, r);
}
else if (c == '/')
{
pbkDivideBint(r, k, x, y);
pbkMoveBint(x, r);
}
c = expr[0];
}
pbkDeleteBint(r);
pbkDeleteBint(k);
if (NULL != y)
pbkDeleteBint(y);
return x;
}

P_BINT CalcAdditional()
{
P_BINT x, y, r;
r = pbkCreateBint(0);
x = CalcBrackets(expr);
if ('^' == expr[0])
{
_ub n;
++expr;
y = CalcAdditional(expr);
n = GETABS(pbkBintToIb(y));
pbmBintPower(r, x, n);
pbkDeleteBint(y);
pbkDeleteBint(x);
return r;
}
return x;
}

P_BINT CalcBrackets()
{
if ('(' == expr[0])
{
++expr;
return CalcPrimary(expr);
}
else
{
return CatchFirstNumber(expr);
}
}

P_BINT CatchFirstNumber()
{
size_t i;
P_BINT r;
P_BNUM t;
char szT[2] = { 0 };
char szTar[MAXLEN] = { 0 };
r = pbkCreateBint(0);
t = pbkCreateBnum(10);
for (i = 0; expr[0] != 0 && i < MAXLEN; ++expr, ++i)
{
if (expr[0] >= '0' && expr[0] <= '9')
{
szT[0] = expr[0];
strcat(szTar, szT);
}
else
{
pbkDecimalSzToBnum(t, szTar);
pbkDecimalBnumToBint(r, t);
pbkDeleteBnum(t);
return r;
}
}
pbkDecimalSzToBnum(t, szTar);
pbkDecimalBnumToBint(r, t);
pbkDeleteBnum(t);
return r;
}

int main(int argc, char ** argv)
{
char szExpr[MAXLEN] = { 0 };
while (EOF != scanf("%s", szExpr))
{
P_BINT r;
P_BNUM t;
expr = szExpr;
t = pbkCreateBnum(10);
r = CalcPrimary();
pbkBintToDecimalBnum(t, r);
printf("= ");
pbkPrintBnum(t);
pbkDeleteBnum(t);
pbkDeleteBint(r);
printf("\n");
}
}

Does anyone want to develop this library with me together?

[TimoVJL]

to make def file from map file, copy relevant part of it and use a tiny helper program like this:

Code: [Select]

#include <stdio.h>

int __cdecl main(void)
{
FILE *fi = NULL;
char s[100];
if (fi = fopen("pbint.lst", "r")) {
while (fgets(s, 100, fi)) {
char *p = s+21;
while (*p != ' ') p++;
*p++ = 10;
*p = 0;
printf(s+21);
}
fclose(fi);
}
return 0;
}