Big Integer Math include file

[Johannes]

After Dan's challenge (the division of the two ridiculously large integers) I started working on proper Big Integer functionality and I've had it sitting on my hard drive for some time now. I've documented it somewhat, added a test and example program, and here it is for those of you who, like me, can't do with just Quad integers.

Big Integers are what the name says: big. In thinBasic the largest integer data type is Quad: signed 64-bit integers. Although the numbers you can describe in those 64 bits are huge, sometimes they're not huge enough. Which is where BigInt comes in.

The size of a BigInt is limited by only three things: (1) your computer's memory, (2) thinBasic's "limit" of 2GB for a string, and (3) your patience. Make no mistake, number three could be the killer. This is written in straight thinBasic, not assembler, and although you will get a result, you may have to wait for a while. But do not despair: calculating the 13th root of a 200-digit number (included as an example) takes 0.0542 seconds on my computer.

I've added as many functions dealing with integers as I could come up with. I haven't gone the way of stuff like Graham's Number but if you want to know the two millionth Fibonacci number, or the factorial of your birthday, here's your chance.

The source code contains minimal comments (basically a short description of the function) and that's it. I did not document the code itself, mainly because I "get" the stuff that I programmed but also because I would be giving a course in mathematics and binary arithmetic if I did. Not for free Chester. ;)

Anyway, see the attached and the small documentation file. (Had to zip that because I got an upload error for the file.) If you have some questions about how to use it all, have a look at the test and example scripts. If that doesn't help you, ask here and you may receive.

Have fun with it. I did.

[Johannes]

I've put in an Easter Egg.

The people most likely to find this Easter Egg are code browsers and people with thick fingers (ie. people making typing errors). If you find the Easter Egg let me know what you think of it. If you understand what it is, that is. ;)

I'll give you one small hint (completely useless, so I might as well give it), and because 13 is my favourite number, this is it:


13 is 13 long

[kryton9]

Can't wait for someone to solve the Easter Egg.

Here is the only thing, I can find.
http://primes.utm.edu/curios/page.php/4294967295.html

Another thing that I saw that I have no idea is "42_13"
42 the answer to the universe and everything alongside your favorite number 13 :)

[danbaron]

I downloaded all of your stuff, Johannes.

Boy, you did a lot of work.

I don't understand it, but it looks good to me.

I like the 13th root calculation.

And, I like the test of all of your functions. That test code is really something.

And, I like your documentation. Some of those functions, like, BigInt_Nrt, look amazing.

Humbly,
Dan ;):p

[Johannes]

Another thing that I saw that I have no idea is "42_13"
42 the answer to the universe and everything alongside your favorite number 13 :)
That's in the test function. And of course that's straight out of Douglas Adams' Hitch-Hiker's Guide to the Galaxy. :D

When they find out the Answer to Life, the Universe and Everything is '42' they build Earth (the planet) to find out what the question is. In the end they try to find the question using Scrabble tiles. The tiles run out but what they get is:

What do you get if you multiply six and nine?

Someone, later, suggested that if they had had enough tiles the complete question would have had after that: "in base thirteen".

It's just a test case. It's not the Easter Egg. The Easter Egg is in the main code and the hint is of no help at all finding it. Only when you've found it will you understand what the hint means. ;)

[ErosOlmi]

I too do not understand the details but this is a huge and great work !
Thank you very much.

It also seems perfect for a compiled thinBasic module that would burst execution speed by a factor of 100 or even more.

[Johannes]

Otherwise some poor soul will have to go through the code line by line. Here is a proper hint and it should lead you directly to the Easter Egg.


all your base IS belong to us

And that's all I'm going to say about it. ;)

[Johannes]

Spotted a typing error in the main script but because thinBasic is very forgiving it doesn't affect anything. Line 983 (in BII_mul) has the +$NUL outside of the CVDWD bracket, which is incorrect.

Originally the line reads n=CVDWD(Mid$(b,i,3))+$NUL but this should be n=CVDWD(Mid$(b,i,3)+$NUL). (Changing it to n=CVDWD(Mid$(b,i,3)) would probably also work.)

For the less adventurous the corrected include script is below.

[Petr Schreiber]

Hi Johaness,

thanks a lot, I am going step by step and the library looks very good to me so far.
I was confused at first, but then I realised I cannot use passed strings directly, but need to use the BigInt_FromString and BigInt_ToString.

I found one more typo:


Function BigInt_Abs(a As String) As String
Return BigIntPos(a)
End Function
should be:


Function BigInt_Abs(a As String) As String
Return BigInt_Pos(a)
End Function
Petr

[Johannes]

Petr,

Thanks for the input. I should also have put the aliases in the test script. Forgot all about ABS because I started out with Pos and Neg.

Seeing that you have been looking at the source closely, have you found the Easter Egg? ;)

[Johannes]

I was confused at first, but then I realised I cannot use passed strings directly, but need to use the BigInt_FromString and BigInt_ToString.
Correct. I thought about making all functions "auto-recognise" but I found it just too much trouble. Also, for a true auto-recognise I would want it to work with numerical variables as well and I just couldn't get the Variant bit to work. So I stuck with the internal representation.

You can get strange results if you try to print (to Console) internal BigInt strings directly, without using BigInt_ToString. Look out for that.

That would also be a problem because if conversion from ASCII to internal is automatic, you'd expect the reverse to be true as well: automatic conversion from internal to ASCII when printing. But for that I would have to make this a proper thinBasic module and if I understand it correctly I would have to use an SDK, and there isn't one for thinBasic, only for PowerBasic and FreeBasic.

I am thinking of doing the low-level functions (BII_add, _sub, _mul, _mli, _div, _dvi) in assembler. That should speed things up enormously. If I'm going to do that I'll make some test cases first to check the speed in pure Basic so I can compare it with the assembler version. I'm not guaranteeing anything because I am very busy with work right now and I'm also thinking about writing high-precision (128-bit) floating-point functions.

[kryton9]

Otherwise some poor soul will have to go through the code line by line. Here is a proper hint and it should lead you directly to the Easter Egg.


all your base IS belong to us

And that's all I'm going to say about it. ;)

That clue is a play on a very famous line from the video game Zero Wing. The line in the game is "All your base belong to us", this was broken English translation from the original in Japanese.

I hope perhaps this trivia will help someone spot the Easter Egg. I'll keep looking myself.

[Johannes]

The line in the game is "All your base belong to us", this was broken English translation from the original in Japanese.
The line from the video game is not quite as you quoted it here. ;)

[Johannes]

BigInt_Nrt may give incorrect results if the power is larger than or equal to &h80000000 (two billion and a bit). I have a fix for this so this is temporary.

BigInt_Nrt2 may give incorrect results if the power is 34. I will change the check within the function.

BigInt_Fac, BigInt_Prm and BigInt_Cmb may give incorrect results if N is larger than or equal to &h80000000.

All problems arise from the fact that I do not have a native unsigned 64-bit integer data type in thinBasic. If (if!) I change the internal functions to assembler (in this case I'm talking about BII_mli) this problem will be solved. As stated, I can correct BigInt_Nrt without having to go to assembler, but the three billionth Fibonacci number is off-limits for the time being...

[Johannes]

Corrected the bugs in BigInt_Nrt and BigInt_Nrt2 as mentioned above, and two other minor bugs (in the string-to-BigInteger conversion). See attached file.

I'm stopping further development on BigInt in thinBasic. I've begun converting these functions to a thinBasic module in PowerBASIC and right now I'm at the point that I'll have to start porting the internal (BII_) functions. It's half past midnight and I have to go to work in less than eight hours... :p

As soon as I have something that's testable I'll make a posting over in the new module section.