Lazarus

Free Pascal => General => Topic started by: eli on October 26, 2021, 12:01:51 pm

Title: n-bit integer, larger than Int64.
Post by: eli on October 26, 2021, 12:01:51 pm
 May I use it in Free Pascal?
Title: Re: n-bit integer, larger than Int64.
Post by: eli on October 26, 2021, 12:38:06 pm
I'm glad to read your positive response. I was almost sure my question had no positive answer.

Anyway, I don't know how the TBits class can be useful in building very long integers, so let's be more specific:

Instead of writing:

var x:int64

What should I write, for the variable x to run over all possible integers whose absolute value is not bigger than: 2 to the n-th power (minus 1), n being a constant?
Title: Re: n-bit integer, larger than Int64.
Post by: Kays on October 26, 2021, 01:50:25 pm
May I use it in Free Pascal?
Pascal defines that all arithmetic operations (http://www.pascal-central.com/iso7185.html#6.7.2.2%20Arithmetic%20operators) in the range -maxInt..maxInt work correctly. Beyond that there is no assurance of correctness.

You will need to use an arbitrary precision arithmetic library, such as GMP (https://wiki.freepascal.org/gmp). This library will (effectively/in theory) allow you to have at most 237 wide integers.
[…] What should I write, for the variable x to run over all possible integers whose absolute value is not bigger than: 2 to the n-th power (minus 1), n being a constant?
The drawback of that kind of approach is that such a simple task as yours becomes quite complicated:
Code: Pascal  [Select][+][-]
  1. program nbitIntegerDemo(input, output, stdErr);
  2. { for `try … finally … end` support }
  3. {$mode objFPC}
  4. uses
  5.         GMP;
  6. const
  7.         n = 666;
  8. var
  9.         { cave: these are pointer variables }
  10.         x, limit: MPZ_t;
  11. begin
  12.         { allocate memory and initialize with value 2 }
  13.         MPZ_init_set_SI(limit, 2);
  14.         try
  15.                 { limit := 2 pow n }
  16.                 MPZ_pow_UI(limit, limit, n);
  17.                
  18.                 { allocate memory and copy value (x := limit) }
  19.                 MPZ_init_set(x, limit);
  20.                 try
  21.                         { while abs(x) <= abs(limit) do }
  22.                         while MPZ_cmpAbs(x, limit) <= 0 do
  23.                         begin
  24.                                 { do your magic stuff here }
  25.                                
  26.                                 { x := x - 1 }
  27.                                 MPZ_sub_UI(x, x, 1);
  28.                         end;
  29.                 finally
  30.                         { release memory }
  31.                         MPZ_clear(x);
  32.                 end;
  33.         finally
  34.                 MPZ_clear(limit);
  35.         end;
  36. end.
Maybe you can improve or alter your algorithm so it doesn’t exceed the bounds of -maxInt..maxInt? Do you really need to iterate over all integers in (−2n, 2n)? Also (possibly to the detriment of precision) you can use ln/exp and logarithmic rules (https://en.wikipedia.org/wiki/List_of_logarithmic_identities#Using_simpler_operations).
Title: Re: n-bit integer, larger than Int64.
Post by: Warfley on October 26, 2021, 01:59:13 pm
GMP is much easier with interfaces:
Code: Pascal  [Select][+][-]
  1.     program nbitIntegerDemo(input, output, stdErr);
  2. {$mode objFPC}
  3. uses
  4.   GMP;
  5. const
  6.   n = 666;
  7. var
  8.   x, limit: MPInteger;
  9. begin
  10.   limit := 2;
  11.   { limit := limit pow n }
  12.   limit := limit ** n;
  13.   { allocate memory and copy value (x := limit) }
  14.   x := limit
  15.   try
  16.     { while abs(x) <= abs(limit) do }
  17.     while z_abs(x) <= z_abs(limit) do // for zhe MPXXX interfaces the mpx_func becomes x_func so mpz_abs becomes z_abs
  18.     begin
  19.       { do your magic stuff here }
  20.       { x := x - 1 }
  21.       x -= 1;
  22.     end;
  23. end.

So I would say that actually it doesn't really get that complicated, but it gets slow
Title: Re: n-bit integer, larger than Int64.
Post by: Kays on October 26, 2021, 02:08:26 pm
GMP is much easier with interfaces:
Where’s that documented? That’s indeed less cluttered. And it’s a blessing if I don’t have to mind the proper …_clear.

Code: Pascal  [Select][+][-]
  1.     while z_abs(x) <= z_abs(limit) do // […]
As handy as it is, this won’t make use of MPZ_cmpAbs though, right? It’ll create two temporary copies, take the absolute value of each of them, and then compare their values. And finally release memory. This isn’t very efficient, you know.

So I would say that actually it doesn't really get that complicated, but it gets slow
Yeah, I think the slowdown is exacerbated if you are using GMP via those interfaces. My code did a plain
Code: ASM  [Select][+][-]
  1.         movq    $U_$P$NBITINTEGERDEMO_$$_LIMIT,%rsi
  2.         movq    $U_$P$NBITINTEGERDEMO_$$_X,%rdi
  3.         call    __gmpz_cmpabs
  4.         cmpl    $0,%eax
PS: The word “complicated” also referred to the fact that you’ll need to learn a new library. I spent a few minutes on browsing the documentation, too.
Title: Re: n-bit integer, larger than Int64.
Post by: Warfley on October 26, 2021, 02:55:57 pm
It's kind of documented in the "Extensions bindings & types" section of the wiki article, but the operator section is completely missing.
Not really the best documentation.

With the cmpAbs that is true, I tried to write the code as "natural" as possible, but you can use every gmp function with the interfaces, so you could use z_cmpAbs with the interfaces.
But with respect to performance there is actually one larger problem that is when using operators. FPC does not support inplace operator overloading (e.g. x -= y is the same as x := x - y) which means that every such operation creates a temporary object.
Even more, each interface also adds it's own overhead, so when you create a GMP object you only need one allocation for the GMP memory, with the interfaces you need 2, one for the interfaced object and one for the gmp object.
This of course aren't that big impacts on their own, but in inner loops this can add up easiely

I would always recommend when using GMP, start of with the interfaces and write as clearly as possible, if you run into performance issues optimize via in-place operations and if even that is not enough, maybe even ditch the interfaces all together.

PS: the assignment operators work btw in both ways:
Code: Pascal  [Select][+][-]
  1. var x: MPInteger;
  2.   s: String;
  3. begin
  4.   x := '123456789012345678901234567890';
  5.   s := x;
  6.   WriteLn(s); // 123456789012345678901234567890
  7. end.
Title: Re: n-bit integer, larger than Int64.
Post by: AlexTP on October 26, 2021, 03:57:33 pm
Quote
Pascal defines that all arithmetic operations in the range -maxInt..maxInt work correctly. Beyond that there is no assurance of correctness.
FPC must work correctly with Int64 vars too, no?
Title: Re: n-bit integer, larger than Int64.
Post by: eli on October 26, 2021, 04:24:27 pm
.
Title: Re: n-bit integer, larger than Int64.
Post by: Kays on October 26, 2021, 04:26:57 pm
It's kind of documented in the "Extensions bindings & types" section of the wiki article, but the operator section is completely missing.
Not really the best documentation.
Indeed. And I always advocate for the security principle: “Don’t use functionality that is not documented.” And if it’s not documented, it might be gone in the next release without further notice.
Quote
With the cmpAbs that is true, I tried to write the code as "natural" as possible, but you can use every gmp function with the interfaces, so you could use z_cmpAbs with the interfaces. […]
Alright, I tried it. That’s neat.
Even more, each interface also adds it's own overhead, so when you create a GMP object you only need one allocation for the GMP memory, with the interfaces you need 2, one for the interfaced object and one for the gmp object.
I daresay that’s negligible though if you’re doing calculations in the zillions.

Quote
Pascal defines that all arithmetic operations in the range -maxInt..maxInt work correctly. Beyond that there is no assurance of correctness.
FPC must work correctly with Int64 vars too, no?
It must at least work correctly in the range -maxInt..maxInt. Consider the following program:
Code: Pascal  [Select][+][-]
  1. program foo(input, output, stdErr);
  2. var
  3.         x: ALUSInt;
  4. begin
  5.         x := low(x); { this is _not_ -maxInt }
  6.         writeLn(x:20);
  7.        
  8.         x := abs(x);
  9.         writeLn(x:20)
  10. end.
Neither {$overflowChecks on} (https://www.freepascal.org/docs-html/current/prog/progsu64.html) nor {$rangeChecks on} (https://www.freepascal.org/docs-html/current/prog/progsu65.html) will produce an error, because arithmetic operations beyond -maxInt..maxInt are not required to work properly.
Title: Re: n-bit integer, larger than Int64.
Post by: eli on October 26, 2021, 05:12:58 pm

Maybe you can improve or alter your algorithm so it doesn’t exceed the bounds of -maxInt..maxInt? Do you really need to iterate over all integers in (−2n, 2n)? Also (possibly to the detriment of precision) you can use ln/exp and logarithmic rules (https://en.wikipedia.org/wiki/List_of_logarithmic_identities#Using_simpler_operations).

What I actually need is, to assign a "huge" integer to a variable. The "huge" integer is a product of some non-negative integers, each of which is of int64 type.

For example, I would like to write something like:
const c = 2 ** 63 -1; var x: int64; begin x:=c*c*c end.

Let's assume that the range of x is not expected to exceed the value of 2 to the n-th power (minus 1), n being a constant.

How do I write that?
Title: Re: n-bit integer, larger than Int64.
Post by: SymbolicFrank on October 26, 2021, 05:24:01 pm
This (http://rvelthuis.de/programs/bigintegers.html) is a nice library. Unfortunately, it doesn't run out of the box, as it uses a few very Delphi-specific constructs. I did port it to Free Pascal a few years ago, but never got around to do some serious testing. But it wasn't that hard (half a day or so).
Title: Re: n-bit integer, larger than Int64.
Post by: avk on October 26, 2021, 05:33:13 pm

For example, I would like to write something like:
const c = 2 ** 63 -1; var x: int64; begin x:=c*c*c end.

Let's assume that the range of x is not expected to exceed the value of 2 to the n-th power (minus 1), n being a constant.

How do I write that?

for example using GMP:
Code: Pascal  [Select][+][-]
  1. ...
  2. const
  3.   c = High(QWord);
  4. var
  5.   x: MPInteger;
  6. begin
  7.   x := c.ToString; //need SysUtils in uses clause
  8.   x := x*x*x;
  9.   WriteLn(string(x)); // prints 6277101735386680762814942322444851025767571854389858533375
  10. end;
  11.  
Title: Re: n-bit integer, larger than Int64.
Post by: BobDog on October 26, 2021, 05:37:06 pm

Some 2^n-1 numbers.
Stopped as 2^128 -1, but continuable if required.
Code: Pascal  [Select][+][-]
  1. program numbers;
  2. {$MODE objfpc}{$H+}
  3. uses
  4. strutils;
  5. function qmult(aa:ansistring;bb:ansistring):ansistring;
  6.  type
  7.      AT = array[0..99] of longint;
  8.      var
  9.      _mod,_div:at;
  10.      z,i,j,la,lb,tmpi:longint;
  11.      tmps:ansistring;
  12.      ans,cc:ansistring;
  13.      n,carry,ai:smallint;
  14.      a,b,c:pchar;
  15.  
  16.       begin {create lookup  tables}
  17.      for z:=0 to 99 do
  18.      begin
  19.      _mod[z]:= (z mod 10) +48;
  20.      _div[z]:=  z div 10;
  21.       end;  {created lookup tables}
  22.      
  23.       la:=length(aa);lb:=length(bb);
  24.       If Lb>La Then
  25.       begin
  26.       tmpi:=la;tmps:=aa;
  27.       la:=lb;aa:=bb;
  28.       lb:=tmpi;bb:=tmps;
  29.       end;
  30.       Setlength(cc,la+lb);
  31.        FillChar(cc[1],la+lb,#48);
  32.        a:=@aa[1];b:=@bb[1];c:=@cc[1];
  33.        for i:=la-1 downto 0 do
  34.       begin
  35.          carry:=0;ai:=ord(a[i])-48 ;
  36.       for j:= lb-1 downto 0 do
  37.       begin
  38.         n :=ai*(ord(b[j])-48)+(ord(c[i+j+1])-48)+carry;
  39.         carry :=_Div[n];ord(c[i+j+1]):=_Mod[n];
  40.       end; {next j}
  41.        ord(c[i]):=ord(c[i])+carry ;
  42.       end; {next i}
  43.       ans:=c;
  44.       if c[1]='0' then ans:=copy(c,2,length(c)-1) ;
  45.       exit(ans);
  46.       end;
  47.      
  48.       function pow2(n:integer):ansistring;
  49.      var
  50.      i:integer;
  51.     q,ans:ansistring;
  52.     begin
  53.     q:='2';
  54.     for i:=1 to n-1 do q:=qmult('2',q);
  55.     ans:=q;
  56.      if q[1]='0' then ans:=copy(q,2,length(q)-1) ;
  57.     exit(ans);
  58.     end;
  59.      
  60.       procedure decrement(var s:ansistring);//:ansistring;
  61.       var
  62.       counts,ls:longint;
  63.       b,c,ans:ansistring;
  64.       begin
  65.       ls:=length(s);
  66.       counts:=0;
  67.       ans:='';b:='';
  68.       repeat
  69.       while ord(s[ls-counts-1+1])=48 do
  70.       begin
  71.       counts:=counts+1;
  72.       end;
  73.        if ord(s[ls-counts-1+1])<>48 Then
  74.       begin
  75.       ans:=leftstr(s,ls-counts-1);
  76.       Str(ord(s[ls-counts-1+1])-49,b);
  77.       ans:=ans+b;
  78.       setlength(c,counts);
  79.       FillChar(c[1],counts,#57);
  80.       ans:=ans+c;
  81.       s:=ans;
  82.       exit;
  83.       end;
  84.       until (true);
  85.       end;
  86.      
  87.      
  88. var
  89. i:integer;
  90. q:ansistring;
  91.  
  92.  
  93. begin
  94.  
  95. for i:=1 to 128 do
  96.  begin
  97.  q:=pow2(i);
  98.  decrement(q);
  99.   write('2^',i,'-1','   ',q,'  ');
  100.  
  101.   case q of
  102.   '127':write('shortint');
  103.   '255':write('byte');
  104.   '32767':write('smallint');
  105.   '65535':write('word');
  106.   '2147483647':write('longint');
  107.   '4294967295':write('longword');
  108.   '9223372036854775807':write('int64');
  109.   '18446744073709551615':write('qword  (End of numerical)');
  110.   end;
  111.  
  112.  writeln;
  113.  
  114.  
  115.  end;
  116.  writeln('Press enter to end . . .');
  117.  readln;
  118.  
  119. end.
  120.  
  121.  
Title: Re: n-bit integer, larger than Int64.
Post by: Warfley on October 26, 2021, 09:12:45 pm
Indeed. And I always advocate for the security principle: “Don’t use functionality that is not documented.” And if it’s not documented, it might be gone in the next release without further notice.
Well this principle doesn't hold up very well with many fpc/fcl/lcl units and libraries simply because most of the documentation is missing, outdated or simply wrong.
The TODO in the operators part looks to me as if there were plans to document this, but it either got forgotten or the person writing this article didn't have had the time to finish it.

Sadly there is not enough workpower to keep the doc complete and up to date
Title: Re: n-bit integer, larger than Int64.
Post by: MarkMLl on October 26, 2021, 09:33:01 pm
Well this principle doesn't hold up very well with many fpc/fcl/lcl units and libraries simply because most of the documentation is missing, outdated or simply wrong.

I think you're being very brave to say that, but since you've raised your head above the parapet I have to agree with you.

My major beef is that the (online) documentation gives no indication of when things have been added or changed. When I was trying to keep up with multiple CPU families, which necessitated compiling against multiple FPC versions, I tried to generate permuted indices and automatically-annotate the docs with when functions had been added, but was too far down the learning curve and had too many other demands on my time to make an impact... and I have to say that when I mentioned what I was trying to do the lack of interest gave me little incentive to continue.

I also have to say that when I was looking at some of the Python API documentation I was extremely impressed by its thoroughness. Shame I have such a low opinion of the language itself.

MarkMLl
Title: Re: n-bit integer, larger than Int64.
Post by: eli on October 27, 2021, 10:41:40 am

for example using GMP:
Code: Pascal  [Select][+][-]
  1. ...
  2. const
  3.   c = High(QWord);
  4. var
  5.   x: MPInteger;
  6. begin
  7.   x := c.ToString; //need SysUtils in uses clause
  8.   x := x*x*x;
  9.   WriteLn(string(x)); // prints 6277101735386680762814942322444851025767571854389858533375
  10. end;
  11.  

What's the maximal quantity of digits, the number assigned to x can have, using your method?

Additionally, except for writing:
{$mode objFPC} uses  GMP; SysUtils;
Should anything else be written before the "begin"?
Title: Re: n-bit integer, larger than Int64.
Post by: avk on October 27, 2021, 11:21:24 am
IIRC, the size of GMP' mpz_t (and hence MPInteger) is limited only by the available computer memory.
Title: Re: n-bit integer, larger than Int64.
Post by: MarkMLl on October 27, 2021, 11:27:32 am
IIRC, the size of GMP' mpz_t (and hence MPInteger) is limited only by the available computer memory.

"There are no practical limits to the precision except the ones implied by the available memory (operands may be of up to 232−1 bits on 32-bit machines and 237 bits on 64-bit machines)."

https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

MarkMLl
Title: Re: n-bit integer, larger than Int64.
Post by: avk on October 27, 2021, 11:48:18 am
...
Additionally, except for writing:
{$mode objFPC} uses  GMP; SysUtils;
Should anything else be written before the "begin"?

You need the GMP (https://gmplib.org/) library installed (on *nix machines this is usually the default).

example:
Code: Pascal  [Select][+][-]
  1. program gmp_test;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.   SysUtils, gmp;
  7.  
  8. var
  9.   f: MPInteger;
  10. begin
  11.   f := z_fac_ui(1000); // factorial
  12.   WriteLn(string(f));
  13. end.
  14.  
it prints
Code: Text  [Select][+][-]
  1. 40238726007709377354370243392300398571937486421071463254379991042993851239862902
  2. 05920442084869694048004799886101971960586316668729948085589013238296699445909974
  3. 24504087073759918823627727188732519779505950995276120874975462497043601418278094
  4. 64649629105639388743788648733711918104582578364784997701247663288983595573543251
  5. 31853239584630755574091142624174743493475534286465766116677973966688202912073791
  6. 43853719588249808126867838374559731746136085379534524221586593201928090878297308
  7. 43139284440328123155861103697680135730421616874760967587134831202547858932076716
  8. 91324484262361314125087802080002616831510273418279777047846358681701643650241536
  9. 91398281264810213092761244896359928705114964975419909342221566832572080821333186
  10. 11681155361583654698404670897560290095053761647584772842188967964624494516076535
  11. 34081989013854424879849599533191017233555566021394503997362807501378376153071277
  12. 61926849034352625200015888535147331611702103968175921510907788019393178114194545
  13. 25722386554146106289218796022383897147608850627686296714667469756291123408243920
  14. 81601537808898939645182632436716167621791689097799119037540312746222899880051954
  15. 44414282012187361745992642956581746628302955570299024324153181617210465832036786
  16. 90611726015878352075151628422554026517048330422614397428693306169089796848259012
  17. 54583271682264580665267699586526822728070757813918581788896522081643483448259932
  18. 66043367660176999612831860788386150279465955131156552036093988180612138558600301
  19. 43569452722420634463179746059468257310379008402443243846565724501440282188525247
  20. 09351906209290231364932734975655139587205596542287497740114133469627154228458623
  21. 77387538230483865688976461927383814900140767310446640259899490222221765904339901
  22. 88601856652648506179970235619389701786004081188972991831102117122984590164192106
  23. 88843871218556461249607987229085192968193723886426148396573822911231250241866493
  24. 53143970137428531926649875337218940694281434118520158014123344828015051399694290
  25. 15348307764456909907315243327828826986460278986432113908350621709500259738986355
  26. 42771967428222487575867657523442202075736305694988250879689281627538488633969099
  27. 59826280956121450994871701244516461260379029309120889086942028510640182154399457
  28. 15680594187274899809425474217358240106367740459574178516082923013535808184009699
  29. 63725242305608559037006242712434169090041536901059339838357779394109700277534720
  30. 00000000000000000000000000000000000000000000000000000000000000000000000000000000
  31. 00000000000000000000000000000000000000000000000000000000000000000000000000000000
  32. 00000000000000000000000000000000000000000000000000000000000000000000000000000000
  33. 00000000
  34.  
Title: Re: n-bit integer, larger than Int64.
Post by: BobDog on October 27, 2021, 11:52:28 am

lib gmp is blazingly fast, it is used by many compilers, you could say it is a de facto big number cruncher.
It is continually worked on and updated, it is written in C.
However for smaller big numbers you can roll out your own methods (as in my previous answer in this topic).
I note that the ^ operator is not allowed in freepascal, so I must use ** instead.
Code: Pascal  [Select][+][-]
  1. program multiply;
  2.  
  3. function qmult(aa:ansistring;bb:ansistring):ansistring;
  4.  type
  5.      AT = array[0..99] of longint;
  6.      var
  7.      _mod,_div:at;
  8.      z,i,j,la,lb,tmpi:longint;
  9.      tmps:ansistring;
  10.      ans,cc:ansistring;
  11.      n,carry,ai:smallint;
  12.      a,b,c:pchar;
  13.  
  14.       begin {create lookup  tables}
  15.      for z:=0 to 99 do
  16.      begin
  17.      _mod[z]:= (z mod 10) +48;
  18.      _div[z]:=  z div 10;
  19.       end;  {created lookup tables}
  20.      
  21.       la:=length(aa);lb:=length(bb);
  22.       If Lb>La Then
  23.       begin
  24.       tmpi:=la;tmps:=aa;
  25.       la:=lb;aa:=bb;
  26.       lb:=tmpi;bb:=tmps;
  27.       end;
  28.       Setlength(cc,la+lb);
  29.        FillChar(cc[1],la+lb,#48);
  30.        a:=@aa[1];b:=@bb[1];c:=@cc[1];
  31.        for i:=la-1 downto 0 do
  32.       begin
  33.          carry:=0;ai:=ord(a[i])-48 ;
  34.       for j:= lb-1 downto 0 do
  35.       begin
  36.         n :=ai*(ord(b[j])-48)+(ord(c[i+j+1])-48)+carry;
  37.         carry :=_Div[n];ord(c[i+j+1]):=_Mod[n];
  38.       end; {next j}
  39.        ord(c[i]):=ord(c[i])+carry ;
  40.       end; {next i}
  41.       ans:=c;
  42.       if ans[1]='0' then ans:=copy(ans,2,length(ans)-1) ;
  43.       exit(ans);
  44.       end;
  45.      
  46.       function pow(num:ansistring;n:integer):ansistring;
  47.      var
  48.      i:integer;
  49.     q,ans:ansistring;
  50.     begin
  51.     q:=num;
  52.     for i:=1 to n-1 do q:=qmult(num,q);
  53.     ans:=q;
  54.      if q[1]='0' then ans:=copy(q,2,length(q)-1) ;
  55.     exit(ans);
  56.     end;
  57.    
  58.     Operator * (r1,r2 : ansistring) z : ansistring;  
  59. begin
  60. z:=qmult(r1,r2);
  61. end;  
  62.  
  63.   Operator ** (r1:ansistring;r2:integer) z : ansistring;  
  64. begin
  65. z:=pow(r1,r2);
  66. end;  
  67.    
  68.       const
  69.   c = High(QWord);
  70. var
  71.   x: ansistring;
  72. begin
  73. Str(c,x);
  74.   WriteLn(x*x*x); // prints 6277101735386680762814942322444851025767571854389858533375
  75.   writeln;
  76.    WriteLn(x**3);// also prints 6277101735386680762814942322444851025767571854389858533375
  77.  
  78.     writeln;
  79.     writeln (x**1000);
  80.     writeln('press return to end . . .');
  81.   readln;
  82. end.
  83.  

Title: Re: n-bit integer, larger than Int64.
Post by: avk on October 27, 2021, 01:31:25 pm
...
"There are no practical limits to the precision except the ones implied by the available memory (operands may be of up to 232−1 bits on 32-bit machines and 237 bits on 64-bit machines)."

https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

MarkMLl

It looks logical for 32-bit systems, otherwise you won't get access to individual bits.
It's funny, but experiments for a 32-bit program on win-64 gives a maximum bit size of 2^32-161.
Title: Re: n-bit integer, larger than Int64.
Post by: BobDog on October 27, 2021, 03:42:39 pm

I cannot find the gmp units in 3.2.2 64 bit pascal??
but they are in the 32 bit version.
Here is the .dll and the example by avk compared to another method.

Title: Re: n-bit integer, larger than Int64.
Post by: eli on October 27, 2021, 04:33:44 pm
IIRC, the size of GMP' mpz_t (and hence MPInteger) is limited only by the available computer memory.

"There are no practical limits to the precision except the ones implied by the available memory (operands may be of up to 232−1 bits on 32-bit machines and 237 bits on 64-bit machines)."

https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

MarkMLl

avk's result, printing the factorial of 1000, has more than 2500 digits, a way beyond the 237 bits you have mentioned.
Title: Re: n-bit integer, larger than Int64.
Post by: MarkMLl on October 27, 2021, 04:52:11 pm
avk's result, printing the factorial of 1000, has more than 2500 digits, a way beyond the 237 bits you have mentioned.

I didn't /mention/, I C&Ped... and the markup got screwed in transit.

Go read the link, or at the very least assume that should be 2^37 bits :-)

MarkMLl
Title: Re: n-bit integer, larger than Int64.
Post by: avk on October 27, 2021, 05:17:50 pm

I cannot find the gmp units in 3.2.2 64 bit pascal??
but they are in the 32 bit version.
Here is the .dll and the example by avk compared to another method.

I have the same problem, curious why? If compile gmp.pas manually and put the result in units, everything seems to work as expected.

If you use QueryPerformanceCounter instead of GetTickCount in your example, the result will be something like this:
Code: Text  [Select][+][-]
  1. time taken gmp = 316
  2. time taken non gmp = 36261
  3.  
Title: Re: n-bit integer, larger than Int64.
Post by: Warfley on October 27, 2021, 09:21:59 pm
I also have to say that when I was looking at some of the Python API documentation I was extremely impressed by its thoroughness. Shame I have such a low opinion of the language itself.
What I have seen with many python docs is that they use a very interesting approach, basically the docs are also in a git repository, and whenever a release of the main software is made, the doc git gets the version tag.
The online doc site then allows looking at what was the last tag this doc was updated (i.e. from which version of the main software is this article), and what changed between the different versions.

I know that writing docs is hard, writing good docs even harder and keeping good docs up to date nearly impossible for a sufficiently large project if you don't have a dedicated team for this sort of stuff. But just knowing how bad the docs are would be worth a lot, simply an information like: "Last update fpc version 2.6.0"
Title: Re: n-bit integer, larger than Int64.
Post by: Jurassic Pork on October 28, 2021, 06:28:20 am
hello,
python can compute large integer natively and it is fast.
you can call python from lazarus with python4lazarus.
Here is a test to calculate factorial(1000) from console demo program of  python4Lazarus
Elapsed time measured with Epiktimer :
Code: Pascal  [Select][+][-]
  1.   try
  2.     ET.Clear;
  3.     ET.Start;
  4.     GetPythonEngine.ExecString(Str);
  5.     ET.Stop;
  6.     DoLogConsoleLine('Elapsed Time : ' + FloatToStr(ET.Elapsed));
  7.   except
  8.   end;

11,9 ms  (see attachment).

Friendly, J.P
Title: Re: n-bit integer, larger than Int64.
Post by: SymbolicFrank on October 28, 2021, 10:17:02 am
Here are the converted but not tested Bignumbers units from Rudy Velthuis. They compile and the basic stuff works.
Title: Re: n-bit integer, larger than Int64.
Post by: Kays on October 28, 2021, 01:02:59 pm
What I actually need is, to assign a "huge" integer to a variable. The "huge" integer is a product of some non-negative integers, each of which is of int64 type.
This smells like cryptography or similar task. If you just wanna store your value, put your integer factorization into an array. It’s that simple. Then the entire array together represents a value, or at least a way to calculate it, you know. You don’t need to calculate the product, just store its factors. Use (a sorted array of) primes if you want a unique way to store a product (https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic).

lib gmp is blazingly fast, it is used by many compilers, […] However for smaller big numbers you can roll out your own methods […]
Don’t program what’s already been programmed for you. It’s certainly fun to implement it, but I wouldn’t recommend that to Eli unless he intends to and is capable of maintaining it. Otherwise you’ll suffer from the not invented here (https://en.wikipedia.org/wiki/Not_invented_here) syndrome. ;D
Title: Re: n-bit integer, larger than Int64.
Post by: BobDog on October 28, 2021, 06:27:34 pm

For those who are interested.
Python simple.(64 bit) and a factorial(1000) test.
https://www.mediafire.com/file/n7xofqqmz7qskac/pythontest.zip/file
Title: Re: n-bit integer, larger than Int64.
Post by: srvaldez on October 31, 2021, 02:55:34 am

I cannot find the gmp units in 3.2.2 64 bit pascal??
but they are in the 32 bit version.
you can compile the gmp unit from source fpcbuild-3.2.2\fpcsrc\packages\gmp\src to 64-bit and then place the files in FPC\3.2.2\units\x86_64-win64\gmp
Title: Re: n-bit integer, larger than Int64.
Post by: BobDog on October 31, 2021, 09:18:05 am

Thanks srvaldez, I did that, I found gmp.bas in a 3.2.0 distribution and compiled the unit on 3.2.2, it worked.
I must admit though, I did it the old fashioned way to begin with:
Code: Pascal  [Select][+][-]
  1. program gmp_test;
  2.  
  3.  
  4. uses
  5.   SysUtils;
  6.  
  7.   type __mpz_struct=object
  8.         _mp_alloc:integer;
  9.         _mp_size :integer;
  10.         _mp_d :pointer
  11.    end;
  12.  
  13.  procedure fact(p:pchar;i:integer) cdecl external 'gmp.dll' Name '__gmpz_fac_ui';
  14.  procedure init2(p:pchar;i:integer)cdecl external 'gmp.dll' Name '__gmpz_init2';
  15.  function setstring(p1:pchar;p2:pchar;i:integer):integer cdecl external 'gmp.dll' Name '__gmpz_set_str';
  16.  function sprintf(s:pchar;mask:pchar):integer; cdecl; varargs; external 'gmp.dll' name '__gmp_sprintf';
  17.  procedure mpz_clear(p:pchar)cdecl external 'gmp.dll' Name   '__gmpz_clear';
  18.  
  19.  function factorial(i:integer):ansistring;
  20.   var f:__mpz_struct;
  21.   var ans:ansistring;
  22.  begin
  23.   Setlength(ans,10000000);
  24.  init2(@f,0);
  25.  setstring(@f,'',10);
  26.  fact(@f,i);
  27.  sprintf( pchar(ans),'%Zi', @f );
  28.  mpz_clear(@f);
  29.  exit(trim(ans));
  30.  end;
  31.  
  32. begin
  33.   WriteLn(factorial(1000));
  34.   readln;
  35. end.
  36.  
You need gmp.dll handy of course either way.

Title: Re: n-bit integer, larger than Int64.
Post by: SymbolicFrank on October 31, 2021, 11:42:54 am
You mean, something like this:

Code: Pascal  [Select][+][-]
  1. uses
  2.   Velthuis.BigIntegers;
  3. ..
  4. procedure TForm1.Button1Click(Sender: TObject);
  5. var
  6.   a, b: BigInteger;
  7.   s: string;
  8. begin
  9.   a := '123456789012345678901234567890';
  10.   b := a * a * a;
  11.   s := b.ToStringClassic(10);
  12.   Memo1.Lines.Text := s;
  13. end;

?


I think the most interesting thing of those BigInteger libraries is, that they tend to treat those integers as floats, to speed up execution time.
Title: Re: n-bit integer, larger than Int64.
Post by: avk on October 31, 2021, 02:53:41 pm
...
Code: Pascal  [Select][+][-]
  1. uses
  2.   Velthuis.BigIntegers;
  3. ...
  4.  
...

Unfortunately, this library does not compile in FPC i386-win32.
Also in FPC x86_64-win64 BigInteger.ModPow(1073676287, 68718952446, 68718952447) returns 0 (it seems it should be 1).
So it seems not usable.
Title: Re: n-bit integer, larger than Int64.
Post by: SymbolicFrank on October 31, 2021, 04:04:49 pm
Well, as I posted earlier, I converted the BigIntegers unit (together with a few more that are used by it) from Delphi to FPC. It compiles, the basic stuff works but it isn't tested.

Then again, it's fully Object Pascal.
Title: Re: n-bit integer, larger than Int64.
Post by: SymbolicFrank on November 01, 2021, 07:39:02 am
He explains it at the bottom of this page (http://rvelthuis.de/programs/bigintegers.html).
Title: Re: n-bit integer, larger than Int64.
Post by: eli on November 04, 2021, 09:55:49 am
This smells like cryptography or similar task. If you just wanna store your value, put your integer factorization into an array. It’s that simple. Then the entire array together represents a value, or at least a way to calculate it, you know. You don’t need to calculate the product, just store its factors. Use (a sorted array of) primes if you want a unique way to store a product (https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic).

Oh, I did need to calculate the product, and I used the library gmp (you'd suggested me here) for calculating that.

Actually, I wanted to see if the equation |3^x - 2^y| = 1, had any natural solutions, besides the three obvious ones:
3^1 - 2^1 = 1.
2^2 - 3^1 = 1.
3^2 - 2^3 = 1.

My conjecture is that this equation has no other natural solutions. Thanks to the library you had suggested me here, my conjecture turned out to be true - for all natural exponentials not larger than 10,000. However. for larger natural exponentials, the calculation becomes too slow, so I didn't check out any larger natural exponentials.

Thank you so much , for being the first one to suggest me a very useful library - by which I could verify my conjecture for very big natural numbers. I still wonder, though, if my conjecture is provable for all natural numbers.

Thanks also to the other members for the other suggestions.
Title: Re: n-bit integer, larger than Int64.
Post by: MathMan on November 04, 2021, 11:08:09 am
...

Oh, I did need to calculate the product, and I used the library gmp (you'd suggested me here) for calculating that.

Actually, I wanted to see if the equation |3^x - 2^y| = 1, had any natural solutions, besides the three obvious solutions:
3^1 - 2^1 = 1.
2^2 - 3^1 = 1.
3^2 - 2 ^3 = 1.

My conjecture is that this equation has no other natural solutions. Thanks to the library you had suggested me here, my conjecture turned out to be true - for all natural exponentials not larger than 1000. However. for larger natural exponentials, the calculation becomes too slow, so I didn't check out any larger natural exponentials.

...

Hello eli - if the above is what you want to do, why not look for some already existing mathematical treatise of the subject. Iirc this - and the more general a^n - b^k = 1 - have been solved in context of number theory.

Cheers,
MathMan
Title: Re: n-bit integer, larger than Int64.
Post by: Thaddy on November 04, 2021, 12:17:30 pm
He explains it at the bottom of this page (http://rvelthuis.de/programs/bigintegers.html).
Rudy is sadly missing from this planet, but indeed. By now, {$mode delphi}+removing the scoping is sufficient to make it work, even the assembler stuff for 32 bit.
Title: Re: n-bit integer, larger than Int64.
Post by: eli on November 04, 2021, 12:58:29 pm
...

Oh, I did need to calculate the product, and I used the library gmp (you'd suggested me here) for calculating that.

Actually, I wanted to see if the equation |3^x - 2^y| = 1, had any natural solutions, besides the three obvious ones:
3^1 - 2^1 = 1.
2^2 - 3^1 = 1.
3^2 - 2^3 = 1.

My conjecture is that this equation has no other natural solutions. Thanks to the library you had suggested me here, my conjecture turned out to be true - for all natural exponentials not larger than 10,000. However. for larger natural exponentials, the calculation becomes too slow, so I didn't check out any larger natural exponentials.

...

Hello eli - if the above is what you want to do, why not look for some already existing mathematical treatise of the subject. Iirc this - and the more general a^n - b^k = 1 - have been solved in context of number theory.

Cheers,
MathMan
Correct. I've just noticed this is Catalan's conjecture, that has already been proven.
Title: Re: n-bit integer, larger than Int64.
Post by: Jurassic Pork on November 04, 2021, 01:21:22 pm
hello,
python with the module sympy can solve this type of equation :
Quote
>>>import sympy as sy
>>>x, y = sy.symbols("x y")
>>>f=sy.Eq(3**x - 2**y,1)
>>>sy.solve((f),(x,y))
Result (x,y)  --> [(log(2**y + 1)/log(3), y)]
Friendly, J.P
Title: Re: n-bit integer, larger than Int64.
Post by: eli on November 04, 2021, 01:35:07 pm
hello,
python with the module sympy can solve this type of equation :
Quote
>>>import sympy as sy
>>>x, y = sy.symbols("x y")
>>>f=sy.Eq(3**x - 2**y,1)
>>>sy.solve((f),(x,y))
Result (x,y)  --> [(log(2**y + 1)/log(3), y)]
Friendly, J.P

I suspect the result given by Python cannot tell us, if the equation |3^x - 2^y| - 1, has any natural solutions other than the three obvious ones:
3^1 - 2^1 = 1.
2^2 - 3^1 = 1.
3^2 - 2^3 = 1.
Title: Re: n-bit integer, larger than Int64.
Post by: MathMan on November 05, 2021, 08:56:49 am
...

Oh, I did need to calculate the product, and I used the library gmp (you'd suggested me here) for calculating that.

Actually, I wanted to see if the equation |3^x - 2^y| = 1, had any natural solutions, besides the three obvious ones:
3^1 - 2^1 = 1.
2^2 - 3^1 = 1.
3^2 - 2^3 = 1.

My conjecture is that this equation has no other natural solutions. Thanks to the library you had suggested me here, my conjecture turned out to be true - for all natural exponentials not larger than 10,000. However. for larger natural exponentials, the calculation becomes too slow, so I didn't check out any larger natural exponentials.

...

Hello eli - if the above is what you want to do, why not look for some already existing mathematical treatise of the subject. Iirc this - and the more general a^n - b^k = 1 - have been solved in context of number theory.

Cheers,
MathMan
Correct. I've just noticed this is Catalan's conjecture, that has already been proven.

eli - sorry for the late response, but I had to look up something in my library @ home. A "light" spotlighting dive into algebraic number theory can be had from Paolo Ribenboim, "My numbers, my friends ...". "Light" in the sense of you should still have some thorough understanding of algebra but don't need to be knowledgeable about highly advanced stuff.

Cheers,
MathMan
TinyPortal © 2005-2018