Recent

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

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is finished
« Reply #75 on: October 12, 2024, 09:56:03 pm »
You already possess a very efficient division routine - remember https://forum.lazarus.freepascal.org/index.php/topic,65158.56.html

Regarding your latest question - I am not sure I understand. What makes you think that the missing initialisation is due to passing the parameters over the stack? If you declare a function parameter as var or out FPC only passes a pointer to the value to the function, not the full value itself. Maybe I misunderstood your question.
I did look at your code (back then, and just now), but it is so complex, I could not understand it. I had a lot of problems getting the basic Knuth division algorithm to work. So I think getting your algorithms/code integrated into my library is probably beyond my capability.

The reason I know about the variables having junk values when passed on the stack, is because I can see the junk with the debugger. For an out or var parameter, a pointer is passed, which points to memory that has been allocated, that will shortly be written to by the procedure. That memory will have the junk values from the last time it was used.
« Last Edit: October 12, 2024, 10:00:36 pm by ad1mt »

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: New Big Integer library is finished
« Reply #76 on: October 12, 2024, 10:44:32 pm »
...
I did look at your code (back then, and just now), but it is so complex, I could not understand it. I had a lot of problems getting the basic Knuth division algorithm to work. So I think getting your algorithms/code integrated into my library is probably beyond my capability.

As I said some time back already, fair enough for me. But why are you then ahwing about the speed of other libraries? They are using this (or slight variants of it). You have more or less reached the limit of the algorithm you implemented. I was positively surprised that it is 'only' 40-50 times slower than the one I gave you - I had expected worse actually.

The reason I know about the variables having junk values when passed on the stack, is because I can see the junk with the debugger. For an out or var parameter, a pointer is passed, which points to memory that has been allocated, that will shortly be written to by the procedure. That memory will have the junk values from the last time it was used.

Inbetween I took a closer look at your sources and I now understand the issue better, I think. And I also think I have a solution. The point is - for your XV type you define an Init-procedure which you also make public. But you are only using it internally and at somewhat random places. What I would do is enforce the rule that every XV variable must be initialised before it is used - either by the user in his program or by you when you create helper variables inside your library. To be more explicit - your, and library users, code should look like

Code: Pascal  [Select][+][-]
  1. function Xyz();
  2.  
  3. var
  4.   a, b, c: Multi_Int_XV;
  5.  
  6. begin
  7.   a.init;
  8.   b.init;
  9.   c.init;
  10.  
  11.   // further code using a, b or c
  12. end;
  13.  

Bart

  • Hero Member
  • *****
  • Posts: 5467
    • Bart en Mariska's Webstek
Re: New Big Integer library is finished
« Reply #77 on: October 12, 2024, 10:50:25 pm »
What I would do is enforce the rule that every XV variable must be initialised before it is used - either by the user in his program or by you when you create helper variables inside your library.
Or use management operators (may be slower than doing it manually?).

Bart

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: New Big Integer library is finished
« Reply #78 on: October 12, 2024, 10:58:39 pm »
What I would do is enforce the rule that every XV variable must be initialised before it is used - either by the user in his program or by you when you create helper variables inside your library.
Or use management operators (may be slower than doing it manually?).

Bart

Sure, but the types are build as advanced records - I am not versed what can be done there so I built my answer around what's already there. If derived from tObject instead then he could piggyback on the existing Create / Destroy mechanism and be done with it, iirc?

Cheers,
MathMan

Bart

  • Hero Member
  • *****
  • Posts: 5467
    • Bart en Mariska's Webstek
Re: New Big Integer library is finished
« Reply #79 on: October 12, 2024, 11:58:25 pm »
Sure, but the types are build as advanced records - I am not versed what can be done there

You can apply them to advanced records, see this wiki article.

Bart

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: New Big Integer library is finished
« Reply #80 on: October 13, 2024, 11:31:18 am »
Sure, but the types are build as advanced records - I am not versed what can be done there

You can apply them to advanced records, see this wiki article.

Bart

Thanks for the heads-up Bart. Using that would definitely be the more elegant solution then.

MathMan

srvaldez

  • Full Member
  • ***
  • Posts: 117
Re: New Big Integer library is finished
« Reply #81 on: October 13, 2024, 12:57:29 pm »
thanks Bart for the link, the Initialize and Finalize class operators look somewhat like the FreeBasic constructor and destructor with which I am familiar with, I haven't grasped the significance of the AddRef operator, when would you need it?
<edit>
I take it back, you are sill required to call New and dispose :(
so what's it good for then?
I mean, you still have to manage the allocation and freeing by "hand" :(
« Last Edit: October 13, 2024, 02:54:51 pm by srvaldez »

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is finished
« Reply #82 on: October 13, 2024, 03:40:59 pm »
I've just made version 4.63 available.
It fixes bugs to do with FPU exceptions on 64bit Raspberry Pi.

Bart

  • Hero Member
  • *****
  • Posts: 5467
    • Bart en Mariska's Webstek
Re: New Big Integer library is finished
« Reply #83 on: October 13, 2024, 03:50:25 pm »
I take it back, you are sill required to call New and dispose :(

No, you don't.
Look at this simple (non-sensical) code:
Code: Pascal  [Select][+][-]
  1. program test;
  2. {$mode objfpc}
  3. {$modeswitch advancedrecords}
  4.  
  5. type
  6.  
  7.   { TRec }
  8.  
  9.   TRec = record
  10.   private
  11.     FValue: Integer;
  12.   public
  13.     class operator Initialize(var aRec: TRec);
  14.     procedure Check;
  15.   end;
  16.  
  17. { TRec }
  18.  
  19. class operator TRec.Initialize(var aRec: TRec);
  20. begin
  21.   writeln('TRec.Initialize: before: FValue = ',aRec.FValue);
  22.   aRec.FValue := 666;
  23.   writeln('TRec.Initialize: after: FValue = ',aRec.FValue);
  24. end;
  25.  
  26. procedure TRec.Check;
  27. begin
  28.   if FValue <> 666 then
  29.   begin
  30.     writeln('TRec.Check: FValue = ',FValue,', Expected: 666');
  31.     Halt;
  32.   end;
  33.   writeln('TRec.Check: OK');
  34. end;
  35.  
  36. procedure X(var R: TRec);
  37. begin
  38.   writeln('Procedure X');
  39.   R.Check;
  40. end;
  41.  
  42. procedure Y(out R: TRec);
  43. begin
  44.   writeln('Procedure Y');
  45.   R.Check;
  46. end;
  47.  
  48. var
  49.   R: TRec;
  50. begin
  51.   writeln('Starting program');
  52.   writeln('Before X');
  53.   X(R);
  54.   writeln('After X');
  55.   writeln('Before Y');
  56.   R.FValue := 0;
  57.   Y(R);
  58.   writeln('After Y');
  59.   writeln('The end.');
  60. end.

It'll output:
Code: [Select]
C:\Users\Bart\LazarusProjecten\ConsoleProjecten>test
TRec.Initialize: before: FValue = 0
TRec.Initialize: after: FValue = 666
Starting program
Before X
Procedure X
TRec.Check: OK
After X
Before Y
TRec.Initialize: before: FValue = 0
TRec.Initialize: after: FValue = 666
Procedure Y
TRec.Check: OK
After Y
The end.

Notice that the initialization code is called for the global variable R, before we arrive at the begin of the main program.
Also notice that inside the procedure with the out parameter, R will be initialized correctly (we did set FValue to zero before calling the procedure).

Bart

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is finished
« Reply #84 on: October 14, 2024, 11:44:07 pm »
I've just made version 4.65 available.
This has a much faster ToStr function, and a little code tidying-up.
« Last Edit: October 15, 2024, 10:01:11 am by ad1mt »

srvaldez

  • Full Member
  • ***
  • Posts: 117
Re: New Big Integer library is finished
« Reply #85 on: October 15, 2024, 12:31:23 am »
👍😁

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is finished
« Reply #86 on: October 15, 2024, 10:01:28 am »
I forgot upload the latest bug fixed v18 unit_test... done now.

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is finished
« Reply #87 on: October 15, 2024, 10:08:13 am »
I've looked the earlier discussion about initialisation.
But the suggestions would involve rewriting a lot of code.
I've worked around the problem... I found the few functions that care about about the internal meta data, and they reset the metadata explicitly when required. Most functions do not care about the meta data; they can just ignore the fact that its trash and just overwrite it.
« Last Edit: October 15, 2024, 10:16:39 am by ad1mt »

srvaldez

  • Full Member
  • ***
  • Posts: 117
Re: New Big Integer library is finished
« Reply #88 on: October 15, 2024, 11:05:12 am »
hello ad1mt
my silly test with the factorial runs about 44% slower in the latest version than in version 4.61, at first I thought that it simply was Windows defender slowing it down and could still be the case, will test in Linux and see what happens
<edit>
tested in Linux and the times between 4.61 and 4.65 are almost the same with version 4.61 about 2% faster in the division test
even though on Windows I compile and run the test in a folder that is exempted from Windows defender, it's apparent that when the test is run it's being monitored by defender slowing it down considerably
« Last Edit: October 15, 2024, 11:48:05 am by srvaldez »

ad1mt

  • Sr. Member
  • ****
  • Posts: 327
    • Mark Taylor's Home Page
Re: New Big Integer library is finished
« Reply #89 on: October 15, 2024, 08:19:13 pm »
my SILLY test with the factorial runs about 44% slower in the latest version than in version 4.61
I'm also getting a 50% slowdown on the factorial 10000 calculation from v4.61 to v4.65, both on Widsnow 10.
I can't explain it, and its puzzling because I did not change the multiplication code.

Also, I have to object to you calling your factorial test silly... this test has found as many bugs as any of my tests!

 

TinyPortal © 2005-2018