Recent

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

srvaldez

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

BobDog

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


SymbolicFrank

  • Hero Member
  • *****
  • Posts: 1313
Re: n-bit integer, larger than Int64.
« Reply #32 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.
« Last Edit: October 31, 2021, 11:55:25 am by SymbolicFrank »

avk

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

SymbolicFrank

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

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 1313
Re: n-bit integer, larger than Int64.
« Reply #35 on: November 01, 2021, 07:39:02 am »
He explains it at the bottom of this page.

eli

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

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.
« Last Edit: November 04, 2021, 03:32:16 pm by eli »

MathMan

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

Thaddy

  • Hero Member
  • *****
  • Posts: 14165
  • Probably until I exterminate Putin.
Re: n-bit integer, larger than Int64.
« Reply #38 on: November 04, 2021, 12:17:30 pm »
He explains it at the bottom of this page.
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.
Specialize a type, not a var.

eli

  • New Member
  • *
  • Posts: 33
Re: n-bit integer, larger than Int64.
« Reply #39 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.
« Last Edit: November 04, 2021, 09:18:50 pm by eli »

Jurassic Pork

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

eli

  • New Member
  • *
  • Posts: 33
Re: n-bit integer, larger than Int64.
« Reply #41 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.
« Last Edit: November 04, 2021, 03:22:51 pm by eli »

MathMan

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