LICENSE: BSD3 (or also similar, like GHC, etc.) INITIAL AUTHOR: Isaac Dupree <id@isaac.cedarswampstudios.org> What is this? It is a reimplementation, in Haskell, of the Integer type that Haskell provides in its Prelude. It is designed in mind of being actually usable as the implementation of that type, for compilers. It is also a module that exports a working Integer type. It is in terms of only basic Prelude functions, [], and Int. It is NOT a purely inductive definition, because Int is much faster than a purely inductive definition would allow, and nevertheless often easier to come by (more portable, license-wise, size-wise, nuisance-wise...) than GMP or other C bignum libraries. /========= darcs repo: http://isaac.cedarswampstudios.org/2007/HIntegerByInt I'm rather proud of it in a silly way: I have run into bugs in *all* major Haskell implementations I tried it with, while testing it (see COMPILERS section). Reminds me somewhat of GMP triggering compiler bugs actually:) All the implementation and documentation is currently in one file "IntegerInTermsOfInt.hs", except for three auxiliary modules for testing, where CheckIntegerInTermsOfInt is a Main module that uses QuickCheck. I have copied some of that documentation here. From here, I offer it to anyone who is interested it using it and will try to help as needed, but I'm not likely to search out compiler internals myself just to try it in them. I didn't give it a version number or Cabal file because it is completely useless on its own, as a library, in view of Prelude already providing a very good Integer. \========== SPEED: It is not too slow on small numbers (smallish constant - much larger than for Int of course), not too slow on medium-size numbers (which I've been testing it with), and not too slow on large numbers (asymptotically; karatsuba multiplication, O(n^1.585) is used to split up large numbers, and division by large numbers uses multiplication and Newton's method). Also see BUGS for the speed of 'show'. CORRECTNESS: It seems to be correct, after a fairly thorough million-iteration QuickCheck in GHC plus a lot of quickcheck testing using debugging-"Int"s that tell you when they overflow and have (minBound,maxBound)=(-31,31). Each of these caught an incredible number of bugs, which is why I am inclined to trust them. Unfortunately, most Haskell implementations are somewhat incorrect - see COMPILERS. Also see CAVEATS(c) for *very* large numbers. CAVEATS: a- It is obviously much slower than GMP. (although I don't know if the penalties for calling primitive/foreign functions counterbalance that for small numbers.) b- It assumes that Int operations are fairly fast, although it doesn't tend to waste them that much (e.g. it uses `quotRem` when it needs both, which is almost always). c- It is expected to break when handling values with magnitude greater than around ( (maxBound::Int)^(maxBound::Int) ). (just like GMP. Probably the assumption is that you'll run out of memory at the same time, or that the operations will take SO LONG, so no-one cares. Prelude.length will (relatedly) also break at this point.) USAGE AS NATIVE INTEGER: Completely untried so far (search file for INTERESTING to customize). The algorithms are quite separable from the newtype Integer and its instances, and Bits, Ix... parts can be separated out too (in which case a proper export list would have to be made for the algorithm functions, which might hinder optimization a little, if assuming separate compilation...). See <http://www.haskell.org/ghc/docs/ latest/html/libraries/base/Prelude.html#t%3AInteger> for all things GHC's Prelude.Integer be an instance of, including Typeable? Data? NFData? PrintfArg? Typeable? Random? This is also a purpose CPP could be useful for, to define (#define?) quotRemDInt and such type-specific things, conditionally on how this Integer-implementation is being used. The internal format is (currently) a list([]) of Ints in base "intLargeBase", least-significant "digit" first (negative x is represented by negating all elements of the list that represents positive x) (No most-significant zeroes are allowed (so zero is represented by the empty list, for example)) ("intLargeBase" is customizable, although there is an optimal value for any particular size of Int, and a limit based on the Int's size) TODO/BUGS: COMPILERS. a- There is one WORKAROUND so Hugs can compile it and two for nhc/yhc. Even so, I refused to keep a third workaround for N/Yhc, but that is for a nyhc bug that Neil thinks should be reasonably fixable. b- though extensively QuickChecked in GHC, Hugs occasionally fails QuickCheck, but when the particular example is run in Hugs, it gives the correct answer! I think Hugs is buggy. (Hugs Version September 2006) c- ghc -O -fvia-C may miscompile "quotRem x (some power of two)". (ghc trac#1603) If QuickCheck fails badly on you, try adding -fasm. d- Beware testing in interpreters - some (at least GHCi 6.6.1) will default to Prelude.Integer even if the module has "default ()". Make show faster than O(n^2), e.g. see http://darcs.haskell.org/packages/base/GHC/Num.lhs ? ...but converting that, it seemed altogether slower than the current [and there is more in IntegerInTermsOfInt.hs] Isaac
Hello Isaac, Friday, August 10, 2007, 7:56:25 PM, you wrote:
The internal format is (currently) a list([]) of Ints
my first thought is that using list of large chunks as in lazy bytestrings may improve efficiency in future -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
BTW: I estimate that it took me about two solid weeks of time, more than I had originally intended to spend :) I think using CPP will prove important, but makes it harder to test in Hugs... should I use Cabal if I want to use Hugs with haskell+cpp code? Bulat Ziganshin wrote:
Hello Isaac,
Friday, August 10, 2007, 7:56:25 PM, you wrote:
The internal format is (currently) a list([]) of Ints
my first thought is that using list of large chunks as in lazy bytestrings may improve efficiency in future
My first aim is portability, as Yhc demonstrated it could be helped by a portable Integer that is usually within the size of an Int. I hated the idea that Int was being hackily used in place of Integer :) For very large numbers, that (i.e. unboxed-array equivalents) would be more memory- as well as possibly speed efficient. Almost all the operations in my implementation are defined inductively, not knowing the exact size of the result in advance, so that would be somewhat different. One *interesting* aspect of the format I used is that unbalanced-size addition (and .&., .|.) are on average O(min(m,n)), because the tail of the list can stay the same except for carrying. e.g. 3 + 2789234879453889743578934589893459834589345898945378974358798973487... is about as fast as (3 + 4). (Note that this asymptotic behavior will only actually be true in my implementation when my version of assertions are turned off, which verify that each generated integer is valid list format. Also it does not work for the second argument of subtraction (nor negate, abs, xor) because negation really does have to change the whole list, given its current format (hmm... abs could short-circuit if it sees its argument is positive, I suppose).) Johm Meacham wrote:
Excellent! this has always been a project I wanted to do in the back of my mind. I will likely make it the default Integer implementation for jhc. I look forward to the fun compiler optimizations it will inspire to make it speed comparable to gmp
I can imaging speed near GMP for small-to-moderate size numbers, but GMP implements LOTS of algorithms as well as a number of sophisticated low-level foundations to make itself very fast. One "advantage" we have is if we're only trying to implement the basic Integer algorithms... Anyway I would be quite happy even with a Haskell implementation that only works very fast for up to, say a few-hundred-digit(base 10) numbers, which I can imagine we might be able to manage. (GMP 4.2.x in my experience starts getting very slow for 1000-10000 digit(base 10) numbers and up.) GMP development goes on and, well, *I'm* not that interested in duplicating it - I prefer the idea of one powerful bignum implementation to be perfected. (GMP's implementation code is not very readable to an outsider - I've tried a little - I'd prefer to win on understandability in Haskell, but as you say, compiler optimizations have the *potential* to really help the speed of a readable implementation.) Isaac
Isaac Dupree wrote:
John Meacham wrote:
Excellent! this has always been a project I wanted to do in the back of my mind. I will likely make it the default Integer implementation for jhc. I look forward to the fun compiler optimizations it will inspire to make it speed comparable to gmp
Actually we have a few advantages over GMP: We can do inlining, and analysis for static knowledge (e.g. small numbers or nonzero numbers), much more than in C, which knows nothing about its bignum type. Probably this would work best with some knowledge baked into the compiler about the meaning of Integer operations (like the way GHC has metadata along with the definitions of its primitives, at least whether they're symmetric operations...) (Unless some way to specify that with compiler pragmas is invented, but computing with Integers may be a bit of a special case.) I want to see compilers do more sophisticated constant folding (generally, computation at compile time), which has to watch out for non-pure, non-safe and non-total (nonterminating) functions as well as deciding whether some partial computation will reduce code size and improve speed, or just bloat it. We can make a higher-level library/type, that relies on any Integer implementation, and gives a type that does not evaluate immediately, so optimizations (runtime) can be done on series of operations. Er... the Integer type would probably have to provide operations that were more efficient and did weird things -- either a Haskell Integer implementation or GMP's mpn layer would probably be useful. (Haskell is a particularly good language for things like this, I think... if it is likely to be useful... It is useful for matrix operations in C++ :)) Another thing I was wondering is whether there's any point making it be able to work on the GMP-integer representation that GHC stores internally... probably not much. Isaac
On Sat, Aug 11, 2007 at 12:09:44PM -0300, Isaac Dupree wrote:
BTW: I estimate that it took me about two solid weeks of time, more than I had originally intended to spend :)
I think using CPP will prove important, but makes it harder to test in Hugs... should I use Cabal if I want to use Hugs with haskell+cpp code?
I think if you were willing to use what is provided by the FFI extension, you could make some signifigant improvements without resorting to CPP. mainly, you could use unsigned arithmetic and have access to bit operations. I was thinking a representation like data Integer = Integer !Bool Rest data Rest = Digit !Word Rest | End where the Bool indicates the sign, and the rest are the base-wordsize digits. It would also be possible to just use a sign bit in the number of course. that unboxed strict Word should make a big difference. (it is not clear to me whether being strict in the 'Rest' field will help or hinder, testing with both would be interesting) John -- John Meacham - ⑆repetae.net⑆john⑈
On Mon, Aug 13, 2007 at 03:21:54PM -0700, John Meacham wrote:
On Sat, Aug 11, 2007 at 12:09:44PM -0300, Isaac Dupree wrote:
BTW: I estimate that it took me about two solid weeks of time, more than I had originally intended to spend :)
I think using CPP will prove important, but makes it harder to test in Hugs... should I use Cabal if I want to use Hugs with haskell+cpp code?
I think if you were willing to use what is provided by the FFI extension, you could make some signifigant improvements without resorting to CPP. mainly, you could use unsigned arithmetic and have access to bit operations.
I was thinking a representation like
data Integer = Integer !Bool Rest data Rest = Digit !Word Rest | End
where the Bool indicates the sign, and the rest are the base-wordsize digits. It would also be possible to just use a sign bit in the number of course. that unboxed strict Word should make a big difference.
You might also try data Integer = Pos !Word | Neg !Word | Big !Word Integer since the incremental penalty of 3 constructors is quite small, and it eliminates a few indirections. (Note: You have to actually specify -funbox-strict-fields for the ! to do much good.) Stefan
Stefan O'Rear wrote:
On Mon, Aug 13, 2007 at 03:21:54PM -0700, John Meacham wrote:
On Sat, Aug 11, 2007 at 12:09:44PM -0300, Isaac Dupree wrote:
BTW: I estimate that it took me about two solid weeks of time, more than I had originally intended to spend :)
I think using CPP will prove important, but makes it harder to test in Hugs... should I use Cabal if I want to use Hugs with haskell+cpp code? I think if you were willing to use what is provided by the FFI extension, you could make some signifigant improvements without resorting to CPP. mainly, you could use unsigned arithmetic and have access to bit operations.
I was thinking a representation like
data Integer = Integer !Bool Rest data Rest = Digit !Word Rest | End
where the Bool indicates the sign, and the rest are the base-wordsize digits. It would also be possible to just use a sign bit in the number of course. that unboxed strict Word should make a big difference.
You might also try
data Integer = Pos !Word | Neg !Word | Big !Word Integer
since the incremental penalty of 3 constructors is quite small, and it eliminates a few indirections.
(Note: You have to actually specify -funbox-strict-fields for the ! to do much good.)
I use the {-# UNPACK #-} pragma where I want that effect. Simpler representation = simpler for a compiler to output. (although I could easily provide a Haskell module containing (Integer -> (that thing's shape) ) for compilers to include.) No-FFI is particularly important (this is NOT GMP), but I don't think I need FFI - the compiler just has to support it somehow - to use Data.Word. I do suspect that storing in two's complement style / with separate sign, might be more efficient for some operations. (I'm particularly concerned that small numbers should be fast, so that Int doesn't have to be used all over the place just for speed reasons. Since my format requires two "case"s to determine that an Integer is a small number, _if_ that is the most costly operation, it might be improved) And of course any of you can try the variant implementations you propose, if you want to put in the work on it! I'm not interested for a long time. The more interesting-looking part to me now is seeing what a good mechanism is for using these implementations in compilers is (which is not entirely obvious to me). I'm BTW. base-wordsize digits are not very good for addition speed, depending... Even GMP uses a somewhat smaller base than that, I believe. Look: * The compiler only has to output lists (it already must do string literals), and Ints, in compiled programs. * No types outside Haskell98 need to be implemented. * The Int does not need to be a certain large size, does not need to be two's-complement bits (except for the extension class Bits which seems to assume two's complement implicitly for signed numbers), and does not need to have any particular overflow behavior. I'm not the one with the energy to make compromises between performance and portability. Seeing something like this in Jhc should be interesting and there is where decent-good performance will be wanted. I know my implementation is quite inferior performance to GMP, in _GHC_ :) I still think GMP is the place to go for the highest, most well-rounded performance. (Although "We will release 4.2.2 in spring 2007." did not come to pass, and still appears on gmplib.org) I wonder if there's any way (Jhc) compiler optimizations could transform a strict inductive data into a UArray sort of representation, since that representation is probably more efficient for Integers... Isaac
Excellent! this has always been a project I wanted to do in the back of my mind. I will likely make it the default Integer implementation for jhc. I look forward to the fun compiler optimizations it will inspire to make it speed comparable to gmp :) John -- John Meacham - ⑆repetae.net⑆john⑈
a statistic I thought of: estimate of lines of non-comment code (after reformatting by ghc) : $ ghc IntegerInTermsOfInt.hs -ddump-parsed | wc -l 1084 (This is the only way I've come up with so far, to easily exclude the many and various comments, in a line-count.) ISaac
On Sun, Aug 12, 2007 at 08:39:23AM -0300, Isaac Dupree wrote:
a statistic I thought of: estimate of lines of non-comment code (after reformatting by ghc) : $ ghc IntegerInTermsOfInt.hs -ddump-parsed | wc -l 1084
$ sloccount IntegerInTermsOfInt.hs [...] SLOC Directory SLOC-by-Language (Sorted) 1010 top_dir haskell=1010 [...] Thanks Ian
participants (5)
-
Bulat Ziganshin -
Ian Lynagh -
Isaac Dupree -
John Meacham -
Stefan O'Rear