You can dynamically link libgmp on windows. That might be easier:

Do you know if the dynamic link escape hatch has ever held up in court? Last time I looked into it, the free software community had mixed opinions. In any case, giving GMP the boot alleviates any licensing concerns, makes the GHC build a little simpler, and allows users to create standalone executables. Is there any reason we shouldn't attempt to make integer-simple the default? -Greg

On 02/20/10 14:37, Ian Lynagh wrote:

There's also HIntegerByInt: http://www.haskell.org/pipermail/libraries/2007-August/007909.html although it would need to be changed to user lower level types etc.

that's true, (I wrote it), the current form uses a list-based implementation with a lot of recursion and I'd have to see how well that converts to some sort of array [at least I assume arrays are the only reasonable storage layout...]. I used a couple algorithms to make operations faster (at least multiplication -- I don't remember the details) so it might be useful code to pick up again. I have a bit of time now, if anyone's seriously interested, I could work on haskell integer code. As long as I had certain standards -what am I trying to accomplish (at least, performance-wise)? -what might be a good low-level format? (And is it important to strew unboxed ints all over the place, or is it fine to skip this and count on the optimizer?) -Isaac

On 02/21/10 13:14, Ian Lynagh wrote:

On Sat, Feb 20, 2010 at 02:56:53PM -0500, Isaac Dupree wrote:

...

-what am I trying to accomplish (at least, performance-wise)?

I think opinions are divided on this.

Performance with word-sized Integer's is definitely important.

This is true. We could start a discussion on the Libraries list -- although I'm sure it would also not reach a clear conclusion. We could try to find out how large Integers get, in practice, in existing Haskell code (this may be difficult to find out). We could make sure there's a good non-builtin-to-ghc GMP-binding library (Is there one? Is it even possible yet, in a way that doesn't conflict with GHC's builtin GMP?). Then people would have a place to turn if they need GMP's performance for something particular.

...

-what might be a good low-level format? (And is it important to strew unboxed ints all over the place, or is it fine to skip this and count on the optimizer?)

I think relying on the optimiser is OK, but don't forget that you don't have the standard (+) etc.

oh okay, interesting. I think I'd best start by finding out where integer-simple lies in the dependency tree. -Isaac

On 02/21/10 14:18, Daniel Fischer wrote:

Am Sonntag 21 Februar 2010 19:56:54 schrieb Isaac Dupree:

...

We could try to find out how large Integers get, in practice, in existing Haskell code (this may be difficult to find out).

I suspect (just guessing...) that a more reliable way to find out is to instrument integer-simple to report the sizes of integers it handles. For example, if you use Rational, (even toRational/fromRational), you might be handling Integers somewhat larger than you thought you were. And this could also report on how often the integers get that large. (Also it's probably only tough operations like multiplication and division that we need to worry about for large numbers. It's easy to get linear-time addition, etc. Incidentally, for operations like Large Number plus or minus Small Number, it's possible to use a representation that has laziness and sharing to achieve amortized O(min(m,n)) time. Which is a nice property... which I believe I implemented in HIntegerByInt... but there are probably disadvantages to doing it this way too.) -Isaac

Isaac Dupree:

...

We could try to find out how large Integers get, in practice, in existing Haskell code (this may be difficult to find out).

Daniel Fischer wrote:

Just as a data-point, my code rarely exceeds 128 bits (at least, beyond that performance isn't so important anymore).

And Daniel, who is part of the Project Euler team, uses large integers far more than most people. As another data point, Python has also re-invented the GMP wheel, likely for the same licensing reasons. They have been using a simple implementation of Karatsuba multiplication for years. I have never heard of anyone complaining about it. Furthermore, they currently use naive multiplication and don't even bother with Karatsuba for less than about 2000 bits on most recent platforms. Regards, Yitz

I wrote:

...

As another data point, Python has also re-invented the GMP wheel, likely for the same licensing reasons. They have been using a simple implementation of Karatsuba multiplication for years. I have never heard of anyone complaining about it

Greg Fitzgerald wrote:

Looks like they swapped out their integer implementation for Python3

Interesting! This will be new in Python 3.2 - the first changes in many years. It's not exactly swapped out, but there are many changes. At first glance, it looks like better 64-bit support, a new division algorithm via floating-point, a new exponentiation algorithm using a 5-bits-at-a-time trick in some cases, optimized Read and Show instances (pardon the expression), a few other things. A lot of the new stuff seems to be from HAC. As before, everything is fully explained in expository comments inside the code, with references; a worthwhile read. Multiplication is still the same basic idea though - naive up to about 2000 bits, followed by just Karatsuba and nothing more. Thanks, Yitz

On 02/20/10 14:11, Greg Fitzgerald wrote:

...

You can dynamically link libgmp on windows. That might be easier:

Do you know if the dynamic link escape hatch has ever held up in court? Last time I looked into it, the free software community had mixed opinions.

GMP is under LGPL, which is designed for this very purpose: to allow proprietary code to link to it as long as it is easy to replace the Free code with a different version of Free code (for example, by replacing a dynamic library). Is there any reason to doubt the FSF's efforts? (Note that LGPL doesn't work as well for Haskell code as for C code because Haskell compilers tend to do a lot more inlining; but GMP is C code.)

In any case, giving GMP the boot alleviates any licensing concerns, makes the GHC build a little simpler, and allows users to create standalone executables.

However the 3-clause BSD license is obviously at least somewhat simpler for lawyers.

Is there any reason we shouldn't attempt to make integer-simple the default?

If you know that none of your code or libraries are using any particularly large integers [how would you know, though?], then it should perform alright. GMP, however, is the result of years of work making operations on integers large and small be reasonably performant -- work that Haskell would be foolhardy to duplicate, I'm guessing. (Depending what our standards are... Is reasonable performance for multiplying integers less than 320 bits long, say, good enough? What happens when someone wants state-of-the-art performance? Is a nonstandard-Integer-type GMP-binding sufficient for these uses?) -Isaac