The bignum package (v. 1.2) --------------------------- Everyone is allowed to distribute this package to anyone else, as long as all changes are recorded and mentioned. If you are including this in a commercial product, be sure to distribute _all_ of the package with the product. (...writing more stuff here later, but I guess everyone knows the approximate contents of it - no warranty, no charge, and so on. I guess it is like the GNU concept. Read that for further details...) Install: Un-tar the archive and type `make'. This will create the object file `bignum.o'. It will also create a few things on its way; `mkhdr' that creates `internal.h' with definitions that make bignum.c portable through a wide variety of architectures and compilers. If you want to run tests on the code, type `make all' to create `bigtest' and `pi'. `bigtest' does some extensive computation and checks that the results are right. The file `makefile.dos' is the same as `Makefile', but it should work in an IBM-DOS environment. Files: bignum.c - Contains the code that implements bignums. bignum.h - Header file for all external functions from `bignum.c'. mkhdr.c - Program to create `internal.h' that contains some machine-dependent integer type definitions. Also prepares a few `defines' for the random number generator. internal.h - File created by the program mkhdr. bigtest.c - Program to do some simple testing on implementation correctness (not complete yet). pi.c - Small program to compute pi to a given number of decimal places. Represented as a bignum, without an implicit decimal point after the first digit. The last m digits (m small) are incorrect due to rounding errors. pi2000.txt - File with 2000 digits of pi. Generated by pi.c. Run `pi' with an argument of 2000, and check that the last digits are the same. Then you can be quite sure that it works correctly. Makefile - Makefile for use with `make'. makefile.dos - The same as Makefile, but for an IBM-DOS environment. DESCR - Describes how to write code that use this bignum package. README - This file. Goal: Implement bignum functions that conform to the Common Lisp standard on integer numbers, also with two's complement behaviour on bitwise operations. Drawbacks: The code becomes a little cumbersome when you have to keep track on temporary variables in a complex expression. Also quite painful to be forced to `create' and `destroy' bignums when entering and leaving a function. The good thing with it is that the space allocated for temporary variables isn't thrown away immediately and can be reused many times before it is returned to the system. Requirements: o Numbers must be represented in two's complement binary notation. o Integer division must be truncating towards zero. o There must be at least one integer type that is twice as large as another integer type. `mkhdr' determines which these two are. Comments and bug reports: Please mail any suggestions and/or bug reports to my e-mail address. If you make changes to the code, be sure to write a good comment on what you did, and why. Please notify me when you do. When you implement anything you want to share with others, please feel free to do so, but send me the additions so that I can add it to the distribution of this package. You will be mentioned among the contributors to this package. Bugs (currently known): o `big_round' doesn't round to nearest _even_ integer when exactly halfway between 0 and denominator. o `bigtest.c' uses strings that are quite long. You may encounter problems if your compiler can't handle strings of long length. Some compilers don't even complain about it. To do: o Make `big_round' produce correct results when rest is exactly halfway between 0 and the denominator. o Implement conversion functions. big_image - Return a pointer to an image, that can be stored on disk, of a bignum. Useful for fast loading and saving of bignums between runs. big_set_image - Set a bignum to the `value' of the image. big_binary - Return a pointer to a portable image, that can be stored on disk, of a bignum. Useful for quite fast loading and saving of bignums between architectures. big_set_binary - Set a bignum to the `value' of the portable image. o Implement bit-wise operations. These should behave as if the bignums were stored in two's complement binary notation. big_shift_left big_shift_right big_or big_and big_xor big_not o Speed up multiplication when arguments allow (eg. c = a * a). Maybe implement multiplication with intelligent transformations as described in Knuth's "Seminumerical Algorithms" or better if there are any such algorithms available. o Implement `big_isqrt' (square root). o Implement `primep' that returns 1 if the bignum is prime, and 0 otherwise. This can be done in many ways, so perhaps it is best to write a number of primality testing functions. Probability testing is the only possible method on _large_ numbers, so there must be a way to specify how sure one wants to be that it is a prime. Contributors: Henrik Johansson (Henrik.Johansson@Nexus.Comm.SE) Wrote the foundation and the most needed functions. - big_init_pkg, big_release_pkg, big_create, big_destroy, big_bitcount, big_set_big, big_set_long, big_set_ulong, big_set_string, big_long, big_ulong, big_string, big_sign, big_abs, big_negate, big_compare, big_lessp, big_leqp, big_equalp, big_geqp, big_greaterp, big_zerop, big_evenp, big_oddp, big_add, big_sub, big_mul, big_trunc, big_floor, big_ceil, big_round, big_random, big_expt, big_exptmod, big_gcd. References: Knuth's "Seminumerical Algorithms" explained how to do `long division', and how to implement a simple random number generator. ---- e-mail: Henrik.Johansson@Nexus.Comm.SE snailmail: Henrik Johansson Box 857 S - 751 08 Uppsala SWEDEN