Recent

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

eli

  • New Member
  • *
  • Posts: 33
n-bit integer, larger than Int64.
« on: October 26, 2021, 12:01:51 pm »
 May I use it in Free Pascal?

eli

  • New Member
  • *
  • Posts: 33
Re: n-bit integer, larger than Int64.
« Reply #1 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?
« Last Edit: October 26, 2021, 01:22:32 pm by eli »

Kays

  • Hero Member
  • *****
  • Posts: 569
  • Whasup!?
    • KaiBurghardt.de
Re: n-bit integer, larger than Int64.
« Reply #2 on: October 26, 2021, 01:50:25 pm »
May I use it in Free Pascal?
Pascal defines that all arithmetic operations 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. 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.
Yours Sincerely
Kai Burghardt

Warfley

  • Hero Member
  • *****
  • Posts: 1499
Re: n-bit integer, larger than Int64.
« Reply #3 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
« Last Edit: October 26, 2021, 02:02:28 pm by Warfley »

Kays

  • Hero Member
  • *****
  • Posts: 569
  • Whasup!?
    • KaiBurghardt.de
Re: n-bit integer, larger than Int64.
« Reply #4 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.
« Last Edit: October 26, 2021, 02:43:27 pm by Kays »
Yours Sincerely
Kai Burghardt

Warfley

  • Hero Member
  • *****
  • Posts: 1499
Re: n-bit integer, larger than Int64.
« Reply #5 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.
« Last Edit: October 26, 2021, 02:59:09 pm by Warfley »

AlexTP

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

eli

  • New Member
  • *
  • Posts: 33
Re: n-bit integer, larger than Int64.
« Reply #7 on: October 26, 2021, 04:24:27 pm »
.
« Last Edit: October 26, 2021, 05:14:04 pm by eli »

Kays

  • Hero Member
  • *****
  • Posts: 569
  • Whasup!?
    • KaiBurghardt.de
Re: n-bit integer, larger than Int64.
« Reply #8 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} nor {$rangeChecks on} will produce an error, because arithmetic operations beyond -maxInt..maxInt are not required to work properly.
Yours Sincerely
Kai Burghardt

eli

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

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?

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 1313
Re: n-bit integer, larger than Int64.
« Reply #10 on: October 26, 2021, 05:24:01 pm »
This 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).
« Last Edit: October 26, 2021, 11:06:17 pm by SymbolicFrank »

avk

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

BobDog

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

Warfley

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

MarkMLl

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

 

TinyPortal © 2005-2018