NO

Author Topic: Big integer arithmetic library  (Read 7375 times)

Offline cosh

  • Member
  • *
  • Posts: 33
Big integer arithmetic library
« on: May 20, 2024, 07:14:08 PM »
 :) 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.
« Last Edit: May 21, 2024, 08:46:45 AM by cosh »

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 2114
Re: Big integer arithmetic library
« Reply #1 on: May 20, 2024, 10:58:59 PM »
 :)
"It is better to be hated for what you are than to be loved for what you are not." - Andre Gide

Offline WiiLF23

  • Member
  • *
  • Posts: 89
Re: Big integer arithmetic library
« Reply #2 on: May 22, 2024, 03:33:01 AM »
Nice work! Very appreciated.

Cheers!

Offline TimoVJL

  • Global Moderator
  • Member
  • *****
  • Posts: 2131
Re: Big integer arithmetic library
« Reply #3 on: May 22, 2024, 09:09:44 AM »
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
May the source be with you

Offline jack

  • Member
  • *
  • Posts: 66
Re: Big integer arithmetic library
« Reply #4 on: May 22, 2024, 02:44:35 PM »
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

Offline jack

  • Member
  • *
  • Posts: 66
Re: Big integer arithmetic library
« Reply #5 on: May 22, 2024, 04:53:55 PM »
hello cosh
if you implement a multiply BigInt by 32-bit integer then your factorial would be about 3 times faster

Offline cosh

  • Member
  • *
  • Posts: 33
Re: Big integer arithmetic library
« Reply #6 on: May 23, 2024, 01:19:37 PM »
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.

Offline cosh

  • Member
  • *
  • Posts: 33
Re: Big integer arithmetic library
« Reply #7 on: May 23, 2024, 01:22:07 PM »
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.

Offline cosh

  • Member
  • *
  • Posts: 33
Re: Big integer arithmetic library
« Reply #8 on: May 23, 2024, 01:27:04 PM »
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.

Offline jack

  • Member
  • *
  • Posts: 66
Re: Big integer arithmetic library
« Reply #9 on: May 23, 2024, 04:35:19 PM »
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

Offline cosh

  • Member
  • *
  • Posts: 33
Re: Big integer arithmetic library
« Reply #10 on: May 24, 2024, 02:55:05 PM »
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.

Offline cosh

  • Member
  • *
  • Posts: 33
Re: Big integer arithmetic library
« Reply #11 on: May 24, 2024, 08:15:53 PM »
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;
}

Offline cosh

  • Member
  • *
  • Posts: 33
Re: Big integer arithmetic library
« Reply #12 on: May 24, 2024, 10:21:16 PM »
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?
« Last Edit: May 25, 2024, 10:31:09 AM by cosh »

Offline TimoVJL

  • Global Moderator
  • Member
  • *****
  • Posts: 2131
Re: Big integer arithmetic library
« Reply #13 on: May 26, 2024, 12:03:30 PM »
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;
}
May the source be with you