BigInt library, full-featured & free?

[idog]

Hi all,

You may have heard about Google Codejam, the programming contest now under way. In its qualification round, it was heavily hinted that in the following rounds, Big Integers (= with arbitrary number of digits) will be considered a reasonable requirement from programmers of all languages. Be it a "political" decision or not, I was wondering whether there's such a library specifically for Lazarus.

In the forums I found two references for BigInt: my own (when I was writing a simple +/-/* library) and this one: http://delphiforfun.org/programs/Math_Topics/Pell%20and%20Continued%20Fractions.htm which is only free for non-commercial purposes. Anyone knows of another?

I also found this for Delphi: http://sourceforge.net/projects/bigint-dl/ , but I didn't get to test it yet, and the comments appear to be non-english and I can't figure them out.

Thanks!

P.S. Not that I'm too optimistic about my chances in this contest ;-) but all in good fun.

[theo]

I don't know how good or complete this is, but it's a Freepascal project:
http://forge.lazarusforum.de/projects/show/gnurz

[Laksen]

I stumbled over the same problem, and I tried using uBigIntsV3, but it proved to be too much work since I needed some sort of sorting. Then I did it in Matlab with some lousy toolbox which proved to be even more work

So just earlier today I too started to write my own unit

[idog]

I don't know how good or complete this is, but it's a Freepascal project:
http://forge.lazarusforum.de/projects/show/gnurz

Thanks Theo, I'll take a look at it, though I'll have to rely on the German of Google Translate for this ;-)

I stumbled over the same problem, and I tried using uBigIntsV3, but it proved to be too much work since I needed some sort of sorting. Then I did it in Matlab with some lousy toolbox which proved to be even more work

So just earlier today I too started to write my own unit

Good cautionary tale there :-) If you come up with some nice code, don't forget to publish it here for the rest of us!


[Edit:] Of course, if someone wants to know how I implemented addition, subtraction and multiplication of Big Integers, you can download/use the code at http://www.idogendel.com/docs/projects/BigInt.zip, but mind you it's more of a simple demo, not something you'd use in a serious application.

[bflm]

Hi all,

You may have heard about Google Codejam, the programming contest now under way. In its qualification round, it was heavily hinted that in the following rounds, Big Integers (= with arbitrary number of digits) will be considered a reasonable requirement from programmers of all languages. Be it a "political" decision or not, I was wondering whether there's such a library specifically for Lazarus.

FYI: FPC as of v2.4.0 fully supports GMP: http://wiki.freepascal.org/gmp

[Leledumbo]

I use NX - Numerics, this one is great.

[Wodzu]

P.S. Not that I'm too optimistic about my chances in this contest ;-) but all in good fun.

How the contest went? ;-)

I do not think that such library is needed in Google Code Jam. Solving such problems is often a case of trick rather then pure mathematical operations.

[Laksen]

P.S. Not that I'm too optimistic about my chances in this contest ;-) but all in good fun.

How the contest went? ;-)

I do not think that such library is needed in Google Code Jam. Solving such problems is often a case of trick rather then pure mathematical operations.

One problem consisted of calculating GCDs of numbers up to 10^50. They even wrote "64 bits will not save you. You have been warned."

The qualification went ok for me, ended up with 53 points out of 99 because of many small mistakes. But well..

[idog]

Oops, some catching up to do  

FYI: FPC as of v2.4.0 fully supports GMP: http://wiki.freepascal.org/gmp

Didn't know that, thanks. This is what they use in PHP, no?

I use NX - Numerics, this one is great.

Excellent, I'll check it out as well!
[Edit:] Hmmm... does it have some sort of a manual, or do I have to figure it all out from the source files?!

P.S. Not that I'm too optimistic about my chances in this contest ;-) but all in good fun.

How the contest went? ;-)

I do not think that such library is needed in Google Code Jam. Solving such problems is often a case of trick rather then pure mathematical operations.

One problem consisted of calculating GCDs of numbers up to 10^50. They even wrote "64 bits will not save you. You have been warned."

The qualification went ok for me, ended up with 53 points out of 99 because of many small mistakes. But well..

Like Wodzu said, there's usually a trick so I assumed the "64 bit" remark meant there's some char-by-char manipulation that will solve the problem. This is exactly what ruined this question for me,  looking for something that wasn't there. Well, that and the fact that I suck at math  

But I wasn't under pressure to solve it, because it's just the qualification stage and I got the other two right (66 points). BTW, There's some interesting info about contestants and languages at  http://www.go-hero.net/jam/10/languages/0, and if anyone wants to see my makeshift solutions and follow my impeding humiliation on the next rounds  , see http://www.go-hero.net/jam/10/name/idog...

[Wodzu]

I think that it can be solved using char manipulation, but google suggests another approach:

http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=1

Personally I think that it is a bad idea to include some "non-standard" things (big numbers) to the problem solving contest.

[Leledumbo]

Hmmm... does it have some sort of a manual, or do I have to figure it all out from the source files?!

Not really, you can learn from its examples.

[idog]

Personally I think that it is a bad idea to include some "non-standard" things (big numbers) to the problem solving contest.

Totally. Especially considering the fact that the vast majority of contestants write in C++, not Java or Python that are more BigInt-friendly. Maybe it's some conspiracy by Google to weed out older languages they don't like 

Hmmm... does it have some sort of a manual, or do I have to figure it all out from the source files?!

Not really, you can learn from its examples.

*Sigh* 

[Wodzu]

Personally I think that it is a bad idea to include some "non-standard" things (big numbers) to the problem solving contest.

Totally. Especially considering the fact that the vast majority of contestants write in C++, not Java or Python that are more BigInt-friendly. Maybe it's some conspiracy by Google to weed out older languages they don't like 

If by "older languages" you mean Pascal than I fully agree  However this is not the case of C++ users. They had upper hand in such contest since years! Just take a look at their boost library. It has even a GCD function out of the box  And what we Pascal users do have instead?

[Leledumbo]

Just take a look at their boost library. It has even a GCD function out of the box And what we Pascal users do have instead?

Just like a Haskellian ever said to me, it's libraries that form a language.

We have nice cross-widgetset GUI library (LCL), we have out of the box XML, JSON, images, etc. handling out of the box (FCL), and we have cross-platform basic library (RTL). And what do C++ users have out of the box?

I ever asked FPC developers to add multiprecision integers and floating points, but they said it would add complexity to the compiler (for building it, especially from users point of view) and slows it down. Such a functionality should be provided by a library. I agree with that, because I see what happens to GCC 4.5.X (GMP, MPFR, and MPC are required to build it).

[Wodzu]

I did not wanted to whine or anything

Its just I miss a good data structures and math library. We haven't had that library in Delphi's days and we do not have it now 

There should be some project started where people could contribute...