Bbnum library
From RoutineWiki
Contents |
Credits and License details
Author(s)
The source code available in this page is copyright of the following author(s):
Maintainer(s)
The software provided in this page is maintained by:
Disclaimer
No warranty of any kind is implied for the uses of the source code provided in this page. It is provided 'as is'. Use at your own risk. See license for details.
License
This software is licensed under BSD License.
Other licenses
Please contact with the maintainer(s) for other license(s).
About the library
This library was written for providing a nice alternative to commercial and only-free software for big-numbers computing.
Known problems
- The current version of the library is not optimized for really big numbers. For numbers with hundreds of decimal digits, the library works fine. For thousands of digits, the adaptation times for computing shared constants can be more than seconds...Currently, the library dont provide fft multiplication. The cut for the fft usage seems to be around the 400 digits in my personal tests.
- It's possible that some operations uses inefficient extra precission in intermediate operations. The library is not fine tunned in that aspect. The main objective was to guarantee final precission.
Download
follow this link for downloading the library
Reference
The bbnum library is a C++ library with some critical subroutines written in assembler. All the classes provided by the library are in the bigmath namespace.
Data types
bigint
This type represents a integer value with variable length. This type is used in assembler subroutines. The compatible declaration in C/C++ is
struct bigint
{
unsigned long m_len; //Actual size in bytes
unsigned long* m_data; //binary data storing the integer in bigendian format
unsigned long m_size; //Total m_data reserved bytes
};
provided that sizeof(unsigned long) is four bytes.
The m_size field represents the total amount of memory reserved for storing the number (the buffer pointed by the m_data field), but the real used length is m_len. The m_size field is required for reducing reallocations.
This type is for use only with assembler routines. For common big integers usage, please see the bmint type.
bmint
This type represents a C++ encapsulation of the type bigint.
|
bmint construction
| bmint | Constructs a bmint object in various ways. |
bmint conversions
| operator char, int, etc | Conversions to native numeric types. |
| operator char* | Conversion to decimal representation. |
| hex | Conversion to hexadecimal representation. |
bmint assignment
| operator = | Assigns a new value to a bmint. |
bmint aritmetical operations
| operator + | Addition of big numbers. |
| operator += | Self addition of big numbers. |
| operator - | Subtraction of big numbers and sign operator. |
| operator -= | Self subtraction of big numbers. |
| operator * | Multiplication of big numbers. |
| operator *= | Self multiplication of big numbers. |
| operator / | Division of big numbers. |
| operator /= | Self division of big numbers. |
| divide | Division of big numbers. |
| operator % | Remainder of big numbers. |
| operator %= | Self remainder of big numbers. |
| operator ++ | Self increment of bmint big integer. |
| operator -- | Self decrement of bmint big integer. |
bmint logical operations
| operator >> | signed logical big number bit-shift right. |
| operator >>= | signed logical big number self bit-shift left. |
| operator << | signed logical big number bit-shift left. |
| operator <<= | signed logical big number self bit-shift left. |
bmint comparison
| operators ==, !=, <, etc | Comparison of big numbers. |
| compare | Comparison of big numbers.fast |
bmint range and magnitude
| domain | Check for negative, zero or positive big integer.fast |
| order | Exponential order of big number. |
bmint low level
| highbitset | Get the index for the highest bit with value 1. |
| highbitreset | Get the index for the highest bit with value 0. |
| lowbitset | Get the index for the lowest bit with value 1. |
| lowbitreset | Get the index for the lowest bit with value 0. |
bmint_tmp
This type represents a C++ encapsulation of the type bigint exactly like bmint but with the difference that there not exist public assignment operators nor constructors. The objects of this type are never created directly by the user. They are created as a intermediate result of bmint operations and are transparent to the user of the library. For a explanation of the existence of this type see the comments below.
bmfloat
This type represents a floating big number.
|
bmfloat construction
| bmfloat | Constructs a bmfloat object in various ways. |
bmfloat conversions
| operator char, int, etc | Conversions to native numeric types. |
| operator char* | Conversion to decimal representation. |
| operator bmint_tmp | Conversion to temporary big integer. |
bmfloat assignment
| operator = | Assigns a new value to a bmfloat. |
| setvalue | Assigns a new value to a bmfloat. |
bmfloat aritmetical operations
| operator + | Addition of big numbers. |
| operator += | Self addition of big numbers. |
| operator - | Subtraction of big numbers. |
| operator -= | Self subtraction of big numbers. |
| subtraction | Subtraction of big numbers. |
| operator * | Multiplication of big numbers. |
| operator *= | Self multiplication of big numbers. |
| operator / | Division of big numbers. |
| operator /= | Self division of big numbers. |
| divide | Division of big numbers. |
| operator % | Remainder of big numbers. |
| operator %= | Self remainder of big numbers. |
| operator ++ | Self increment of bmfloat big float. |
| operator -- | Self decrement of bmfloat big float. |
bmfloat comparison
| operators ==, !=, <, etc | Comparison of big numbers. |
bmfloat mathematical functions
| ceil | Calculates the ceiling of a big float. |
| floor | Calculates the floor of a big float. |
| roundz | Calculates the integer rounding nearest to zero of a big float. |
| abs | Calculates the absolute value of a big float. |
| sqrt | Calculates the square root of a big float. |
| log | Calculates the logarithm of big float in big float base. |
| pow | Calculates the big float power of a big float base. |
bmfloat auxiliar methods
| normalize | Adjusts internal representation of big float. |
| GetNumberStatus | Gets information about NAN situations etc. |
bmfloat_temp
This type represents a temporary floating big number exactly like bmfloat but with the difference that there not exist public assignment operators nor constructors. The objects of this type are never created directly by the user. They are created as a intermediate result of bmfloat operations and are transparent to the user of the library. For a explanation of the existence of this type see the comments below.
float_domain
This type is a enumerator for defining some of the floating processor constants. The available values are:
- number
- positive_infinite
- negative_infinite
- undeterminated
- not_a_number
These constants are not for declaring special big floats (although that can be made). They are provided primarily for checking results of some unsure floating operations (for example , 1/x when x = 0).
Parametrization
Compilation
In the header file bigmath.h there are some useful macros when compiling the library :
- _GCC : default value is 1. Undefine it when not using gcc for compilation
- THROW_EXCEPTIONS : default value is 1. Undefine if you want that the library raise exceptions.
- TROW_CAST_OVERFLOW : default value is 0. Define it if you want to get exceptions for overflow situations.
- THROW_CAST_UNDERFLOW : default value is 0. Define it if you want to get exceptions for underflow situations.
old stuff:
- TEST_SUITE : default value is 1. You can remove the TestSuite files and undefine it if you dont want the self check routines in the library.
Runtime
- Globals::SetPrecision(long maxDigits) : Use it for specifying the maximum decimal digits for float big numbers. Invoking this method will update with the appropriate values the global constants:
- Limits::maxDecimalPlaces : maximum decimal places of the mantissa of big floats.
- Limits::maxMantissaBytes : maximum binary extent of mantissa of big floats.
- Limits::maxExponentBytes : maximum binary extent of exponent of big floats.
Globals::SetPrecision will also update the value of common shared constants, according to the new precision.
Error handling
When using THROW_EXCEPTIONS macro, some functions from the library will throw exceptions, always with a string describing problem. In every case (using THROW_EXCEPTIONS or not) we can handle the errors using the following methods:
- unsigned long bienget() : returns a numerical code for the error.
- const char *biesget() : returns a text describing the current error status.
- void bieclr() : clears any error code.
- void bienset(long errcode) : sets a error code.
| Numerical value | description |
|---|---|
| 0 | No error |
| 1 | Insufficient memory |
| 2 | Division by zero |
| 3 | Indeterminate division |
| 4 | Not a number |
| 5 | Overflow |
| 6 | Internal error |
| 7 | Invalid value |
| 8 | Indetermined |
| 9 | Underflow |
Comments
Temporary classes vs. reference counting
Reusing buffers using reference counter is a common and easy-to-implement technique. We can found it in some well-known libraries for the implementation, for example, of string classes. With a reference counting we know how many objects share a common value and when is mandatory to create buffer copies. We can enumerate some goodness of this technique:
- saving memory in sharing large common constants.
- avoiding redundant copies : A single operation like y = a + b is carried first creating the value a + b using some addition operator. The result is now assigned to the y variable using some assign operator. A poor implementation makes a copy of the temporary a + b and the temporary is destroyed. With reference counting, no extra copy is created and the temporary buffer is reused. That speed up our application.
But unfortunately, the reference counting technique has some penalties:
- each non-const operation must check reference counter : Each object using reference counting is not free to modify his own buffer. The object must check first if the reference indicates that the buffer is shared. In this case, the object must make a copy and release its participation in the old buffer.
- reference counting requires extra space. That's not really a big problem since reference counting loses a very low percentage of the memory handling really big numbers.
- reference counting multithreading problems. The reference counting requires sinchronization objects in multithreading contexts. This can be really a reliability problem.
In the bbnum library we are using a more difficult to implement technique for reusing buffers: The temporary classes. These clases are instantiated never directly but as a result of operations. The operators that receive temporary values are designed for reusing buffers. This technique makes possible to resolve buffer reutilization in compilation time, rather than in run time. With this techique some possibilities from reference counting are out of scope. For example, creating a matrix of constant values we dont reuse the buffer values. But the common operations are improved :
- each non-const operation dont check anything about buffer sharing. The operation carries the correct buffer operation in each moment. For example any expression like y = a + b is carried first creating a temporary-class value a + b using some addition operator. The result is now assigned to the y variable reusing the buffer of the temporary. That increases the performance of the library.
- The temporary classes technique dont requires extra space. In practice, temporary classes are simple derived classes, for which the class is the key for method selection at compilation time.
- No multithreading problems. This technique is not buffer sharing. This is buffer propagation through nested calls in the same thread.
Projected improvements
- creation of const classes for shared values.
