1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783
|
************************************************************
* Core Library
*
* A C/C++ Library for Robust Computation
*
* Department of Computer Science
* Courant Institute of Mathematical Sciences
* New York University
* 251 Mercer Street
* New York, NY 10012
* USA
*
* http://cs.nyu.edu/exact/
*
* Copyright (c) 1998-2004 by Exact Computation Project, NYU
*
* $Id: README,v 1.46 2004/11/12 22:56:33 exact Exp $
*************************************************************
README FILE: TABLE OF CONTENTS
1) ORIENTATION
2) DIRECTORIES AND FILES
3) DOWNLOAD AND INSTALLATION
4) NEWS, PLANS AND BUGS
5) ACKNOWLEDGEMENT AND HISTORY
6) LICENSE INFORMATION
*************************************************************
1) ORIENTATION
This is Core Library Version 1.7, released on Nov 12, 2004.
The Core Library is a collection of C/C++ classes for exact
computation with real algebraic numbers.
It embodies our precision-driven approach and is
useful for robust numerical (especially geometric) algorithms.
The library supports the Exact Geometric Computation (EGC) philosophy
through its novel and easy-to-use notion of accuracy levels.
We define four "Core Accuracy Levels":
Level I: Machine Accuracy
This is the IEEE 754 Standard.
Level II: Arbitrary Accuracy
If a user specify "1000 bits" of accuracy,
this means no overflow/underflow occurs as long
as long as number sizes do not exceed 1000 bits.
Level III: Guaranteed Accuracy
The user can specify "10 bits" (relative or
absolute) and any computed number will have
at least 10 bits of accuracy.
Level IV: Mixed Accuracy
The above three levels are intermixed.
Level III is the most interesting level. It is the default level,
Ideally, a single C++ program can be compiled to run at any chosen
level. Level IV is not fully defined at the present time.
The current library focuses on Level III. Most programs should
be able to run both Levels I and III. Such multi-level capability
in a single program is useful for debugging and program development.
A key design goal is to allow any standard C/C++ program to access
critical CORE facilities with minimal changes to the program. Most
basic standalone C++ programs can be ``CORE-ized'' with little fuss.
In the ideal case, one only has to insert the following statement
#include "CORE/CORE.h"
following all the standard include statements. The default accuracy
is Level III. At this level, a variable with the machine type
"double" or "long" is redefined as an instance of the class "Expr"
(a C++ class). All comparisons involving Expr are error-free,
provided your expressions involve only the four arithmetic operations
and square-roots. Example:
double x, y, a, b;
x = 2; y = 3;
a = sqrt(x) + sqrt(y);
b = sqrt(x + y + 2*sqrt(x)*sqrt(y));
if (a == b) cout << "Equal (CORRECT!)\n";
else cout << "Not Equal (ERROR!)\n";
When run in Level III, the expressions for a and b are always equal
regardless of the values (x=2 and y=3) assigned to x and y.
In the framework of EGC, error-free comparisons amount to
computing the ''exact geometry'' in your programs. Nonrobustness
issues from round-off errors are thereby abolished.
A tutorial in this "doc" subdirectory, plus the many
sample programs in the "progs" subdirectory, should allow you
to start writing CORE programs rather quickly. In particular,
you may use the examples in progs/generic as template
to develop your own CORE programs. For extra functionality,
we define domain specific "CORE eXtensions" (COREX for short).
These include a linear algebra COREX and a geometry
COREX. They are still rudimentary.
The Core Library is relatively small. The "base distribution"
of Version 1.7, which includes source code and examples, is less
than 800 KB. The "full distribution" which includes the base distribution,
documentation and gmp, is over 3.5MB. The library has been tested
on solaris, linux, cygwin and Windows. It is
also fully compatible with CGAL.
NOTE ON TERMINOLOGY.
"Core" is not an abbreviation; we chose this name to suggest its
role as the "numerical core" for robust geometric computations.
It is also to remind ourselves (the designers) that "cores" are
usually small. However, we use the capitalized sequence "CORE"
as a shorthand for "Core Library" (e.g., a CORE program).
*************************************************************
2) DIRECTORIES AND FILES
The Core Directory is denoted ${CORE_PATH} in these notes.
The base distribution has the following files and subdirectories:
README This file
ANNOUNCEMENT Release announcement
LICENSE.QPL The Q Public License
FAQs Frequently asked questions
Makefile Makefile for the whole library
Make.config Compilation flags for CORE programs
ext/ CORE eXtensions (linear algebra, geometry, etc)
inc/ The header files.
lib/ The compiled library is found here.
progs/ Sample programs that use Core Library.
src/ Source code for the Core Library.
tmp/ Temporary files (e.g., installation diagnostic messages)
win32/ Windows related files (can be deleted for unix-base)
gmp/ gmp installation directory (may be a link). This
directory may be missing if you have your own gmp.
The full distribution has these additional files and directories:
doc/ Core Library Documentation
gmp-xxx.tar.gz GNU's gmp distribution (version xxx)
gmp-xxx/ GNU's gmp directory for unpacking and compiling
(can be deleted after installing gmp)
*************************************************************
3) DOWNLOAD AND INSTALLATION
3.0) PREREQUISITE:
You must have "make" (GNU's gmake is recommended), "tar" and "gzip".
For compilers, "g++" is also recommended but not required.
In turn, "g++" will need "m4" (the macro preprocessor).
We DO NOT assume that you already have "gmp" (GNU's multiprecision
number package).
For Windows: you could replace g++ with Visual C++.
However we highly recommend "Cygwin" from Red Hat. This is a free
and easy-to-install Unix-like environment that sits on top of all
versions of Windows. It comes with g++, make, tar, gzip that are
needed to install the Core Library. The big bonus of Cygwin are
(I) There is no need for dual booting;
(II) There is no need to partition your disc;
(III) You can share files between Windows and Cygwin;
(IV) There is a convenient setup.exe utility that allows you to
install / update / re-install / uninstall
any component in a large suite of Unix tools and utilities, directly
from the web. You can download Cygwin at
http://www.cygwin.com.
3.1) DOWNLOAD. First download the file core_vX.Y.Z_full.tgz
(for version X.Y.Z). The current distribution is X.Y=1.7.0.
The website for download is
http://cs.nyu.edu/exact/core.
There are three distributions, a "base distribution", a "standard
distribution" and a "full distribution". The standard distribution
includes the base distribution and documentation. The full
distribution includes the standard distribution, plus gmp.
The main steps here describes on installation from a full distribution
in a unix-like environment: it is the simplest to install.
But see 3.9) below for *variant* installations: these include
installing only the base distribution, using dynamic libraries,
Windows platform, re-installing the Core Library, building Debugging
Versions of Core Library, etc.
The overall installation time is 20-40 minutes on a typical
machine. If you already have gmp, the time is halved (on Pentium III
800 MHz, 256 MB RAM, it takes 10 minutes).
3.2) UNPACK. In your computer, go to the directory where you wish to
install the Core Library. If this location is the value of
the environment variable CORE_INSTALL (in unix), you would do:
% cd $(CORE_INSTALL)
(% denotes the unix prompt in these instructions)
Move the file core_vX.Y_full.tgz there. Now unzip and untar the
file by typing:
% gzip -cd core_vX.Y_full.tgz | tar xvf -
This creates a directory called core_vX.Y. All the files and
directories mentioned in 2) above, including this README file,
should now be in this directory.
In the following, the variable CORE_PATH denotes the full path
name of this newly created directory. Hence, $(CORE_PATH) is really
$(CORE_INSTALL)/core_vX.Y
3.3) There are three stages of installation:
STAGE 1 -- gmp-related installation
STAGE 2 -- create the core library, extensions, samples
STAGE 3 -- run tests and timings
The screen output from the individual steps in these stages
are stored in the files ${CORE_PATH}/tmp/DIAG_* for your diagnostics.
But before any of these steps, you must choose your PLATFORM.
PLATFORM is a combination of OS plus compiler.
This variable is set in the Make.config file:
% cd $(CORE_PATH)
% vi Make.config -- use "vi" or your favorite editor to edit
the file ``Make.config''.
-- Follow the instructions in the file.
-- For most users, you only need to set the
PLATFORM variable.
To see what your chosen options are, do:
% make opt[ions] -- this will show the various global settings
-- e.g. PLATFORM=gnu, LINKAGE=static, VAR=, etc.
3.4) STAGE 1: INSTALLING GMP
PRELIMINARY STEP: For most Unix-like OS (e.g., Solaris, Linux),
gmp will automatically build BOTH a static and a dynamic library.
In this case, most compilers will link to the dynamic gmp library.
Therefore, you need to add the path of your dynamic gmp library to
the environmental variable LD_LIBRARY_PATH.
E.g., in csh/tcsh,
% setenv LD_LIBRARY_PATH ${LD_LIBRARY_PATH}:${your_gmp_install_dir}/lib
E.g., in bash,
% export LD_LIBRARY_PATH=${LD_LIBRARY_PATH}:${your_gmp_install_dir}/lib
In option b) below, there is an example where ${your_gmp_install_dir}=/usr/local.
NOW we are ready to proceed with installing gmp.
Choose one of the following three situations that apply to you:
a) You already have GMP header files and library files on
your system directory, AND they can be found by your
C++ compiler. In this case, there is nothing to do.
In any case, if you want to quickly check if you are in this
best case situation, do the following:
% cd ${CORE_PATH}
% make testgmp
This test simply computes 12345 * 67890. If the answer
838102050 is shown, you have passed this test and
you may go to STAGE 2.
b) If you have compiled and installed GMP in some
directory which cannot be found by your compiler, then make a
symbolic link from ${CORE_PATH}/gmp using the following command:
% cd ${CORE_PATH}
% ln -s ${your_gmp_install_dir} gmp
% make testgmp
If you pass this test, you can go to STAGE 2.
E.g., The default gmp installation will install the
header file and library files in /usr/local/include
and /usr/local/lib (respectively). Hence, in this case,
${your_gmp_install_dir}=/usr/local.
c) If you need to install gmp, and assuming you have downloaded
our full distribution, follow the following steps:
% cd ${CORE_PATH}
% make first -- this is equivalent to "make configure"
-- it uses the configuration program in gmp
-- it searches for system information
(compiler, CPU, files, etc).
-- screen output from this process is placed
in the file ${CORE_PATH}/tmp/DIAG_CONFIG.
(E.g., if you do not have m4, the error will
be detected here.)
% make second -- this is equivalent to "make gmp"
-- this compiles gmp
-- screen output from this process is placed
in the file ${CORE_PATH}/tmp/DIAG_GMP
% make third -- this installs gmp
-- screen output from this process is placed
in the file ${CORE_PATH}/tmp/DIAG_GMPINSTALL
% make testgmp -- you must pass this test to continue
in the file ${CORE_PATH}/tmp/DIAG_TESTGMP
IMPORTANT: Our top level make file is written for GNU's gmake.
The remaining make files in subdirectories should work with other
make programs. The first and second steps takes 10-20 minutes.
3.5) STAGE 2: BUILD CORE LIBRARY.
% cd ${CORE_PATH}
% make fourth -- this is equivalent to a plain "make", or
"make core", or "make corelib; make corex;
make demo".
-- screen output is placed in the files
${CORE_PATH}/tmp/DIAG_X where X = CORELIB,
COREX or BUILD_DEMO.
This creates the library files "libcore++.a", "libcorex++_level1.a"
and "libcorex++_level3.a", and store them under ${CORE_PATH}/lib.
The source files for the Core Library are found in
${CORE_PATH}/src. If you only want to make "libcore++.a", type
"make" while in ${CORE_PATH}/src.
IMPORTANT: the compilation settings for STAGE 2 are found in
${CORE_PATH}/Make.config. See the Make.config file and also
step 3.9) below.
3.6) STAGE 3: TESTING AND TIMING.
If you had chosen LINKAGE to be "shared" above, then make sure
that your LD_LIBRARY_PATH contains the directory ${CORE_PATH}/lib
(see 3.9(4) below).
% cd ${CORE_PATH}
% make fifth -- equivalent to "make test". Screen output is
placed in the file ${CORE_PATH}/tmp/DIAG_TEST_DEMO
This tests all the previously compiled programs
in ${CORE_PATH}/progs. Many of the programs are self-validating:
if an unexpected value is computed, it will output "ERROR!"
instead of "CORRECT!". Sometimes, the output says "INCORRECT!" but this
is not considered an error (e.g., with Level I accuracy, this
is expected). You can browse the output in the DIAG_TEST_DEMO file
(search for the word "ERROR" to catch obvious errors).
You can also time it:
% make sixth -- equivalent to "make time"; it uses the "time"
utility to measure the time "make test"
-- screen output is placed in
the file ${CORE_PATH}/tmp/DIAG_TIME
3.7) USING CORE LIBRARY.
Assume that you have a stand alone C++ program "foo.cpp".
In the ideal case, you only have to insert the preamble:
#ifndef CORE_LEVEL
# define CORE_LEVEL N // N=1,2,3. Defaults to N=3 if omitted
#endif
#include "CORE/CORE.h"
This should be placed after your standard include
files (e.g., <iostream.h>). You can now compile it as usual:
g++ -I${CORE_PATH}/inc -I${CORE_PATH}/gmp/include \
foo.cpp -o foo \
-L${CORE_PATH}/lib -L${CORE_PATH}/gmp/lib \
-lcore${VAR} -lgmp -lm
For more information, please go to ${CORE_PATH}/progs/generic for
samples, and also read the tutorial in ${CORE_PATH}/doc.
3.8) PLATFORMS.
Version 1.7 has been tested on
sun solaris 5.8 -- g++-2.95.3, g++-3.2, g++-3.3, g++-3.4
-- (gmp 3.1.1, gmp 4.0.1, gmp 4.1, gmp 4.1.2)
-- (gmp 4.1.3, gmp 4.1.4)
-- Sun's WorkShop 6 (C++ 5.3)
Debian Linux 2.4.9 -- gcc version 2.95
cygwin -- g++-3.2, g++-3.3, g++-3.4
mingw -- g++-3.2, g++-3.3, g++-3.4
Windows -- Visual C++, version 6.0, 7.0, 7.1
NOTE : for users who prefer a unix/linux type environment that is
embedded within the Windows' world, we highly recommend the Cygwin
platform as an easy-to-use environment. Cygwin and Windows
can freely access each other's files (a big bonus).
3.9) VARIANT INSTALLATIONS
(1) INSTALLING BASE DISTRIBUTION:
This assumes you already have an installed gmp.
-- Download the file core_vX.Y.tgz (for version X.Y) from our
website, http://cs.nyu.edu/exact/core. This version has no
gmp and no documentation.
-- Do the UNPACK STEP (Step 3.2) above. This creates the files
under ${CORE_PATH} as described above.
At this point there are two possibilities.
You may not have to do anything. To test this, try the following:
% cd ${CORE_PATH}
% make testgmp
If this compiles a test program and prints an encouraging message,
you may continue from STAGE 2 (Step 3.5) above.
Otherwise assume that your gmp is installed at $(MY_GMP_DIR). For
instance, if you have installed a full version of Core
Library at $(MY_CORELIB) then $(MY_GMP_DIR)=$(MY_CORELIB)/gmp.
-- Link Core Library to pre-installed gmp by performing these steps:
% cd ${CORE_PATH}
% ln -s $(MY_GMP_PATH) gmp
% make testgmp
This should compiles and prints an encouraging message.
Continue from STAGE 2 (Step 3.5) above.
(2) INSTALLATION FOR WINDOWS PLATFORM
If you use cygwin on your windows platform, then the installation
is same as on Unix platform as described above.
But if you use Visual C++ instead, then follow these steps.
-- Download the file core_vX.Y_full.tgz (for version X.Y) from our
website. (We recommend the Full Distribution since it contains
gmp already and you cannot easily link to preinstalled gmp)
-- Unpack it into some directory ${CORE_PATH}.
-- Unpack ${CORE_PATH}\gmp-xxx.tar.gz into ${CORE_PATH}\win32: this
creates a subdirectory ${CORE_PATH}\win32\gmp-xxx. Rename this
to plain ${CORE_PATH}\win32\gmp.
-- Install gmp patches
c:\>cd ${CORE_PATH}\win32\patches
c:\>patch xxx // where "xxx" is the gmp version;
// (xxx = "3.1.1", "4.0.1", "4.1-static",
// and "4.1-dynamic" available)
// for GMP 4.1.2, you still can choose
// "4.1-static" or "4.1-dynamic".
-- Open a "Command Prompt" window and run "vcvars32.bat" to setup
Visual C++ command line environment. File vcvars32.bat is
automatically created by your Visual C++. E.g., sometimes it is
found in C:\"Microsoft Visual Studio"\vc98\Bin.
-- Compile gmp and the Core Library:
c:\>cd ${CORE_PATH}\win32
c:\>nmake
This nmake also creates the Core Extension libraries and
and all the demo programs.
-- Optional: Testing (for the demo programs)
c:\>cd ${CORE_PATH}\win32
c:\>set PATH=%PATH%;${CORE_PATH}\win32\lib
c:\>nmake test
-- Alternatively, use Visual Studio IDE to compile the Core Library
and Core Extensions. E.g., to compile Core Library, open the
project file "core.dsw" under ${CORE_PATH}\win32\corelib, and
compile. To compile Core Extensions, open the project file "
corex.dsw" under ${CORE_PATH}\win32\ext, and compile.
(3) CORE USAGE FOR WINDOWS PLATFORM
If you want to create your own Visual C++ project file, do the
following steps:
-- add "${CORE_PATH}\inc", "${CORE_PATH}\win32\gmp" into "Include Path".
-- add "${CORE_PATH}\win32\lib" into "Lib Path".
-- Enable "Run-Time Type Information" in your project settings.
(4) SHARED OR STATIC LIBRARY LINKAGE:
In Make.config, you can set the LINKAGE variable to "shared" or
"static". The default is "static" for simplicity; but the
executables will be fairly large (over 1MB each).
To run programs using the static library there is nothing
special to do; to run the dynamic version of the Core Library,
you could move your compiled CORE, gmp, etc, libraries
into the standard library paths (e.g., /lib or /usr/lib).
Alternatively, you can set the environment
variable LD_LIBRARY_PATH as follows:
for "csh/tcsh",
% setenv LD_LIBRARY_PATH \
${CORE_PATH}/lib:${CORE_PATH}/gmp/lib:${LD_LIBRARY_PATH}.
for "bash",
$ export LD_LIBRARY_PATH= \
${CORE_PATH}/lib:${CORE_PATH}/gmp/lib:${LD_LIBRARY_PATH}.
If gmp is not installed in ${CORE_PATH}, adjust accordingly.
(5) RECOMPILATION OF THE CORE LIBRARY:
Sometimes you may want to recompile the Core Library (perhaps after
changing a file in ${CORE_PATH}/src or $(CORE_PATH)/inc).
The simplest is to go into ${CORE_PATH}/src and type
"make clean; make". This will automatically
update the files libcore++.a and/or libcore++.so in ${CORE_PATH}/lib.
But for experimental purposes, we may want to keep two or more
versions of libcore++.a around. In this case, we suggest using the
VAR variable described next.
(6) DEBUGGING AND OTHER VERSIONS OF CORE LIBRARY:
It may be useful to have different compiled versions of the Core
Library around. For this, you must edit file ${CORE_PATH}/Make.config.
This file defines the compilation flags, depending on the platform.
There are two main variables to set: VAR and PLATFORM.
VAR indicates the "variant" of the library you want to compile.
The Makefile creates the library file "libcore++$(VAR).a", which will be
placed in ${CORE_PATH}/lib/. Since the default value of VAR is
the empty string, the default library is the plain "libcore++.a".
Here are two useful variants, Debug variant and NoOpt variant:
(a) VAR=Debug: you need this variant to run the GNU debugger, gdb.
If you set VAR=Debug in Make.config, and then re-do STAGE 2 above
(STAGE 1 does not have to be re-done), you will create the debugging
variant of the library, namely "libcore++Debug.a". The other stages
will similarly create the Debug variants, e.g., Debug versions
Core Extension libraries, sample programs, etc.
(b) VAR=NoOpt: this version turns off all compiler optimizations.
Try this if you find mysterious bugs, and want to rule out the
possibility that they are caused by aggressive compiler optimizations.
PLATFORM is used to define various variables that are platform-
and compiler-specific. It defaults to "gnu".
Other possible values are "sun", "cyg", "mingw", "sgi".
The "sgi" option has not been tested in the latest library.
3.10) CORE EXTENSIONS.
Under ${CORE_PATH}/ext, you will find extensions of Core Library
to encode knowledge of algebraic and geometric domains. These
"CORE Extensions" (COREX) are quite rudimentary at present, but
feel free to contribute.
For instance, there is a geometry2d and geometry3d. We compile a
Level 1 and Level 3 versions of these libraries, so that you can
compile your application in either of these two accuracy levels.
3.11) HOUSEKEEPING AND UNINSTALL
To uninstall the library, simple delete all the files under
${CORE_PATH} (i.e., we do not put files anywhere).
In every directory, we have a Makefile with two targets called
"clean" and "veryclean". If you want to save space, you can type
"make clean" in any directory to remove temporary files.
E.g., *.o files. If you type "make veryclean", this will,
in addition, remove more files (in particular, all executable files).
NOTE: both targets are recursively propagated into subdirectories.
*************************************************************
4) NEWS, PLANS AND BUGS
NEW in Version 1.7:
-- Introduction of plane algebraic curves and bi-variate polynomials
The main capability is to plot curves and do basic
intersection tests. See CORE_PATH/progs/curves/.
-- Introduced "InCore", an interactive version of Core Library
based on Python (this has to be downloaded separately)
-- Enhancement of the univariate polynomial and real algebraic
number facilities. New methods such as
polynomial GCD, resultant, square free part, primitive part, etc.
* Polynomial<NT> can now work with all choices of NT
NT = BigInt, int, BigRat, Expr, BigFloat
But not all functionality are fully available for
NT=BigFloat and NT=Expr (e.g., rootbounds).
* Sturm<NT> can now work with NT=BigFloat
* To support the above, various new methods are added to the
BigInt, BigRat, BigFloat and Real classes (isDivisible, gcd, etc).
* Polynomials now accept string inputs.
E.g., Polynomial<BigInt> p = "x^3 - 2x^2 + 17x - 4";
-- Compatibility with gmp 4.1, and gcc 3.3
-- Introduced a common Reference Counting facility for all
Core number types, encoded in the two templated classes:
RCRepImpl<class N>
to create Reps of the class N. The basic functions provided by
this class is reference counting, and gives us the "Reps" of
each number type (e.g., BigIntRep is derived from RCRepImpl).
The other class is
RCImpl<class T>
which is the actual number type (e.g., BigInt is derived
from RCImpl<BigIntRep>). As a result former Rep Files
such as RealRep.h can be removed, and the code size is reduced.
Also, BigInt and BigRat now have reference counting in
their Rep classes (none before).
-- Speedup from reorganization of Core Library number classes.
We wrote wrappers around gmp's C function library.
We also tested the possibility of using gmp's C++ classes (since
gmp 4.1) which are template based. CORE's interface are not fully
compatible with gmp since since we have exact algebraic representation
and precision bounds.
We compared three versions of Core Library:
(A) -- old code: version 1.6
(B) -- new code: some optimization
(C) -- new code: optimzation + using gmp C++ class
Here are the running times on two machines:
Test Pentium III (1G Memory) Jinai (Solaris)
=======================================================
> A 64.12s 1m:07s
> B 56.52s 52.6s
> C 50.71s 50.4s
> Speedup 20% 25%
Although the use of gmp C++ classes (which use expression template
to eliminate temporary variables) is faster, it is
incompatiable with visual C++ (not sure about Sun CC).
So we added as an option for compiling the Core Library:
to turn on gmp C++ classes, uncomment macro CORE_USE_GMPXX
in CoreImpl.h and recompile Core Library; there is no need to compile
GMP C++ library since all necessory code are in Core Library already.
-- Updated Core Library Tutorial
-- Simple openGL display for curves: see CORE_PATH/ext/graphics/
-- Bug fixes
* rootOf(P,i) now works properly when P have multiple roots
(reason: we assumed the endpoints of isolating intervals
have distinct signs)
* Fixed bugs in Newton and Sturm methods
* Expr::doubleValue() is now correctly implemented.
E.g., suppose you compute
double s = sqrt(n);
double ss = sqrt(Expr(n)).doubleValue();
Then we guarantee that |s-ss| has relative error at
most 4*CORE_EPS = 4.44089e-16 (CORE_EPS is machine epsilon).
This factor of 4 is essentially the best possible (see
CORE_PATH/progs/testIO/testSqrt.cpp).
* fixed Expr::degreeBound(). Previously it always returned 1 at
leaves. But with algebraic numbers, it must return d_e()). This
has dramatic improvement in speed. Ron Wein's program for
intersecting two ellipses used to take overnight, but now take
0.4 sec.
* Fixed an output bug that has been around since Core 1.4.
BigFloat can print an output whose exponent is off by 1.
E.g., sqrt(100) = 9.999e0 but BigFloatRep::round(...),
an internal function, returns the string "1.0000e0"
instead of "1.0000e1". Thanks to Blazi for noticing this.
-- Miscellaneous:
* Previously, the library version numbers have two numbers
(e.g., "1" and "6" in Version 1.6). Between official releases,
we call it Version 1.6x. Thus "Version 1.6x" refers to any
number of unofficial releases between 1.6 and 1.7.
We now have a third number. E.g., this official release
is Wersion 1.7.0.
* CORE::core_error() is enhanced to write its results
into a file "Core_Diagnostics" but also writes errors to
std::cerr (as before).
* We introduce new versions of the BigFloat::makeExact(), namely,
makeCeilExact() and makeFloorExact().
* Upgraded Core Library to be compatible with the latest gmp
4.1.3 (released 4/28/2004).
* Use the program "astyle" to beautify all our code, so the
files are more consistent and readable. Tab are converted
to spaces, use k&r style, etc):
./astyle --style=kr -s2 filename
* More use of BigFloats to replace Expr, when possible. E.g.
CauchyLowerBound() and CauchyUpperBound() rewritten using
BigFloat instead of Expr (30% improvement here).
* In CORE_PATH, you can type "make options"
to see all your currently selected CORE ENVIRONMENT VARIABLES.
If you type "make alloptions", this will also show
all possible alternatives that you could have chosen.
* Simple timing facility (see src/Timer.h)
-- Acknowledgements: Thanks for feedback and bug reports from
Janos Blazi, Arno Eigenwillig, Ovidiu Daescu,
Andreas Fabri, Michael Hemmer, Athanasios Kakargias,
Daniel Russell, Ron Wein.
PLANS:
-- improved precision-sensitive algorithm
-- improved bounds (measure of Sekigawa, etc)
-- better floating point filters
-- optimized determinant primitive and filters
-- compilation and optimization of expressions
-- Expressions should have the ability to output exact values
in case of integers or rational numbers. Currently,
only bigFloat values are output.
-- complex numbers
-- better implementation of relative precision bounds
-- Newton-based algorithms for elementary functions
-- development of Core Extensions (geometry, algebra, meshes, etc)
-- graphical support and interface
-- File I/O of Core Objects (e.g., expressions)
-- CORE versions of "printf" and "scanf" (this will reduce the fuss to
CORE-ize a standard C program).
-- the exponent of a bigFloat number is represented by
a machine long. This should not be a problem in practice. An
improvement is to use machine double for the exponent,
yielding 53 bits of precision.
BUGS:
-- To report a bug, please send email to exact@cs.nyu.edu, with as
much details as possible (including your platform/compiler).
-- Let r = 54. Suppose you convert a rational p/q to a BigFloat bf
using r bits of relative precision. Next convert bf to a machine
double md,
double md = (double)bf;
This md should be equal to rounding "p/q" to the nearest machine
double. Turns out (Core 1.4) this may not be true!
But if r=59, our tests indicated that md does equal the machine
rounding of p/q. This bug is not too serious since,
for any particular inputs, it can be removed by increasing r.
Tests suggest that r=59 is sufficient for
all p/q. See ${CORE_PATH}/src/test/ for details.
-- we should allow defOutputDigits to be CORE_INFTY, and when
a rational number is printed in this case, we ought to print
it with no errors. Currently, we let defBigFloatOutputDigits
control this output; since this value is never infinite,
the printed value may have error.
-- level II is not fully supported
-- level IV is not fully defined
*************************************************************
5) ACKNOWLEDGEMENT and BRIEF HISTORY
This work has been supported by a National Science Foundation
Grant \#CCR 9402464 and \#CCR 0082056 (an ITR grant).
The Real/Expr Package (1994-96) was developed by
Chee Yap and Tom Dube.
Koji Ouchi and Chee Yap further improved the Real/Expr Package with
its concept of composite precision bounds.
The new algorithms for BigFloat with automatic error bounds
is documented in Koji's masters thesis.
A Numerical Accuracy API (the 4 levels of accuracy) was
proposed by Chee Yap in Oct 1998.
Core Library Version 1.1 (Jan 1999) was adapted from Real/Expr by
Chee Yap, Vijay Karamcheti, Igor Pechtchanski and Chen Li to
implement the Numerical Accuracy API.
Compiler-based optimizations techniques were investigated.
Version 1.2 (Sep 1999) is a debugged and improved version.
The BFMS root bound was incorporated.
Version 1.3 (Sep 2000) is significantly
faster than its predecessor because of new improved root
bounds and adoption of LiDIA/CLN's bignumber as default kernel.
Version 1.4 (Aug 2001) moved from LiDIA/CLN to gmp as the main kernel.
Incremental square roots, improved precision-sensitivity algorithms,
simple floating point filters, hypergeometry package.
Version 1.5 (Aug 2002) improvements in speed and root bounds (k-ary bounds),
CGAL compatibility changes, file I/O for large mathematical constants
(BigInt, BigFloat, BigRat), improved hypergeometric package,
Version 1.6 (June 2003) introduced arbitrary
real algebraic numbers in Expr's, incorporated Polynomial and Sturm
classes into Core Library. CORE is now distributed with CGAL,
and issued under the QPL agreement.
Version 1.7 (Nov 2004) introduced algebraic curves and bivariate
polynomials. An interactive version of Core Library called "InCore"
is available. Beginning graphic capability for display of curves.
*************************************************************
6) LICENSE INFORMATION
Core Library is now under the terms of the Q Public License
version 1.0. See the file LICENSE.QPL distributed with CORE.
*************************************************************
*************************************************************
* CONTACT AND FURTHER INFORMATION:
* For comments and bug report, send email to:
* exact@cs.nyu.edu.
* Core Library Homepage:
* http://cs.nyu.edu/exact/
* CGAL Homepage:
* http://www.cgal.org/
* GEOMETRY FACTORY Homepage:
* http://www.geometryfactory.com/
* GNU/gmp Homepage:
* http://www.gnu.org/software/gmp/gmp.html
* http://www.gnu.org/home.html
*************************************************************
|