Monday, September 17, 2007

Bignum libraries

So does anybody know of a simple, efficient, BSD-licensed bignum library where the radix size is equal to the CPU's word size, and not the CPU's word size minus two bits?

9 comments:

Anonymous said...

I don't want to make the obvious seem like a revelation, but... the GHC Haskell project is looking for a suitable BSD-license like GMP replacement and hopefully both projects may benefit by collaborating possibly in some way.

http://hackage.haskell.org/trac/ghc/wiki/ReplacingGMPNotes

Slava Pestov said...

That wasn't obvious to me at all. Thanks for pointing out. While I don't have the time or expertise to develop a new bignum library, hopefully somebody else does :)

The reason word-size radix would be interesting is that it would simply boxing/unboxing word-size quantities and allow this to be done with assembly intrinsics instead of calls into C.

Anonymous said...

Slava,

Howdy! That comment was me, Mark at mgaspar@starmill.com

I was too lazy to create a Blogger Identity.

Could you briefly share what fundamental subset of ops are needed?

If possible, I could take a crack at it in assembly and then invite help in optimizing it on various assembler hack websites so Factor could end up with something possibly decent (all under BSD license of course). I'd start with x86, then x86-64 then let someone else take a crack at other CPUs.

Feel free to edit out my email address or not even post this at all if you don't want to bother. However, I think others that might help may want to know what the bare minimum Bignum functionality you are looking for... that is for people too lazy like me to look at your source and figure it out myself! That would make me all too useful and I strive on being useless!

Anonymous said...

Slava,

In retrospect, could you edit & replace my email of the last post to mgaspar7@pacbell.net since I already get a fair amount of spam on it from whereas my starmill account has yet to get any and I'd rather not give the spam address 'bots out there pick up on it here if you don't mind the trouble.

george said...

What does sbcl use for it's bignum's.

Slava Pestov said...

george: they use apostrophes. I think they also use possessive nouns, the correct grammatical form thereof.

nathan said...

FWIW, SBCL uses a home-grown implementation written in Lisp. It'd be a OK place to copy algorithms from, but it's obviously unsuitable for porting directly.

(I'm sure Slava knows this already, just stating it for the record.)

Anonymous said...

I am not sure if it use one word for the radix, bit libtommath (http://math.libtomcrypt.com) is a BSD library, which is used in the latest versions of Tcl for bignum support. It has a Public Domain license.

Anonymous said...

duh, if it is Public Domain, it obviously isn't a BSD library.