I've been developing on a recursive binary/"really bignum" bignum package for Lisp where the "words" are in a binary tree instead of a linear list or vector, and the leaves are the (big) digits. However, I've included a quadtree-type optimization for long sequences of 0's or 1's, which has magical properties -- e.g., you get "carry-lookahead" for free! My representation is very similar to Jean Vuillemin's 2009 paper (referenced in the file), which doesn't have the quadtree-type optimization, although my representation was developed independently. Jean also uses sign-magnitude rather than 2's complement; 2's complement is much better for Lisp's logical operations on integers. As Vuillemin points out, Karatsuba squaring & multiplication is really ideal for this type of representation. This bignum package is obviously not complete today, but you can watch the progress here: http://home.pipeline.com/~hbaker1/rb.lsp At 12:35 PM 6/8/2012, Bill Gosper wrote:
In case anyone missed it, Knuth is strongly pushing MMIX's MOR and MXOR for commercial 64 bit processors.
www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz