Recent

Author Topic: New Big Integer library is almost finished  (Read 18741 times)

srvaldez

  • Full Member
  • ***
  • Posts: 117
Re: New Big Integer library is almost finished
« Reply #165 on: November 05, 2024, 12:57:07 am »
👍
all works OK so far  :)

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is almost finished
« Reply #166 on: November 07, 2024, 11:34:17 am »
I've just made version 4.86 available. This has bug fixes and speed increases.

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is almost finished
« Reply #167 on: November 07, 2024, 11:36:05 am »
all works OK so far
I'm disappointed... I was hoping you would find more bugs! :D

srvaldez

  • Full Member
  • ***
  • Posts: 117
Re: New Big Integer library is almost finished
« Reply #168 on: November 07, 2024, 12:24:39 pm »
 :D

srvaldez

  • Full Member
  • ***
  • Posts: 117
Re: New Big Integer library is almost finished
« Reply #169 on: November 07, 2024, 03:32:14 pm »
just for fun, the first 50 Bernoulli numbers
Code: Pascal  [Select][+][-]
  1. {$mode objfpc}
  2. {$MODESWITCH NESTEDCOMMENTS+}
  3. {$warn 6058 off}
  4. {$warn 5025 off}
  5.  
  6. program speed_test;
  7. uses    sysutils
  8. ,       strutils
  9. ,       strings
  10. ,       math
  11. ,       Multi_Int
  12. ;
  13.  
  14. const prec = 50;
  15. const n = 50;
  16.  
  17. type Rational = record
  18.     num : Multi_Int_XV;
  19.     den : Multi_Int_XV;
  20. end;
  21.    
  22. var
  23.     big_int_size,
  24.     start_time,
  25.     end_time        :int32;
  26.     delta           :double;
  27.  
  28.     b: array[0..n] of Rational;
  29.     c: array[0..n] of Rational;
  30.     one, tmp : Rational;
  31.     i, j : longint;
  32.  
  33. function GCD(const n : Multi_Int_XV; const m : Multi_Int_XV) : Multi_Int_XV;
  34. var
  35.     a, b : Multi_Int_XV;
  36. begin
  37.     a:=abs(n);
  38.     b:=abs(m);
  39.     While ((a <> 0) And (b <> 0)) do
  40.         If a > b Then a := a Mod b Else b := b Mod a;
  41.  
  42.     GCD := a + b;
  43. End;
  44.  
  45. function lcm(const a : Multi_Int_XV; const b : Multi_Int_XV) : Multi_Int_XV;
  46. begin
  47.     lcm := (a * b) div gcd(a, b);
  48. end;
  49.  
  50. procedure RationalSimplify( var r : Rational);
  51. var
  52.     divisor : Multi_Int_XV;
  53. begin
  54.     divisor := GCD(r.num, r.den);
  55.     r.num := r.num div divisor;
  56.     r.den := r.den div divisor;
  57.     if (r.den < 0) then
  58.     begin
  59.         r.num := -r.num;
  60.         r.den := -r.den;
  61.     end;
  62. end;
  63.  
  64. function RationalAdd(const r1 : Rational; const r2 : Rational) : Rational;
  65. var
  66.     res : Rational;
  67. begin
  68.     res.num := r1.num * r2.den + r2.num * r1.den;
  69.     res.den := r1.den * r2.den;
  70.     RationalSimplify(res);
  71.     RationalAdd := res;
  72. end;
  73.  
  74. function RationalSubtract(const r1 : Rational; const r2 : Rational) : Rational;
  75. var
  76.     res : Rational;
  77. begin
  78.     res.num := r1.num * r2.den - r2.num * r1.den;
  79.     res.den := r1.den * r2.den;
  80.     RationalSimplify(res);
  81.     RationalSubtract := res;
  82. end;
  83.  
  84. function RationalMultiply(const r1 : Rational; const r2 : Rational) : Rational;
  85. var
  86.     res : Rational;
  87. begin
  88.     res.num := r1.num * r2.num;
  89.     res.den := r1.den * r2.den;
  90.     RationalSimplify(res);
  91.     RationalMultiply := res;
  92. end;
  93.  
  94. function RationalDivide(const r1 : Rational; const r2 : Rational) : Rational;
  95. var
  96.     res : Rational;
  97. begin
  98.     res.num := r1.num * r2.den;
  99.     res.den := r1.den * r2.num;
  100.     RationalSimplify(res);
  101.     RationalDivide := res;
  102. end;
  103.  
  104. function RationalDivide(const r1 : Rational; const r2 : LongInt) : Rational;
  105. var
  106.     res : Rational;
  107. begin
  108.     res.num := r1.num;
  109.     res.den := r1.den * r2;
  110.     RationalSimplify(res);
  111.     RationalDivide := res;
  112. end;
  113.  
  114. operator := (const r : ansistring) z : Rational;  
  115. var
  116.     lhs, rhs : ansistring;
  117.     c, i, n : longint;
  118.     num, den : Multi_Int_XV;
  119. begin
  120.     c:=0;
  121.     n:=length(r);
  122.     for i:=1 to n do
  123.     begin
  124.         if r[i]='/' then
  125.         begin
  126.             c:=i;
  127.             break;
  128.         end;
  129.     end;
  130.     lhs:=leftstr(r, c-1);
  131.     rhs:=rightstr(r, n-c);
  132.     z.num:=lhs;
  133.     z.den:=rhs;
  134.     RationalSimplify(z);
  135. end;
  136.  
  137. operator := (const r : longint) z : Rational;  
  138.  
  139. begin
  140.     z.num:=r;
  141.     z.den:=1;
  142. end;
  143.  
  144. operator + (const x : Rational; const y : Rational) z : Rational;  
  145.  
  146. begin
  147.     z:=RationalAdd(x, y);
  148. end;
  149.  
  150. operator - (const x : Rational) z : Rational;  
  151.  
  152. begin
  153.     z:=x;
  154.     z.num*=(-1);
  155. end;
  156.  
  157. operator - (const x : Rational; const y : Rational) z : Rational;  
  158.  
  159. begin
  160.     z:=RationalSubtract(x, y);
  161. end;
  162.  
  163. operator * (const x : Rational; const y : Rational) z : Rational;  
  164.  
  165. begin
  166.     z:=RationalMultiply(x, y);
  167. end;
  168.  
  169. operator * (const x : Rational; const y : LongInt) z : Rational;
  170.  
  171. begin
  172.     z:=x;
  173.     z.num*=y;
  174.     RationalSimplify(z);
  175. end;
  176.  
  177. operator / (const x : Rational; const y : Rational) z : Rational;  
  178.  
  179. begin
  180.     z:=RationalDivide(x, y);
  181. end;
  182.  
  183. operator / (const x : Rational; const y : LongInt) z : Rational;  
  184.  
  185. begin
  186.     z:=RationalDivide(x, y);
  187. end;
  188.  
  189. operator < (const a,b:Rational):Boolean;
  190. var
  191.     n, m : Multi_Int_XV;
  192. begin
  193.     n:=a.num*b.den;
  194.     m:=b.num*a.den;
  195.     result:=(n<m);
  196. end;
  197.  
  198. operator <= (const a,b:Rational):Boolean;
  199. var
  200.     n, m : Multi_Int_XV;
  201. begin
  202.     n:=a.num*b.den;
  203.     m:=b.num*a.den;
  204.     result:=(n<=m);
  205. end;
  206.  
  207. operator > (const a,b:Rational):Boolean;
  208. var
  209.     n, m : Multi_Int_XV;
  210. begin
  211.     n:=a.num*b.den;
  212.     m:=b.num*a.den;
  213.     result:=(n>m);
  214. end;
  215.  
  216. operator >= (const a,b:Rational):Boolean;
  217. var
  218.     n, m : Multi_Int_XV;
  219. begin
  220.     n:=a.num*b.den;
  221.     m:=b.num*a.den;
  222.     result:=(n>=m);
  223. end;
  224.  
  225. operator = (const a,b:Rational):Boolean;
  226. var
  227.     n, m : Multi_Int_XV;
  228. begin
  229.     n:=a.num*b.den;
  230.     m:=b.num*a.den;
  231.     result:=(n=m);
  232. end;
  233.  
  234. function abs(const x : Rational): Rational;
  235. var
  236.     a : Rational;
  237. begin
  238.     a:=x;
  239.     if a.num<0 then a.num*=-1;
  240.     abs:=a;
  241. end;
  242.  
  243. function RationalToStr(const n:Rational): ansistring;
  244. var
  245.     s:ansistring;
  246.    
  247. begin
  248.     s:='';
  249.     if n.num>0 then s:=' ';
  250.     s:=s+n.num.toStr;
  251.     if n.den>1 then s:=s+'/'+n.den.toStr;
  252.     RationalToStr:=s;
  253. end;
  254.  
  255. begin
  256.     big_int_size:= ceil( prec / (32*0.3010299956639812));
  257.     Multi_Int_Set_XV_Limit(big_int_size);
  258.     Multi_Int_Initialisation(big_int_size);
  259.    
  260.     //---------------------------------------------------------
  261.     // Akiyama–Tanigawa algorithm for Bn
  262.     //---------------------------------------------------------
  263.  
  264.     start_time:= GetTickCount64;
  265.  
  266.     one := 1;
  267.     For i := 0 To n do
  268.     begin
  269.         c[i] := one / (i+1);
  270.         For j := i downTo 1 do
  271.         begin
  272.             tmp:=c[j - 1]-c[j];
  273.             c[j - 1] := tmp * j;
  274.         end;
  275.         b[i]:=c[0];
  276.     end;
  277.     end_time:= GetTickCount64;
  278.     b[1]:=-b[1]; // the algorithm is wrong, Bernoulli[1] = -1/2
  279.     For i := 0 To n do
  280.     begin
  281.         if i>2 then
  282.         begin
  283.             if (i and 1)=0 then
  284.             begin
  285.                 writeln('B[',i:2,'] = ', RationalToStr(b[i]));
  286.             end;
  287.         end
  288.         else
  289.         begin
  290.             writeln('B[',i:2,'] = ', RationalToStr(b[i]));
  291.         end;
  292.     end;
  293.     delta:= (end_time - start_time) / 1000;
  294.     writeln('time elapsed is ', delta:1:6, ' seconds');
  295.  
  296. end.
  297.  
« Last Edit: November 08, 2024, 01:00:41 am by srvaldez »

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is almost finished
« Reply #170 on: November 07, 2024, 08:47:35 pm »
I've just made version 4.87 available.
Conversion to decimal string is now 3x faster.
Conversion to heximal speed up will follow shortly.

srvaldez

  • Full Member
  • ***
  • Posts: 117
Re: New Big Integer library is almost finished
« Reply #171 on: November 07, 2024, 10:52:18 pm »
👍

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is almost finished
« Reply #172 on: November 08, 2024, 11:18:45 am »
I've just made version 4.88 available.
The main change is that the Multi_Int_XV type size limit can now be specified in number of decimal digits. Thanks to @srvaldez for giving me a formula for this.
There is also a new version of the unit test program.

srvaldez

  • Full Member
  • ***
  • Posts: 117
Re: New Big Integer library is almost finished
« Reply #173 on: November 08, 2024, 11:51:04 am »
thanks ad1mt 👍

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is almost finished
« Reply #174 on: November 08, 2024, 05:42:58 pm »
I've just made version 4.88 available.
I made some omissions in the version 4.88 source file earlier, so I've just uploaded a new source file. Only the minor version number has changed.
I've also updated the documentation to reflect the new feature.

Since v4.88 a compiler error has started appearing for some numerical expressions: "Error: Can't determine which overloaded function to call". I hope to post a fix for this shortly. I don't want to roll back to a previous version, because I'd like to keep the latest changes. The error can be worked around with an explicit type cast to big integer type, of any other integer types in the expression, like this:
v_big1:= v_big2 * big_int_type(v_int64);

This is now fixed in the source file I uploaded at 17:20 GMT. Only the minor version number has changed.
« Last Edit: November 08, 2024, 06:22:14 pm by ad1mt »

srvaldez

  • Full Member
  • ***
  • Posts: 117
Re: New Big Integer library is almost finished
« Reply #175 on: November 08, 2024, 08:31:39 pm »
😁

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is almost finished
« Reply #176 on: November 09, 2024, 08:00:05 am »
I've just made a small improvement to the code & documentation.
Only the minor version number has changed.

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is almost finished
« Reply #177 on: November 09, 2024, 09:41:52 am »
I've just made version 4.89 available.
This has speeded-up Multi_Int_X2/3/4 conversion to decimal ansistring, and bug fixes in Multi_Int_X2/3/4 sqroot functions.

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is almost finished
« Reply #178 on: November 09, 2024, 09:11:24 pm »
I've just made version 4.90 available.
This has faster functions for converting Multi_Int_X2/3/4 types to and from heximal string.

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is almost finished
« Reply #179 on: November 10, 2024, 10:40:45 am »
I'm just finishing version 4.91, which will enable the 64bit override switch to be used in the 32bit compiler/environments.

I expected this code would run slightly slower than native 64bit code, but that is not the case. Code generated by the 32bit compiler with the 64bit switch set, runs faster than 64bit code generated by the 64bit compiler.

Does anyone have any insight into why this is the case?
« Last Edit: November 14, 2024, 12:30:56 pm by ad1mt »

 

TinyPortal © 2005-2018