Hey kids, here's a story from the Unfrozen Caveman Files!

I was telling someone about about this the other day, and it's time that Google said something other than "Your search - most-positive-bignum - did not match any documents" so here it is.

Background:

In Common Lisp, there are two types of integers: small ones, which are what you expect; and "bignums", which the specification says should have no upper limit on their range. Fixnums are immediate values (not objects) and bignums are compound (allocated) objects. All the math functions work on either, promoting results to bignums as needed.

So, there is a constant called MOST-POSITIVE-FIXNUM, which is the largest representable "immediate" integer. C calls this MAXINT, and in a C world, it's generally 2^31-1. Because of the type bits on every word, in Lisp it's typically smaller than that. On TI Explorer Lisp Machines it was 2^24-1 (32 bit word, 7 bits of tag).

Here Comes the Dumb:

Well, I was poking around in the system's basement one day, and realized that their implementation of bignums did have an upper limit! A bignum was implemented as an array, with no facility to tack on a second array, so the limit was related to the size of the length field in the array header (instead of being limited by available memory).

So I went and consed up MOST-POSITIVE-BIGNUM.

I did this by carving out a chunk of memory of the proper size for the underlying array, filling it with the right pattern of ones, and slapping an appropriate type tag on the front so that the system would recognize it.

(These sorts of tricks are exactly the sort of things that Java goes out of its way to prevent you from doing, and that's part of why it's impossible to write efficient programs in Java. Whereas the whole Lisp Machine operating system was written in Lisp.)

Fun facts:

• It is 1,223,146 decimal digits (that's 1.0e1223146).
• The object representing it consumes 524 KB of RAM.
• The largest known prime passed it in 1999.
• If you add one to it, e.g.: (1+ MOST-POSITIVE-BIGNUM) you get zero. But it's a zero that consumes 524 KB, and is not = to 0.
• If you ever tried to print it (for example, by having it be the return value in the debugger...) a TI Explorer would lock up in a tight loop in microcode, from which only a warm boot would recover. That microcode loop was trying to grind the number into decimal. That process took more than three days.
• Printing it as a roman numeral took pretty much the same amount of time.

And finally, here's some code that doesn't run on any computer that has been manufactured in two decades.

(Coincidentally, it looks like I wrote this code eighteen years and four days ago. I guess I should have posted this on Friday.)

;;; -*- Mode:Lisp; Syntax: Common-Lisp; Package:USER; Base:10 -*-

;;; 21 Mar 90   Jamie Zawinski   Created.

;;; When you load this file, the constants MOST-POSITIVE-BIGNUM and
;;; MOST-NEGATIVE-BIGNUM will be defined.
;;;
;;; These are the absolute largest and smallest numbers which can be
;;; represented in the TI Explorer's memory architecture.
;;;
;;; WARNING: if you try to print these numbers, the microcode will
;;; hang.  They are totally useless quantities, and dangerous to
;;; have around.  You can examine them with 
;;; (sys:dump-memory most-positive-bignum :bignum-is-dump-object t)
;;; and perform normal arithmetic operations on them.  But the same
;;; dangers apply to any numbers this large.

(defun make-most-positive-bignum (&optional minusp)
  (let* ((header-word 0)
	 (nwords (1- (expt 2 17)))
	 new)
    ;; Construct a bignum header word.
    ;; 31       29           24        22              18     17           0
    ;; +-------------------------------------------------------------------+
    ;; |CDRcode | DTPheader | unused | hdr-type-bignum | sign | datalength |
    ;; +-------------------------------------------------------------------+
    (setq header-word (dpb sys:%header-type-bignum (byte 3 19) 0))
    (setq header-word (dpb (if minusp 1 0)	   (byte 1 18) header-word))
    (setq header-word (dpb nwords		   (byte 17 0) header-word))
    (without-interrupts
      ;; Allocate a chunk of memory, with the header word at the front
      ;; and a pointer to NIL in every other location.
      (setq new (sys:%allocate-and-initialize
		  sys:DTP-EXTENDED-NUMBER	; pointer dtp to return
		  sys:DTP-HEADER		; object dtp to store
		  header-word			; "pointer" field contents
		  nil				; word n+1
		  sys:DEFAULT-CONS-AREA		; area
		  (+ 2 nwords)			; total data length
		  ))
      ;; Stomp on the first word after the header to be a lit-up bignum data
      ;; chunk.  All bits are on except bit 31 (the msb).  Since fixnums are
      ;; only 25 bits, we do this in two steps.
      (sys:%p-dpb-offset #b0111111 (byte 7 25) (sys:%pointer new) 1)
      (sys:%p-dpb-offset -1        (byte 25 0) (sys:%pointer new) 1)
      ;; Now replicate the N+1 byte to addresses N+2 to N+length.
      (sys:%blt (sys:%pointer-plus (sys:follow-structure-forwarding new) 1)
		(sys:%pointer-plus (sys:follow-structure-forwarding new) 2)
		nwords 1))
    new))

;; #, to eval at load-time so that the binary isn't monstrously huge...

(defconstant MOST-POSITIVE-BIGNUM '#,(make-most-positive-bignum))
(defconstant MOST-NEGATIVE-BIGNUM '#,(make-most-positive-bignum t))


;;; If you want to play with these, this might help.  Prevents huge bignums 
;;; from being printed.

(sys:advise sys:print-bignum :around safe-biggestnums nil
  (cond ((eql (car sys:arglist) most-positive-bignum)
	 (write-string "#.MOST-POSITIVE-BIGNUM" (second sys:arglist)))
	((eql (car sys:arglist) most-negative-bignum)
	 (write-string "#.MOST-NEGATIVE-BIGNUM" (second sys:arglist)))
	((> (integer-length (car sys:arglist)) 10000)
	 (write-string (if (minusp (car sys:arglist))
			   "#<massively-negative-bignum>"
			   "#<massively-positive-bignum>")
		       (second sys:arglist)))
	(t :DO-IT)))