Recent

Author Topic: Large/Big Integer Library in pure Pascal  (Read 9303 times)

ad1mt

  • Full Member
  • ***
  • Posts: 199
    • Mark Taylor's Home Page
Large/Big Integer Library in pure Pascal
« on: July 17, 2022, 06:46:08 pm »
I'm working on a Large/Big Integer Library, written entirely in Pascal.
I started this project after failing to find an existing library that suited my requirements:
- must be written in Pascal, no assembly, no C, no C++
- must have an OO interface to make code conversion easy/transparent.
- must compile on all CPUs
- must compile on all word sizes... 32bit and 64bit
- must be reasonably fast/efficient, so implementations that use strings to hold integers are too slow for me.
I'm looking for people who are interested in testing and/or commenting and/or contributing to the library.
I intend to contribute the library to the FPC community, with no restrictions/limitations.
« Last Edit: July 18, 2022, 06:19:50 pm by ad1mt »

af0815

  • Hero Member
  • *****
  • Posts: 1291
Re: Large/Big Integer Library in pure Pascal
« Reply #1 on: July 17, 2022, 06:50:30 pm »
Reinvent the wheel?

If you search there are some. Eg. Gnurz.
regards
Andreas

srvaldez

  • New Member
  • *
  • Posts: 36
Re: Large/Big Integer Library in pure Pascal
« Reply #2 on: July 17, 2022, 06:52:28 pm »
I am interested in testing and giving feedback

Kays

  • Hero Member
  • *****
  • Posts: 575
  • Whasup!?
    • KaiBurghardt.de
Re: Large/Big Integer Library in pure Pascal
« Reply #3 on: July 17, 2022, 07:31:57 pm »
[…] written in pure Pascal. […]
What is “pure” Pascal⁇ You know that already the notion of units is an UCSD Pascal extension to Pascal, right?
Yours Sincerely
Kai Burghardt

ad1mt

  • Full Member
  • ***
  • Posts: 199
    • Mark Taylor's Home Page
Re: Large/Big Integer Library in pure Pascal
« Reply #4 on: July 17, 2022, 07:46:07 pm »
RE "What is “pure” Pascal⁇"
I've edited my post to clarify... saying "written entirely in Pascal" would be clearer.

RE Gnurz...
Thanks for the suggestion, I was not aware of this one. Unfortunately, it's mostly written in asembly.
« Last Edit: July 17, 2022, 08:15:37 pm by ad1mt »

Thaddy

  • Hero Member
  • *****
  • Posts: 14373
  • Sensorship about opinions does not belong here.
Re: Large/Big Integer Library in pure Pascal
« Reply #5 on: July 17, 2022, 09:34:53 pm »
BigInt sources are already in the standard distribution for many years......
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.

af0815

  • Hero Member
  • *****
  • Posts: 1291
Re: Large/Big Integer Library in pure Pascal
« Reply #6 on: July 17, 2022, 10:01:08 pm »
RE Gnurz...
Thanks for the suggestion, I was not aware of this one. Unfortunately, it's mostly written in asembly.
as I know, you can remove the assembler (only for cpu86) and work pascal pure. only some parts were written dual. to speed up some routines have implementation in asm beside the pascal implementation. So its written in pure pascal with the try on one platform (cpu86) to be in assembler. but this can revoked.
« Last Edit: July 17, 2022, 10:07:11 pm by af0815 »
regards
Andreas

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 1313
Re: Large/Big Integer Library in pure Pascal
« Reply #7 on: July 18, 2022, 09:36:24 am »
BigInt sources are already in the standard distribution for many years......

Where? I tend to search for a working and (reasonably) fast one every few years, and I never found one that works in FPC (except the bindings for gmp).

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11453
  • FPC developer.
Re: Large/Big Integer Library in pure Pascal
« Reply #8 on: July 18, 2022, 10:27:26 am »
Reinvent the wheel?

If you search there are some. Eg. Gnurz.

Unsuitable license; GPL2/3. But yeah, it is easier to put a few pascal versions besides the assembler ones than to start over.

srvaldez

  • New Member
  • *
  • Posts: 36
Re: Large/Big Integer Library in pure Pascal
« Reply #9 on: July 18, 2022, 03:42:06 pm »
 TForge had a bigint package, the repository is no longer available but there's a snapshot in the wayback machine https://web.archive.org/web/20200622073152/https://bitbucket.org/sergworks/tforge/downloads/ the license is very liberal

BobDog

  • Sr. Member
  • ****
  • Posts: 394
Re: Large/Big Integer Library in pure Pascal
« Reply #10 on: July 18, 2022, 05:44:24 pm »

Into the abyss:
Code: Pascal  [Select][+][-]
  1.  
  2.  
  3. uses
  4. strutils;
  5.  
  6.      
  7. function qmult(aa:ansistring;bb:ansistring):ansistring;
  8. type
  9.           AB = array of byte;
  10. const init:boolean=false;
  11.       _mod:AB=nil;
  12.       _div:AB=nil;
  13.      var
  14.      z,i,j,la,lb,tmpi:longint;
  15.      tmps,ans:ansistring;
  16.      cc:ansistring='';
  17.      n,carry,ai:smallint;
  18.      a,b,c:pchar;
  19.      
  20.      begin
  21.      if (init=false) then
  22.      setlength(_mod,100);
  23.      setlength(_div,100);
  24.       begin {create lookup  tables once}
  25.      for z:=0 to 99 do
  26.      begin
  27.      _mod[z]:= (z mod 10) +48;
  28.      _div[z]:=  z div 10;
  29.       end;  {created lookup tables}
  30.       init:=true;
  31.       end;
  32.      
  33.       la:=length(aa);lb:=length(bb);
  34.       If Lb>La Then
  35.       begin
  36.       tmpi:=la;tmps:=aa;
  37.       la:=lb;aa:=bb;
  38.       lb:=tmpi;bb:=tmps;
  39.       end;
  40.       Setlength(cc,la+lb);
  41.        FillChar(cc[1],la+lb,#48);
  42.        a:=@aa[1];b:=@bb[1];c:=@cc[1];
  43.        for i:=la-1 downto 0 do
  44.       begin
  45.          carry:=0;ai:=ord(a[i])-48 ;
  46.       for j:= lb-1 downto 0 do
  47.       begin
  48.         n :=ai*(ord(b[j])-48)+(ord(c[i+j+1])-48)+carry;
  49.         carry :=_Div[n];ord(c[i+j+1]):=_Mod[n];
  50.       end;
  51.        ord(c[i]):=ord(c[i])+carry ;
  52.       end;
  53.       ans:=c;
  54.       if c[1]='0' then ans:=copy(c,2,length(c)-1) ;
  55.       exit(ans);
  56.       end;
  57.      
  58.      function pow2(n:integer):ansistring;
  59.      var
  60.      i:integer;
  61.     q,ans:ansistring;
  62.     begin
  63.     q:='2';
  64.     for i:=1 to n-1 do q:=qmult('2',q);
  65.     ans:=q;
  66.      if q[1]='0' then ans:=copy(q,2,length(q)-1) ;
  67.     exit(ans);
  68.     end;
  69.      
  70.       procedure decrement(var s:ansistring);
  71.       var
  72.       counts,ls:longint;
  73.       b,c,ans:ansistring;
  74.       begin
  75.       c:='';
  76.       ls:=length(s);
  77.       counts:=0;
  78.       ans:='';b:='';
  79.       repeat
  80.       while ord(s[ls-counts-1+1])=48 do
  81.       begin
  82.       counts:=counts+1;
  83.       end;
  84.        if ord(s[ls-counts-1+1])<>48 Then
  85.       begin
  86.       ans:=leftstr(s,ls-counts-1);
  87.       Str(ord(s[ls-counts-1+1])-49,b);
  88.       ans:=ans+b;
  89.       setlength(c,counts);
  90.       FillChar(c[1],counts,#57);
  91.       ans:=ans+c;
  92.       s:=ans;
  93.       exit;
  94.       end;
  95.       until (true);
  96.       end;
  97.      
  98.      
  99. var
  100. i,L:integer;
  101. q,space,gap:ansistring;
  102.  
  103.  
  104. begin
  105.  
  106. for i:=1 to 300 do
  107.  begin
  108.  gap:='';
  109.  q:=pow2(i);
  110.  decrement(q);
  111.  str(i,space);
  112.  L:=length(space);
  113.  L:=7-L;
  114.  setlength(gap,L);
  115.  FillChar(gap[1],L,#32);
  116.   write('2^',i,'-1',gap,q,'  ');
  117.  
  118.   case q of
  119.   '127':write('shortint');
  120.   '255':write('byte or uint8');
  121.   '32767':write('smallint');
  122.   '65535':write('word');
  123.   '2147483647':write('longint');
  124.   '4294967295':write('longword or cardinal');
  125.   '9223372036854775807':write('int64');
  126.   '18446744073709551615':write('qword or uint64 (End of numerical)');
  127.   '340282366920938463463374607431768211455':write('some day');
  128.   end;
  129.  
  130.  writeln;
  131.  
  132.  
  133.  end;
  134.  writeln('Press enter to end . . .');
  135.  readln;
  136.  
  137. end.
  138.  
  139.  

Jurassic Pork

  • Hero Member
  • *****
  • Posts: 1228
Re: Large/Big Integer Library in pure Pascal
« Reply #11 on: July 19, 2022, 01:40:26 am »
hello,
you can also try  the mparith library.

Quote
This archive contains Pascal source for multi precision integer, rational,
real and complex floating point arithmetic and functions. The basic routines
can be compiled with the usual Pascal versions that allow const parameters
(tested with BP 7.0, VP 2.1, FPC 1.0/2.0/2.2/2.4/2.6/3x, and Delphi versions
2..7/9-10/12/17/18/25/26).

A separate introduction can be found in the mp_intro.txt; Windows and
Borland Pascal help files are included.
For a complete list with brief descriptions see the mp_intro function list.

There are test programs that verify the functions and the compilation. Demo
programs are included for pi calculation, expression parsing and evaluation
(including two interactive multi precision calculators), factorization based
on Pollard's rho and p-1, Williams's p+1, and ECM methods, RSA attacks, etc.

My Pascal routines are based on many public resources (source code
libraries, books, articles), links are given in the mp_intro references.

W.Ehrhardt, Nov. 2018

Quote
mparith : calculate pi with 200 digits
314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038197

Friendly, J.P
« Last Edit: July 19, 2022, 01:44:47 am by Jurassic Pork »
Jurassic computer : Sinclair ZX81 - Zilog Z80A à 3,25 MHz - RAM 1 Ko - ROM 8 Ko

srvaldez

  • New Member
  • *
  • Posts: 36
Re: Large/Big Integer Library in pure Pascal
« Reply #12 on: July 19, 2022, 02:37:19 am »
yes indeed, mparith is by far the best option and with very permissible license

Thaddy

  • Hero Member
  • *****
  • Posts: 14373
  • Sensorship about opinions does not belong here.
Re: Large/Big Integer Library in pure Pascal
« Reply #13 on: July 19, 2022, 10:24:42 am »
This one by the late Rudy Velthuis can be made to work for freepascal with a little effort:
https://github.com/rvelthuis/DelphiBigNumbers
I already did that, but I can't find it. It took me half an hour or so, if I remember correctly.
(Mostly define extensions and removal of delphi scoped units like system.math -> math. The code in itself is fully compatible and in purepascal mode also works on Unix/Linux.)

Good to see that code is still preserved even if he has passed away some time ago.
« Last Edit: July 19, 2022, 10:26:54 am by Thaddy »
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 1313
Re: Large/Big Integer Library in pure Pascal
« Reply #14 on: July 19, 2022, 04:13:52 pm »
This one by the late Rudy Velthuis can be made to work for freepascal with a little effort:
https://github.com/rvelthuis/DelphiBigNumbers
I already did that, but I can't find it. It took me half an hour or so, if I remember correctly.
(Mostly define extensions and removal of delphi scoped units like system.math -> math. The code in itself is fully compatible and in purepascal mode also works on Unix/Linux.)

Good to see that code is still preserved even if he has passed away some time ago.

Yes, I did that as well, but it wasn't that easy and I only got it partly working. Out of the box, it totally doesn't compile.

 

TinyPortal © 2005-2018