MOST-POSITIVE-BIGNUM

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.)

<lj-cut text=" --More--(49%) ">


;;; -*- 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)))
Tags: , , ,

Your tax dollars at work. No, really!

The stretch of Brannan between 9th and Division is between me and many of my destinations, and for at least six years, it's had a very nasty collection of potholes: less potholes than long, thin chasms on the gap between the asphalt and the concrete. I've lost at least two bike tires to them over the years.

So, on Feb 27, I thought "what the hell", and emailed potholes@sfdpw.org saying, basically, "hey, how about patching those."

On or about Mar 15... THEY DID.

Maybe this is just a coincidence, but, damn. I almost wiped out from the shock of it alone!

Tags: , ,

I, for one, demand that our new robot overlords bring that beat back

International Dance Party with Radar Technology

This look like, how you say, "party time".

Tags: , ,
Current Music: whatever whitebread trance crap is playing in this video