New Big Integer library is almost finished

[ad1mt]

I see that you changed from using 64-bit words to using 32-bit words, as far as I tested there are no problems 

What has changed that makes you think that?
I worried I might have changed something accidentally.
Thanks.

[ad1mt]

Besides the issues I left on your repo (that nobody else cared enough to notice)...

I'm also a big fan of plain text files for documentation.
There was a plain text documentation file all along... the problem was I accidentally put it in the Demo folder. I have moved it to the main folder.

[srvaldez]

ad1mt
in my previous test that I posted, I had to Multi_Int_Initialisation(1851) but to then divide the factorial(10000) 32 times to get 1 I now have to Multi_Int_Initialisation(2*1851)
factorial(10000) has 35660 decimal digits, dividing that by log10(2)*64 = 1851
10000! works with size of 1851 but to divide as in the test above it needs to be twice that, that's why it made think that you were use 32-bit words

[ad1mt]

I am puzzled by how fast Mparith computes square roots, I have toyed with my own multi-precision floating point and Mparith  computes square roots much faster than mine

I'm also very impressed by the speed of mp_arith, the division algorithm is also very fast.
Even with my new "Babylonian" square root algorithm, mp_arith is still extremely faster (that does not sound like correct English, but I think you will still understand).

[Bart]

P.S.: Please learn Git. It's painful seeing "Add files using upload" on GitHub. This isn't OneDrive or Google Drive, so learn the platform. P.P.S: It doesn't seem like you're following semver whatsoever (MAJOR.MINOR.PATCH). At least just do MAJOR.MINOR and treat this as an increasing number. Enough for now.

Once the code has stabilised and is bug free, I'll be happy to take ideas for improving readability and regarding Git.

I would strongly advise you to reconsider.
Using git (github) as intended makes it possible to easily see what changes you made.
Which is especially important if it turned out you introduced a new bug (which is inevitable) and only find out later.

It really isn't that hard.
Your basic workflow (assuming you are the only one with commit rights) will be something like:
- do work
- > git commit -a -m "your commit message"
- > git push

It is recommended to commit often, so after each relevant change.

Bart

[ad1mt]

PS: I also saw you using labels and goto's simply to jum to the end of a procedure.

Quoting from https://www.ee.ryerson.ca/~elf/hack/realmen.html

Real Programmers aren't afraid to use GOTOs.
Real Programmers can write five page long WHILE loops without getting confused.
Real Programmers don't need comments: the code is obvious.
 

[ad1mt]

Using git (github) as intended makes it possible to easily see what changes you made.
Which is especially important if it turned out you introduced a new bug (which is inevitable) and only find out later.

I've used source control systems, and know benefits of change/source management.
I am doing this on my hard drive... you just can't see it. Every time I make a change, I create a new copy of my source file with the version number in the filename. If I needed to, I can go back to v3.9 dated June 2021.

[ad1mt]

Someone here might be able to help me with one of the biggest problems I'm having...
When the compiler creates a procedure call with a var or out parameter of type big int, the procedure needs to initialise the big int parameter but only if it has not already been initialised.

If I unconditionally initialise the var, then I risk losing critical info contained in the big int var (e.g. the size of the integer array). This has been the cause of many of the bugs I've had.

So what I would like to do is detect when a var has not been initialised.

The problem is that an uninitialised var, when passed to the procedure on the stack, has random values in the fields. And this means if write code that assumes the fields have meaningful values, then the program might crash or fail whenever those random values has sensible looking but incorrect values by chance. As the stack memory gets re-used during the running of the program, random values that look sensible will happen more often than you might think.

One idea I had was to add a check-sum/hash field, which has a value that is derived from the other field values. If the checksum/hash did not match the other field values, then the code would know that the big int was unititialised. But even then, there is minute chance, that this could fail.

Can anyone think of a way of detecting uninitialised vars with 100% reliability?
Thanks.

[MathMan]

I am puzzled by how fast Mparith computes square roots, I have toyed with my own multi-precision floating point and Mparith  computes square roots much faster than mine

I'm also very impressed by the speed of mp_arith, the division algorithm is also very fast.
Even with my new "Babylonian" square root algorithm, mp_arith is still extremely faster (that does not sound like correct English, but I think you will still understand).

Now I feel compelled to respond. MP-Arith isn't that fast - as I undertood it the goals of this library were different.

You already possess a very efficient division routine - remember https://forum.lazarus.freepascal.org/index.php/topic,65158.56.html. When I benchmark that against MP-Arith for the problem in the current context (dividing an 1851 64 bit limb value by a 58 one - representing 10000! / 32nd root of 10000!) then I get the following figures

 - MP-Arith basecase: 53380159 clock cycles
 - MP-Arith efficient: 39196864 clock cycles
 - lDivMod basecase: 3498345 clock cycles

Of course individual figures will vary for your computer but the ratios will probably remain.

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.

Cheers,
MathMan

[srvaldez]

ad1mt
couldn't you check for zero pointer and only initialize if the pointer is zero?
it goes without saying that you would initialize pointers and set a freed pointer to zero
but a constructor/destructor would be ideal, I just don't know how to do that in freePascal

[Bart]

I've used source control systems, and know benefits of change/source management.
I am doing this on my hard drive... you just can't see it. Every time I make a change, I create a new copy of my source file with the version number in the filename. If I needed to, I can go back to v3.9 dated June 2021.

Doing it that way makes absolutely no sense to me at all.

Bart

[ad1mt]

Even with my new "Babylonian" square root algorithm, mp_arith is still extremely faster (that does not sound like correct English, but I think you will still understand).

Now I feel compelled to respond. MP-Arith isn't that fast - as I undertood it the goals of this library were different.

Another way to think of it is... my library is extremely slower!   

Ease of use, not speed, is my primary goal. However, I would still like it to be as fast as possible, without making the code so complex that I can't remember how it works 4 weeks after I wrote it.
Suggestions for algorithms are very welcome, but the suggestion must come in the form of program code. My maths is not good enough to translate from a very obscure mathematical equation.

Here's an example of the type of problem one can hit... when implementing the "Babylonian" method for square root, I got the method from wikipedia. The mathematical equation was so easy, even I could understand it. Although it was not stated explicitly, the method assumed Real/Float variables. The significance of implementing the algorithm with integers did not hit me until I found that certain values caused the code to go into an infinite loop.  What was happening was when the value was just about settle down to a constant (in Real/Float vars), with integer vars, the value instead flip-flopped between two small values. It only did this intermittently with some values.

[ad1mt]

I have just made version 4.61 available.
It has a critical bug fix in the division function for the Multi_Int_XV type.

[ad1mt]

Doing it that way makes absolutely no sense to me at all.

It means I don't have to learn the quirks/bugs of each fashionable source control system that comes along every few years.

I'll give you a couple of examples...

The first one I used was SCCS, which comes with Unix. I worked for several days on some code. I had put a lot of work into it, so I immediately made the source file read-only, so that I could not delete the file by accident.

I checked-out the file from sccs, and it overwrote the file I had been working on, and I lost all my work. It turns out, that sccs treats read-only files as write-able, and write-able files as read-only! This behaviour was not obvious from the manual. That was the point I abandoned sccs.

Then it was suggested to me that I use CSV instead. Having had my fingers burnt once, I closely read the small print in the documentation first. It turned out that CSV would allow multiple programmers to check out a file, make changes, then allow them to check the same file back in with the same new version number, without any warning.  CSV claimed to be able resolve any code clashes automatically!  This claim was obviously nonesense, so I refused to use CVS.

At that point I abandoned source control software, and used a manual source control method with every change going into a separately named file.

If anyone else volunteered to help on this project, I would learn how to use Git. But until that happens, I will use my own method, because I can guarantee 100% that it works.

I am sick and tired of badly designed software that does not work properly. I'm not suggesting Git is badly designed. But I am now very wary of trusting any source control system with code that I have spent literally years working on.

[ad1mt]

Can I ask...
1. Has anyone used my library, or planning to use it, in your own software?
2. If so, what are you using it for?
Just curious.
Thanks.