Oct is a portable Lisp implementation of quad-double arithmetic. This gives about 65 digits of precision. Quad-double arithmetic uses four double-float numbers to represent an extended precision number.
The implementation is modeled on the quad-double package by Yozo Hida. This package is in C++, but we have translated parts of it and extended it to use Lisp. The intent is to provide all of the CL arithmetic functions with a quad-double implementation.
Further information will be provided at a later date. This is currently a work in progress, but the current code has the basic functionality implemented and includes all of the special functions specified by CL. There are, undoubtedly, many bugs.
This package has been tested with CMUCL, SBCL, Clisp, and Allegro. All tests pass. Note that development is primarily done using CMUCL.
%quad-double
numbers, many functions now
support an optional third arg which is where the result should be
written. This is like how bit-and
works. This should
work correctly with both an array or (complex
double-double-float)
implementation, but perhaps some care is
needed to make sure it works for both.
(complex
double-double-float)
to store a %quad-double
.
However, simple timing measurements indicate that arrays are
slightly slower to much slower than using (complex
double-double-float)
.
OCT
package has been renamed. The package is
now NET.COMMON-LISP.OCT
, with a nickname of
OCT
.QD
is no longer a nickname for
OCT
QUAD-DOUBLE-INTERNAL
has been renamed to
OCT-INTERNAL
, with a nickname of
OCTI
. The old nickname QDI
has been
removedMK:DEFSYS
from clocc, if you don't
already have a copy. Or you can also use ASDF
. Note that this might be
out-of-date compared to the mk:defsys
version.
(mk:oos "oct" :compile)
will compile up
everything. Or use (asdf:oos 'asdf:load-op :oct)
(mk:oos "oct-test" :compile)
will compile up some
simple tests. (qdi::all-tests)
will run a series of
tests. The accuracy of the results should be on the order of about
200 bits or more. There are a few cases where accuracy is much less
than this, but that is due to the algorithm. If you have a copy of
RT, you should run
(rt:do-tests)
to run the tests. All tests should pass.
Everything in Oct resides in the NET.COMMON-LISP.OCT
package,
with a nickname of OCT
.
The basic arithmetic operations
of CL
are shadowed in this package so you can use
natural Lisp expressions to operate on quad-doubles. Special
functions are included.
There are two types added:
QD-REAL
- A quad-double type. This has about 65 digits of precision, or about 212 bits.
QD-COMPLEX
- A complex type consisting of two
QD-REAL
values.
The reader is also modified to make it easier to enter quad-double
values. #q
is used to enter both QD-REAL
and QD-COMPLEX
types. For example #q1.25q5
is the QD-REAL
with the value 125000. The exponent
marker is q
. To enter a QD-COMPLEX
value,
use #q(r i)
where r
and i
are
the real and imaginary parts. The parts will be coerced to
QD-REAL
type if necessary.
Here are a few examples:
QD> (/ (sqrt #q3) 2) #q0.866025403784438646763723170752936183471402626905190314027903489696q0 QD> (sin (/ +pi+ 3)) #q0.86602540378443864676372317075293618347140262690519031402790348972q0 QD> (sqrt #q-1) #q(#q0.0q0 #q1.0q0) QD> (coerce 7 'qd-complex) #q(#q7.0q0 #q0.0q0) QD> (integer-decode-float +pi+) 165424160919322423196824703508232170249081435635340508251270944637 -215 1 QD> +pi+ #q3.1415926535897932384626433832795028841971693993751058209749445923q0 QD> (* 4 (atan #q1)) #q3.1415926535897932384626433832795028841971693993751058209749445923q0
Note that +pi+
is the QD-REAL
value for pi.
Here are some simple benchmarks on the performance of this
quad-double implementation. These benchmarks were run using CMUCL on
a 1.42 GHz PPC. The columns are times relative to a
double-float
. The %quad-double
represents
the time using the internal implementaiton, without the overhead of
CLOS
. The QD-REAL
column shows the effect
of CLOS
dispatch.
Operation | %quad-double | QD-REAL | Notes |
---|---|---|---|
Addition | 36 | 73 | |
Multiplication | 420 | 950 | |
Division | 900 | 1200 | |
Square root | 125 | 133 | There is no FP sqrt instruction on a PPC |
Here are some timing results using CMUCL on a 1.5 GHz UltraSparc IIIi
Operation | %quad-double | QD-REAL | Notes |
---|---|---|---|
Addition | 120 | 240 | |
Multiplication | 390 | 660 | |
Division | 1100 | 1450 | |
Square root | 13400 | 13600 | UltraSparc has a FP sqrt instruction |
Here are some timing results using CMUCL with SSE2 support on a 3.06 GHz Core i3
Operation | %quad-double | QD-REAL | Notes |
---|---|---|---|
Addition | 288 | 390 | |
Multiplication | 536 | 673 | |
Division | 2528 | 2785 | |
Square root | 3572 | 3739 |
Hida's QD package has a few timing tests. The lisp equivalent was written and here are the timing results. Note that the Lisp equivalent tried to be exactly the same as the QD reference, but no guarantees on that.
Test | QD | Oct | Relative speed Oct/QD |
---|---|---|---|
add | 0.236 | 1.16 | 4.91 |
mul | 0.749 | 1.54 | 2.06 |
div | 3.00 | 3.11 | 1.03 |
sqrt | 10.57 | 12.2 | 1.15 |
sin | 57.33 | 64.5 | 1.12 |
log | 194 | 119 | 0.613 |
The second and third columns are microsec per operation. The last column is the relative time of Oct vs QD. All of these were run on a 1.5 GHz Ultrasparc III. Sun Studio 11 was used to compile the C code. CMUCL 2007-10 was used for the Lisp code.
It's surprising that Oct does as well as it does. To be fair, the times for Oct include the cost of CLOS dispatch since QD uses templates and classes in the tests. Except for add and mul, QD and Oct are within a few percent. The sin test is a bit slower in Oct. I don't know why, but the test did include the accurate argument reduction. The log test is quite a bit faster for Oct. This is probably due to using a different algorithm. QD uses a Newton iteration to compute the log. Oct uses Halley's iteration.
Currently, there are no official releases. However, you may find occasional snapshots of the sources here.
It is known that CMUCL and SBCL have the desired rounding by default. Allegro works fine on ppc and x86 now.
#q
reader macro. This may interfere with other
systems that want to use #q
.
You can browse our CVS repository or download the development tree via anonymous cvs, as described here. Note that CVS is no longer up-to-date
You can browse our git repository or clone it if desired.