The best cross platform (portable) arbitrary precision math library

views:

537

answers:

+16 Q:

The best cross platform (portable) arbitrary precision math library

+3 A:

I've not compared arbitrary precision arithmetic libraries to each other myself, but people who do seem to have more or less uniformly settled on GMP. For what it's worth, the arbitrary precision integers in GHC Haskell and GNU Guile Scheme are both implemented using GMP, and the fastest implementation of the pidigits benchmark on the language shootout is based on GMP.

Richard Barrell 2010-04-02 23:04:36

Thanks! ^___^ Nice information!

Siu Ching Pong - Asuka Kenji 2010-04-03 02:04:36

+3 A:

Overall, he fastest general purpose arbitrary precision library is GMP. If you want to work with floating point values, look at the the MPFR library. MPFR is based on GMP.

Regarding native arbitrary precision support in other languages, Python uses its own implementation because of license, code size, and code portability reasons. The GMPY module lets Python access the GMP library.

casevh

casevh 2010-04-03 07:56:21

Thank you for your response! You mentioned "code portability". Could you please explain what the problem is? I thought that GMP is portable and is supported on major platforms...

Siu Ching Pong - Asuka Kenji 2010-04-03 12:46:42

"code portability" is not the same as "supported on major platforms". Python uses a simple implementation that makes very few assumptions about the behavior of the C compiler so the same code can compile on almost any C compiler. GMP uses more code (C and highly-tuned assembly) that make GMP faster but also make more assumptions about the behavior of the C compiler and assembler. For example, GMP is not well supported by the Microsoft Visual Studio compilers. There is a GMP fork called MPIR (www.mpir.org) that does support Microsoft's compilers.

casevh 2010-04-03 16:53:53

I see. That means the Python implementation is more like ANSI C while the GMP implementation uses __asm tricks... Thank you for your explanations.

Siu Ching Pong - Asuka Kenji 2010-04-04 04:01:13

+3 A:

GMP is the popular choice. Squeak Smalltalk has a very nice library, but it's written in Smalltalk.

You asked for relevant books or articles. The tricky part of bignums is long division. I recommend Per Brinch Hansen's paper Multiple-Length Division Revisited: A Tour of the Minefield.

Norman Ramsey 2010-04-04 04:48:21

Thank you for your link to the paper! Yes, I agree that division is the most tricky part. I knew how to do division by hand using "paper-and-pencil methods" long time ago :-), and thus the same method can be applied to a decimal string of `char *` (each `char` representing a decimal digit) or an `int *` of BCD string (each `int` representing 4 / 8 / 16 BCD digits). However, I wonder if real-world production level libraries mimics the "paper-and-pencil method", as it is too slow.

Siu Ching Pong - Asuka Kenji 2010-04-04 06:23:38

To see why, let's imagine how it runs for `100,000,000,000,000,000 / 333,333,333,333`: The first step is to compare `100,000,000,000` with `333,333,333,333`. Because the former is less than the latter, the calculation simply moves to the next digit. The second step is to find the quotient of `1,000,000,000,000 / 333,333,333,333`, this involves either a trial-and-error multiplication of `333,333,333,333 * 1` (and `* 2`, `* 3` and `* 4`), or doing successive subtractions in a loop. Do you see how slow it is? I believe that more efficient algorithms exist.

Siu Ching Pong - Asuka Kenji 2010-04-04 06:36:26

@Sui: Brinch Hanson shows how you can reduce the trial-and-error method to at most two trials. It's really very impressive.

Norman Ramsey 2010-04-04 19:51:07

@Norman: Okay, let me have a more detailed look to the paper. Thank you!

Siu Ching Pong - Asuka Kenji 2010-04-05 02:08:59

ansaurus

tags:

views:

answers:

The best cross platform (portable) arbitrary precision math library

related questions