/cl-unum

A Common Lisp implementation of John L. Gustafson's unums as described in The End of Error

Primary LanguageCommon LispMIT LicenseMIT

cl-unum

A Common Lisp implementation of John L. Gustafson's unums as described in The End of Error.

Initial goals are to

  1. understand bit twiddling corner cases

    • unums are represented more abstractly
    • methods print-object give a visual bit-level representation

  2. delimit the host/universal from the scratchpad/general numbers

    • method (gbound (ubound)) corresponds to host-to-scratchpad transfer
    • method (ubound (gbound)) corresponds to scratchpad-to-host transfer
    • macro with-scratchpad turns on data transfer measurement
    • macro without-scratchpad turns off data transfer measurement (should disappear)

Currently, only SBCL is supported.

Examples.

UNUM> (ubound 1.2)
#ub(#u(0 01 0011001100110011 1 001 1111,
       (1.1999969482421875 . 1.20001220703125)))
UNUM> (gbound *)
#gb(#g(1.1999969482421875), #g(1.20001220703125))
UNUM> (ubound *)
#ub(#u(0 01111111 0011001100110011 1 111 1111,
       (1.1999969482421875 . 1.20001220703125)))
UNUM> (with-scratchpad () (gbound *))
;;; Scratchpad transfer: 34 bits, 1 unums, 1 ubounds (34.0 b/ub)
#gb(#g(1.1999969482421875), #g(1.20001220703125))
UNUM> (with-scratchpad () (gbound (make-ubound (unum -1.2) (unum 2.4))))
;;; Scratchpad transfer: 54 bits, 2 unums, 1 ubounds (54.0 b/ub)
#gb(#g(-1.20001220703125), #g(2.4000244140625))

UNUM> (unpack (lo (ubound 1.2)))
#u38(00000 ......01 1 0011001100110011 1 001 1111,
     (1.1999969482421875 . 1.20001220703125))
UNUM> (unum-inf *env* :sign '-)
#u[1 11111111 1111111111111111 0 111 1111, -inf]
UNUM> (open-inf-unum *env* :sign '-)
#u(1 1 1 1 000 0000, (-inf . -3))
UNUM> (unum-nan *env* :sign t)
#u(1 11111111 1111111111111111 1 111 1111, snan)
UNUM> (let ((*env* (make-env 2 2))) (unpack (lo (ubound -1.2))))
#u19(10000 ..01 1 0011 1 01 11, (-1.25 . -1.1875))
UNUM> (unum-inf *)
#u[1 1111 1111 0 11 11, -inf]

UNUM> (trace poly)
(POLY)
UNUM> (flet ((%quad (x)
	   (poly
	    (make-ubarray (vector (ubound 2) (ubound 100) (ubound 3)))
	    x)))
    (let* ((*env* (make-env 0 0))
	   (dom (make-ubound (open-inf-unum *env* :sign '-)
			     (open-inf-unum *env*))))
      (with-scratchpad () (jointp (%quad dom) (ubound 0)))))
  0: (POLY
      #ubarray[ #(#ub[#u[0 1 0 0, 2]] #ub(#u(0 1 0 1, (2 . inf)))
                  #ub(#u(0 1 0 1, (2 . inf)))) ]
      #ub(#u(1 1 0 1), #u(0 1 0 1); ((-inf . -2), (2 . inf))))
    1: (POLY
        #gbarray[ #(#gb[#g[2], #g[2]] #gb(#g(2), #g(inf))
                    #gb(#g(2), #g(inf))) ]
        #gb(#g(-inf), #g(inf)))
    1: POLY returned #gb(#g(-inf), #g(inf))
  0: POLY returned #ub(#u(1 1 0 1), #u(0 1 0 1); ((-inf . -2), (2 . inf)))
;;; Scratchpad transfer: 241 bits, 53 unums, 29 ubounds (8.310345 b/ub)
T

UNUM> (trace plus minus times divide plus2 minus2 times2 divide2)
(PLUS MINUS TIMES DIVIDE PLUS2 MINUS2 TIMES2 DIVIDE2)
UNUM-USER> (with-scratchpad ()
    (let* ((*env* (make-env 3 7))
	   (r (rump 77617 33096)))
      (<= -0.8274 (to-rational (lo r))
	  (to-rational (hi* r)) -0.8273)))
  0: (TIMES #ub[#u[0 1111 0100110111 0 011 0001001, 333.75]]
            #ub[#u[0 11011001 000011111100001111010010000100001001101111111001010111000011011010110001 0 111 1000111,
                   1314174534371215466459037696]])
    1: (UNUM::TIMES2 #ub[#u[0 1111 0100110111 0 011 0001001, 333.75]]
                     #ub[#u[0 11011001 000011111100001111010010000100001001101111111001010111000011011010110001 0 111 1000111,
                            1314174534371215466459037696]])
      2: (UNUM::TIMES2 #gb[#g[333.75], #g[333.75]]
                       #gb[#g[1314174534371215466459037696],
                           #g[1314174534371215466459037696]])
      2: UNUM::TIMES2 returned
           #gb[#g[438605750846393161930703831040],
               #g[438605750846393161930703831040]]
    1: UNUM::TIMES2 returned
         #ub[#u[0 11100001 0110001001001101100010110001110100100111010110000101011111111000010011010100000111 0 111 1010001,
                438605750846393161930703831040]]
  0: TIMES returned
       #ub[#u[0 11100001 0110001001001101100010110001110100100111010110000101011111111000010011010100000111 0 111 1010001,
              438605750846393161930703831040]]
  0: (TIMES #ub[#u[0 110 011 0 010 0000010, 11]]
            #ub[#u[0 111111 01100111000101010000011101100001 0 101 0011111,
                   6024398689]]
            #ub[#u[0 111101 000001010010011010010001 0 101 0010111,
                   1095345216]])
    1: (UNUM::TIMES2 #ub[#u[0 110 011 0 010 0000010, 11]]
                     #ub[#u[0 111111 01100111000101010000011101100001 0 101 0011111,
                            6024398689]])
      2: (UNUM::TIMES2 #gb[#g[11], #g[11]] #gb[#g[6024398689], #g[6024398689]])
      2: UNUM::TIMES2 returned #gb[#g[66268385579], #g[66268385579]]
    1: UNUM::TIMES2 returned
         #ub[#u[0 1100010 11101101101111001110101000100101011 0 110 0100010,
                66268385579]]
    1: (UNUM::TIMES2
        #ub[#u[0 1100010 11101101101111001110101000100101011 0 110 0100010,
               66268385579]]
        #ub[#u[0 111101 000001010010011010010001 0 101 0010111, 1095345216]])
      2: (UNUM::TIMES2 #gb[#g[66268385579], #g[66268385579]]
                       #gb[#g[1095345216], #g[1095345216]])
      2: UNUM::TIMES2 returned
           #gb[#g[72586759116001040064], #g[72586759116001040064]]
    1: UNUM::TIMES2 returned
         #ub[#u[0 11000000 11110111101010111111110001101010110111010000101101101011011 0 111 0111010,
                72586759116001040064]]
  0: TIMES returned
       #ub[#u[0 11000000 11110111101010111111110001101010110111010000101101101011011 0 111 0111010,
              72586759116001040064]]
  0: (TIMES #ub[#u[0 1101 111001 0 011 0000101, 121]]
            #ub[#u[0 1111011 000010100110011110101001011110010101111000100001 0 110 0101111,
                   1199781142214086656]])
    1: (UNUM::TIMES2 #ub[#u[0 1101 111001 0 011 0000101, 121]]
                     #ub[#u[0 1111011 000010100110011110101001011110010101111000100001 0 110 0101111,
                            1199781142214086656]])
      2: (UNUM::TIMES2 #gb[#g[121], #g[121]]
                       #gb[#g[1199781142214086656], #g[1199781142214086656]])
      2: UNUM::TIMES2 returned
           #gb[#g[145173518207904485376], #g[145173518207904485376]]
    1: UNUM::TIMES2 returned
         #ub[#u[0 11000001 111101111010101111111100011010010111010111110110011001 0 111 0110101,
                145173518207904485376]]
  0: TIMES returned
       #ub[#u[0 11000001 111101111010101111111100011010010111010111110110011001 0 111 0110101,
              145173518207904485376]]
  0: (MINUS
      #ub[#u[0 11000000 11110111101010111111110001101010110111010000101101101011011 0 111 0111010,
             72586759116001040064]]
      #ub[#u[0 11011001 000011111100001111010010000100001001101111111001010111000011011010110001 0 111 1000111,
             1314174534371215466459037696]]
      #ub[#u[0 11000001 111101111010101111111100011010010111010111110110011001 0 111 0110101,
             145173518207904485376]]
      #ub[#u[0 1 0 0 000 0000000, 2]])
    1: (UNUM::MINUS2
        #ub[#u[0 11000000 11110111101010111111110001101010110111010000101101101011011 0 111 0111010,
               72586759116001040064]]
        #ub[#u[0 11011001 000011111100001111010010000100001001101111111001010111000011011010110001 0 111 1000111,
               1314174534371215466459037696]])
      2: (UNUM::MINUS2 #gb[#g[72586759116001040064], #g[72586759116001040064]]
                       #gb[#g[1314174534371215466459037696],
                           #g[1314174534371215466459037696]])
        3: (UNUM::PLUS2 #gb[#g[72586759116001040064], #g[72586759116001040064]]
                        #gb[#g[-1314174534371215466459037696],
                            #g[-1314174534371215466459037696]])
        3: UNUM::PLUS2 returned
             #gb[#g[-1314174461784456350457997632],
                 #g[-1314174461784456350457997632]]
      2: UNUM::MINUS2 returned
           #gb[#g[-1314174461784456350457997632],
               #g[-1314174461784456350457997632]]
    1: UNUM::MINUS2 returned
         #ub[#u[1 11011001 000011111100001111010001000101001100010111111011001001101100100000101011010010100101 0 111 1010011,
                -1314174461784456350457997632]]
    1: (UNUM::MINUS2
        #ub[#u[1 11011001 000011111100001111010001000101001100010111111011001001101100100000101011010010100101 0 111 1010011,
               -1314174461784456350457997632]]
        #ub[#u[0 11000001 111101111010101111111100011010010111010111110110011001 0 111 0110101,
               145173518207904485376]])
      2: (UNUM::MINUS2
          #gb[#g[-1314174461784456350457997632],
              #g[-1314174461784456350457997632]]
          #gb[#g[145173518207904485376], #g[145173518207904485376]])
        3: (UNUM::PLUS2
            #gb[#g[-1314174461784456350457997632],
                #g[-1314174461784456350457997632]]
            #gb[#g[-145173518207904485376], #g[-145173518207904485376]])
        3: UNUM::PLUS2 returned
             #gb[#g[-1314174606957974558362483008],
                 #g[-1314174606957974558362483008]]
      2: UNUM::MINUS2 returned
           #gb[#g[-1314174606957974558362483008],
               #g[-1314174606957974558362483008]]
    1: UNUM::MINUS2 returned
         #ub[#u[1 11011001 000011111100001111010011000011000111000111110111100100000011111000100001101011100101 0 111 1010011,
                -1314174606957974558362483008]]
    1: (UNUM::MINUS2
        #ub[#u[1 11011001 000011111100001111010011000011000111000111110111100100000011111000100001101011100101 0 111 1010011,
               -1314174606957974558362483008]]
        #ub[#u[0 1 0 0 000 0000000, 2]])
      2: (UNUM::MINUS2
          #gb[#g[-1314174606957974558362483008],
              #g[-1314174606957974558362483008]]
          #gb[#g[2], #g[2]])
        3: (UNUM::PLUS2
            #gb[#g[-1314174606957974558362483008],
                #g[-1314174606957974558362483008]]
            #gb[#g[-2], #g[-2]])
        3: UNUM::PLUS2 returned
             #gb[#g[-1314174606957974558362483010],
                 #g[-1314174606957974558362483010]]
      2: UNUM::MINUS2 returned
           #gb[#g[-1314174606957974558362483010],
               #g[-1314174606957974558362483010]]
    1: UNUM::MINUS2 returned
         #ub[#u[1 11011001 00001111110000111101001100001100011100011111011110010000001111100010000110101110010100001 0 111 1011000,
                -1314174606957974558362483010]]
  0: MINUS returned
       #ub[#u[1 11011001 00001111110000111101001100001100011100011111011110010000001111100010000110101110010100001 0 111 1011000,
              -1314174606957974558362483010]]
  0: (TIMES
      #ub[#u[0 111111 01100111000101010000011101100001 0 101 0011111,
             6024398689]]
      #ub[#u[1 11011001 00001111110000111101001100001100011100011111011110010000001111100010000110101110010100001 0 111 1011000,
             -1314174606957974558362483010]])
    1: (UNUM::TIMES2
        #ub[#u[0 111111 01100111000101010000011101100001 0 101 0011111,
               6024398689]]
        #ub[#u[1 11011001 00001111110000111101001100001100011100011111011110010000001111100010000110101110010100001 0 111 1011000,
               -1314174606957974558362483010]])
      2: (UNUM::TIMES2 #gb[#g[6024398689], #g[6024398689]]
                       #gb[#g[-1314174606957974558362483010],
                           #g[-1314174606957974558362483010]])
      2: UNUM::TIMES2 returned
           #gb[#g[-7917111779274712207494296632228773890],
               #g[-7917111779274712207494296632228773890]]
    1: UNUM::TIMES2 returned
         #ub[#u[1 11111001 0111110100110001111011111101110000010111110011111101001101101010111010100001001110010000101001101010000111000000000000001 0 111 1111000,
                -7917111779274712207494296632228773890]]
  0: TIMES returned
       #ub[#u[1 11111001 0111110100110001111011111101110000010111110011111101001101101010111010100001001110010000101001101010000111000000000000001 0 111 1111000,
              -7917111779274712207494296632228773890]]
  0: (TIMES #ub[#u[0 11 011 0 001 0000010, 5.5]]
            #ub[#u[0 11110111 000101010011101110010110001010100000011101110111110010100101111110101111110011100100000001000001 0 111 1011111,
                   1439474789212538429291115400277262336]])
    1: (UNUM::TIMES2 #ub[#u[0 11 011 0 001 0000010, 5.5]]
                     #ub[#u[0 11110111 000101010011101110010110001010100000011101110111110010100101111110101111110011100100000001000001 0 111 1011111,
                            1439474789212538429291115400277262336]])
      2: (UNUM::TIMES2 #gb[#g[5.5], #g[5.5]]
                       #gb[#g[1439474789212538429291115400277262336],
                           #g[1439474789212538429291115400277262336]])
      2: UNUM::TIMES2 returned
           #gb[#g[7917111340668961361101134701524942848],
               #g[7917111340668961361101134701524942848]]
    1: UNUM::TIMES2 returned
         #ub[#u[0 11111001 011111010011000111101110011110011100101001000100101101100100001110010001101110111001100001011001011 0 111 1100010,
                7917111340668961361101134701524942848]]
  0: TIMES returned
       #ub[#u[0 11111001 011111010011000111101110011110011100101001000100101101100100001110010001101110111001100001011001011 0 111 1100010,
              7917111340668961361101134701524942848]]
  0: (TIMES #ub[#u[0 1 0 0 000 0000000, 2]]
            #ub[#u[0 11110 000000101001 0 100 0001011, 33096]])
    1: (UNUM::TIMES2 #ub[#u[0 1 0 0 000 0000000, 2]]
                     #ub[#u[0 11110 000000101001 0 100 0001011, 33096]])
      2: (UNUM::TIMES2 #gb[#g[2], #g[2]] #gb[#g[33096], #g[33096]])
      2: UNUM::TIMES2 returned #gb[#g[66192], #g[66192]]
    1: UNUM::TIMES2 returned #ub[#u[0 11111 000000101001 0 100 0001011, 66192]]
  0: TIMES returned #ub[#u[0 11111 000000101001 0 100 0001011, 66192]]
  0: (DIVIDE #ub[#u[0 11111 0010111100110001 0 100 0001111, 77617]]
             #ub[#u[0 11111 000000101001 0 100 0001011, 66192]])
    1: (UNUM::DIVIDE2 #ub[#u[0 11111 0010111100110001 0 100 0001111, 77617]]
                      #ub[#u[0 11111 000000101001 0 100 0001011, 66192]])
      2: (UNUM::DIVIDE2 #gb[#g[77617], #g[77617]] #gb[#g[66192], #g[66192]])
      2: UNUM::DIVIDE2 returned #gb[#g[77617/66192], #g[77617/66192]]
    1: UNUM::DIVIDE2 returned
         #ub(#u(0 01 00101100001011111100010110010101101100000110101111101011011101001010010100011000111100000001100011000000100100101000100010000010 1 001 1111111,
                (1.1726039400531786318588349045201837080003886557882708834714246123149027628826780313251072762614768407729570753872394561767578125
                 . 1.17260394005317863185883490452018370800332739166532660224134645365795837707722469521703749506524872003865311853587627410888671875)))
  0: DIVIDE returned
       #ub(#u(0 01 00101100001011111100010110010101101100000110101111101011011101001010010100011000111100000001100011000000100100101000100010000010 1 001 1111111,
              (1.1726039400531786318588349045201837080003886557882708834714246123149027628826780313251072762614768407729570753872394561767578125
               . 1.17260394005317863185883490452018370800332739166532660224134645365795837707722469521703749506524872003865311853587627410888671875)))
  0: (PLUS
      #ub[#u[0 11100001 0110001001001101100010110001110100100111010110000101011111111000010011010100000111 0 111 1010001,
             438605750846393161930703831040]]
      #ub[#u[1 11111001 0111110100110001111011111101110000010111110011111101001101101010111010100001001110010000101001101010000111000000000000001 0 111 1111000,
             -7917111779274712207494296632228773890]]
      #ub[#u[0 11111001 011111010011000111101110011110011100101001000100101101100100001110010001101110111001100001011001011 0 111 1100010,
             7917111340668961361101134701524942848]]
      #ub(#u(0 01 00101100001011111100010110010101101100000110101111101011011101001010010100011000111100000001100011000000100100101000100010000010 1 001 1111111,
             (1.1726039400531786318588349045201837080003886557882708834714246123149027628826780313251072762614768407729570753872394561767578125
              . 1.17260394005317863185883490452018370800332739166532660224134645365795837707722469521703749506524872003865311853587627410888671875))))
    1: (UNUM::PLUS2
        #ub[#u[0 11100001 0110001001001101100010110001110100100111010110000101011111111000010011010100000111 0 111 1010001,
               438605750846393161930703831040]]
        #ub[#u[1 11111001 0111110100110001111011111101110000010111110011111101001101101010111010100001001110010000101001101010000111000000000000001 0 111 1111000,
               -7917111779274712207494296632228773890]])
      2: (UNUM::PLUS2
          #gb[#g[438605750846393161930703831040],
              #g[438605750846393161930703831040]]
          #gb[#g[-7917111779274712207494296632228773890],
              #g[-7917111779274712207494296632228773890]])
      2: UNUM::PLUS2 returned
           #gb[#g[-7917111340668961361101134701524942850],
               #g[-7917111340668961361101134701524942850]]
    1: UNUM::PLUS2 returned
         #ub[#u[1 11111001 0111110100110001111011100111100111001010010001001011011001000011100100011011101110011000010110010110000000000000000000001 0 111 1111000,
                -7917111340668961361101134701524942850]]
    1: (UNUM::PLUS2
        #ub[#u[1 11111001 0111110100110001111011100111100111001010010001001011011001000011100100011011101110011000010110010110000000000000000000001 0 111 1111000,
               -7917111340668961361101134701524942850]]
        #ub[#u[0 11111001 011111010011000111101110011110011100101001000100101101100100001110010001101110111001100001011001011 0 111 1100010,
               7917111340668961361101134701524942848]])
      2: (UNUM::PLUS2
          #gb[#g[-7917111340668961361101134701524942850],
              #g[-7917111340668961361101134701524942850]]
          #gb[#g[7917111340668961361101134701524942848],
              #g[7917111340668961361101134701524942848]])
      2: UNUM::PLUS2 returned #gb[#g[-2], #g[-2]]
    1: UNUM::PLUS2 returned #ub[#u[1 1 0 0 000 0000000, -2]]
    1: (UNUM::PLUS2 #ub[#u[1 1 0 0 000 0000000, -2]]
                    #ub(#u(0 01 00101100001011111100010110010101101100000110101111101011011101001010010100011000111100000001100011000000100100101000100010000010 1 001 1111111,
                           (1.1726039400531786318588349045201837080003886557882708834714246123149027628826780313251072762614768407729570753872394561767578125
                            . 1.17260394005317863185883490452018370800332739166532660224134645365795837707722469521703749506524872003865311853587627410888671875))))
      2: (UNUM::PLUS2 #gb[#g[-2], #g[-2]]
                      #gb(#g(1.1726039400531786318588349045201837080003886557882708834714246123149027628826780313251072762614768407729570753872394561767578125),
                          #g(1.17260394005317863185883490452018370800332739166532660224134645365795837707722469521703749506524872003865311853587627410888671875)))
      2: UNUM::PLUS2 returned
           #gb(#g(-0.8273960599468213681411650954798162919996113442117291165285753876850972371173219686748927237385231592270429246127605438232421875),
               #g(-0.82739605994682136814116509547981629199667260833467339775865354634204162292277530478296250493475127996134688146412372589111328125))
    1: UNUM::PLUS2 returned
         #ub(#u(1 010 1010011110100000011101001101010010011111001010000010100100010110101101011100111000011111110011100111111011011010111011101111101 1 010 1111110,
                (-0.8273960599468213681411650954798162919996113442117291165285753876850972371173219686748927237385231592270429246127605438232421875
                 . -0.82739605994682136814116509547981629199667260833467339775865354634204162292277530478296250493475127996134688146412372589111328125)))
  0: PLUS returned
       #ub(#u(1 010 1010011110100000011101001101010010011111001010000010100100010110101101011100111000011111110011100111111011011010111011101111101 1 010 1111110,
              (-0.8273960599468213681411650954798162919996113442117291165285753876850972371173219686748927237385231592270429246127605438232421875
               . -0.82739605994682136814116509547981629199667260833467339775865354634204162292277530478296250493475127996134688146412372589111328125)))
;;; Scratchpad transfer: 3865 bits, 55 unums, 55 ubounds (70.27273 b/ub)
T

UNUM> (rt:do-tests)
Doing 166 pending tests of 166 tests total.
 UNUM-USER::MAKE-ENV.TEST-1 UNUM-USER::MAKE-ENV.TEST-2
...
 UNUM-USER::INTERSECT.TEST-14 UNUM-USER::INTERSECT.TEST-14B
;;; Scratchpad transfer: 20332 bits, 302 unums, 180 ubounds (112.95556 b/ub)
 UNUM-USER::CH14.TEST-1
;;; Scratchpad transfer: 2999 bits, 131 unums, 92 ubounds (32.597828 b/ub)
;;; Scratchpad transfer: 652 bits, 140 unums, 92 ubounds (7.0869565 b/ub)
 UNUM-USER::CH14.TEST-2
;;; Scratchpad transfer: 3865 bits, 55 unums, 55 ubounds (70.27273 b/ub)
 UNUM-USER::CH14.TEST-3
;;; Scratchpad transfer: 12958 bits, 267 unums, 220 ubounds (58.9 b/ub)
 UNUM-USER::CH14.TEST-4
;;; Scratchpad transfer: 543 bits, 23 unums, 22 ubounds (24.681818 b/ub)
 UNUM-USER::CH14.TEST-5
;;; Scratchpad transfer: 625 bits, 21 unums, 21 ubounds (29.761906 b/ub)
 UNUM-USER::CH14.TEST-6
;;; Scratchpad transfer: 214 bits, 9 unums, 5 ubounds (42.8 b/ub)
 UNUM-USER::CH17.TEST-1 UNUM-USER::CH17.TEST-2 UNUM-USER::CH17.TEST-2B
...
No tests failed.
T