Recent

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

BobDog

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

srvaldez

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

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


jamie

  • Hero Member
  • *****
  • Posts: 5049
Re: n-bit integer, larger than Int64.
« Reply #33 on: October 31, 2021, 11:34:24 am »
all this reminds be back in the days of the 6502 processor where I implemented a 32 bit integer number system with basic math included and ASCII translation code.

 can't a advanced Record type be made with class operators to make this look natural ?
The only true wisdom is knowing you know nothing

SymbolicFrank

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

jamie

  • Hero Member
  • *****
  • Posts: 5049
Re: n-bit integer, larger than Int64.
« Reply #37 on: November 01, 2021, 01:28:00 am »
converting Delphi code can be tricky if there are any managed strings in and they are doing lots of character interactions on the strings

by default I believe they use WideStrings which are 2 char's wide and fpc is using UTF8 which are single byte

Also at some point and it maybe optional the 0 index was the base index of a managed string instead of 1 so something to look into.
The only true wisdom is knowing you know nothing

SymbolicFrank

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

  • Full Member
  • ***
  • Posts: 240
Re: n-bit integer, larger than Int64.
« Reply #40 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: 10991
Re: n-bit integer, larger than Int64.
« Reply #41 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.
The average programmer productivity is 4-5 hours per day. Peak performance 72 hours for short bursts. MTBF is 1 second or less.

eli

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

 

TinyPortal © 2005-2018