New Big Integer library is almost finished

[ad1mt]

I've just made version 4.60 available.
This has a square root function that is 20x faster, and more bug fixes.

[srvaldez]

👍😁

[Ștefan-Iulian Alecu]

This has been a headache to go through. Besides the issues I left on your repo (that nobody else cared enough to notice), you really need to split up your code, as Bart said.

Separate procedures/functions would slow down the code.

Prove that. Show us some benchmarks. That's a nothing burger, since you should prioritize maintainability first and foremost, something which is really lackluster as of now. That also includes code formatting (which you can do on Lazarus using Ctrl+D, but I don't see you using that, judging by the lack of any lp* file). If you expect to release this in the public domain (which you can't, in the current form, I made an issue regarding that), it should ideally also be in a state where people in the future can, you know, study the code and see what it does.

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. It takes 5 minutes to learn how to add and commit files, at most. A sea of "Add files using upload" is as useless as no commit whatsoever, it describes absolutely nothing. Name your commits properly, since the name actually has a purpose...

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.

[srvaldez]

hello Ștefan-Iulian Alecu
The phrase "Never look a gift horse in the mouth" comes to mind, ad1mt released his code into the Public domain so it's not right to make demands
you can make a fork of his Git repo and make changes to your heart's content 
@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 
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

[Bart]

By "factored out", do you mean made into a source code macro?
Or do you mean made into a separate procedure/function?
Separate procedures/functions would slow down the code.

I mean functions/procedures.
It may slow down (a bit), but imagine that you need to alter that code just slightly (perhaps a bugfix or a faster algorithm), then you would have to alter it in many places.

Alternatively, if you always use the same variable names, then you can put the code for e.g. overlow checking in an include file and include that file everywhere you need that code.
I've done a similar thing in my utf8cpstrict unit, re-using the same piece of code in several functions (with a little macro help).
(Or define the pice of code as a macro, but the debugger really doesn't like it and compiler and runtime errors tend to show up in the wrong line.)

PS: I also saw you using labels and goto's simply to jum to the end of a procedure.
That's what you can use the Exit statement for.

I would really encourage you to try to improve readabilty and maintainability of your code.

Bart

PS. I wrote my own biginteger library, which allows in theory for up to 2^32 digits, implementing all basic functions (add, subtract, multiply, divide) using the logic we were told in primary school (so it does longdivision).
It's just a silly pet project (and really slow. In theory it can calculate 10000 factorial (and more), but it may take several days to calculate that, I never had the courage to test.).
It also does conversion to any base (well, base 2 to base 36).
And it is nullable (not really usefull, but hey, if you can add more complexity, why not?).

[MathMan]

@Ștefan-Iulian Alecu

"Prove that. Show us some benchmarks."
I can only subscribe to that. In the majority of cases, carefully splitting out a function, not only increases readability but contrary to expectation can increases speed too. Simply because the compiler can optimise better, putting variables to registers instead of keeping them on the stack etc. I think that is a learning experience everybody programming in a high level language has to go through.

@Bart
Maybe you should have added that, very probably, ad1mt himself will not be able to do anything with his program, in lets say 3-5 years, if it stays in the current form.

@srvaldez
As it is, if you read Ștefan-Iulian Alecus reply as a comment from an experienced programmer then he is simply spot on.

Beside that mp-arith isn't that fast on square roots. The algorithm used is the divide & conquer one described at several places in literature. But mp-arith implementation leaves out a lot of improvements - e.g. how to find the initial approximation for the first limb, etc. A decent Pascal implementation can be made ~10x faster up to around 5000 bit value sizes.

[Ștefan-Iulian Alecu]

hello Ștefan-Iulian Alecu
The phrase "Never look a gift horse in the mouth" comes to mind, ad1mt released his code into the Public domain so it's not right to make demands
you can make a fork of his Git repo and make changes to your heart's content 

Good thing the code ISN'T in the public domain. As I mentioned in https://github.com/ad1mt/Multi-Word-Int/issues/7, just calling something "public domain" without any license doesn't cut it in most legislations (mine included in the EU). You seem like the kind of programmer to call source-available proprietary projects "open source" just because you can see the source code (or at least a slice of it).

It isn't me making "demands", it's me telling the author that he should set some standards for himself if he wants to release this for the wider Pascal community to use (ESPECIALLY as public domain, I'll let proprietary codebases with millions of lines of code or projects made in 1984 slide).

I'll make a fork later on with my improvements, after reinstalling Lazarus and FPC. I just didn't feel like doing so at 11 PM local time. The code can definitely be improved, so I'll lead by example and make it faster as well, with the knowledge I have from using and making bignum libraries. I'll put money where my mouth is and have PRs for each issue I made.

[srvaldez]

UNIT Multi_Int;

(******************************************************************************)
// This code is public domain.
// No copyright.
// No license.
// No warranty.
// If you want to take this code and copyright it yourself, feel free.

but a license file stating the above would be good 

[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 

That might be an accident on my part. It should use 64bit ints with the 64bit compiler and 32bit ints with the 32bit compiler. I will investigate.

[ad1mt]

I would really encourage you to try to improve readabilty and maintainability of your code.

I agree 100% that the code needs tidying up.
I was intending to do that after I got the code working. Unfortunately, getting the code working has turned out to be much more difficult than I anticipated. Some of the algorithms are the most complex I have ever worked on.

[ad1mt]

PS. I wrote my own biginteger library, which allows in theory for up to 2^32 digits, implementing all basic functions (add, subtract, multiply, divide) using the logic we were told in primary school (so it does longdivision).
It's just a silly pet project (and really slow. In theory it can calculate 10000 factorial (and more), but it may take several days to calculate that, I never had the courage to test.).
It also does conversion to any base (well, base 2 to base 36).
And it is nullable (not really usefull, but hey, if you can add more complexity, why not?).

I would be interested to see your big integer code.
What do you mean by “nullable”?
By base conversion, do you mean as string output?

[Bart]

I would be interested to see your big integer code.

It's here.
It may require some additional units of mine (not sure), which can be found here.
Mind you it's not a serious implementation (although it works).

What do you mean by “nullable”?

It can contain the value NULL.

By base conversion, do you mean as string output?

Yep.

Bart

[ad1mt]

It's here.

Do you mind if I steal ideas from your code?
I'm especially interested in faster division, square root, power algorithms (or any that are significantly faster than my current algorithm).

Mind you it's not a serious implementation (although it works).

My library didn't start off as a serious implementation either. I was working on another unrelated bit of code, and suddenly needed integers bigger than 64bits. I looked for Free Pascal big int libraries, but they all had problems for me. Either I would have to have to redesign/rewrite all my code (e.g. mp_arith), or they did not work in a 32bit environment/cpu (FNX), or they were not portable because they used intel assembly code (several others). So I decided I could quickly knock out a very minimal big int library to solve the problem    however it took much longer than I expected.

Later on when it mostly working, I thought I would quickly tidy up my code, share it and save other people a lot of work. I started nearly 4 years ago, and I'm still working on the code now! Some people might say my library is still not a serious implementation, and in some ways I would have to agree! Its turning into a never-ending project!

[ad1mt]

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.
Right now, I'm 100% focussed on getting the code to work reliably.

[ad1mt]

hello ad1mt, silly tests often reveal bugs
the following silly test sets MV_i to factorial 10000, then in the following loop it divides MV_i by the sqrt(sqrt(sqrt(sqrt(sqrt(factorial 10000))))) 32 times, the result should be 1 but it's zero after the 17th divide

My apologies for suggesting there was bug in your code!
With the latest v4.60 you can now run the following code:

Code: Pascal  [Select][+][-]

1. program sqroot_fact_10000;
2. uses    sysutils
3. ,               strutils
4. ,               strings
5. ,               math
6. ,               Multi_Int
7. ;
8. var
9. n     :int32;
10. i,j,k :Multi_Int_XV;
11.  
12. begin
13. Multi_Int_Initialisation(3750);
14.  
15. // calculate factorial 10000
16. i:=1;
17. for n:=2 to 10000 do
18. begin
19.         i:= (i * n);
20. end;
21.  
22. j:= sqroot(sqroot(sqroot(sqroot(sqroot(i)))));
23. writeln('sqroot(sqroot(sqroot(sqroot(sqroot(i))))) = ',j.tostr);
24. end.
25.  

The resulting var j, now equals your original value.
Thank you for your feedback... it has prompted the discovery & fixing of many bugs that I had not discovered myself.