Recent

Author Topic: n-bit integer, larger than Int64.  (Read 11101 times)

MarkMLl

  • Hero Member
  • *****
  • Posts: 3501
Re: n-bit integer, larger than Int64.
« Reply #15 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
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

eli

  • New Member
  • *
  • Posts: 33
Re: n-bit integer, larger than Int64.
« Reply #16 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"?
« Last Edit: October 27, 2021, 10:54:07 am by eli »

avk

  • Hero Member
  • *****
  • Posts: 505
    • my self-education project
Re: n-bit integer, larger than Int64.
« Reply #17 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.

MarkMLl

  • Hero Member
  • *****
  • Posts: 3501
Re: n-bit integer, larger than Int64.
« Reply #18 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
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

avk

  • Hero Member
  • *****
  • Posts: 505
    • my self-education project
Re: n-bit integer, larger than Int64.
« Reply #19 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 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.  

BobDog

  • Full Member
  • ***
  • Posts: 168
Re: n-bit integer, larger than Int64.
« Reply #20 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.  


avk

  • Hero Member
  • *****
  • Posts: 505
    • my self-education project
Re: n-bit integer, larger than Int64.
« Reply #21 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.

BobDog

  • Full Member
  • ***
  • Posts: 168
Re: n-bit integer, larger than Int64.
« Reply #22 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.


eli

  • New Member
  • *
  • Posts: 33
Re: n-bit integer, larger than Int64.
« Reply #23 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.

MarkMLl

  • Hero Member
  • *****
  • Posts: 3501
Re: n-bit integer, larger than Int64.
« Reply #24 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
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

avk

  • Hero Member
  • *****
  • Posts: 505
    • my self-education project
Re: n-bit integer, larger than Int64.
« Reply #25 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.  

Warfley

  • Hero Member
  • *****
  • Posts: 602
Re: n-bit integer, larger than Int64.
« Reply #26 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"

Jurassic Pork

  • Hero Member
  • *****
  • Posts: 1063
Re: n-bit integer, larger than Int64.
« Reply #27 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
Jurassic computer : Sinclair ZX81 - Zilog Z80A à 3,25 MHz - RAM 1 Ko - ROM 8 Ko

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 736
Re: n-bit integer, larger than Int64.
« Reply #28 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.

Kays

  • Sr. Member
  • ****
  • Posts: 382
  • Whasup!?
    • KaiBurghardt.de
Re: n-bit integer, larger than Int64.
« Reply #29 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.

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 syndrome. ;D
Yours Sincerely
Kai Burghardt

 

TinyPortal © 2005-2018