Bbnum library

From RoutineWiki

Jump to: navigation, search

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.


Construction
Conversions
Assignment
Aritmetical operations
Logical operations
Comparison
Range and magnitude
Low level




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.


Construction
Conversions
Assignment
Aritmetical operations
Comparison
mathematical functions
Low level





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

ceilCalculates the ceiling of a big float.
floorCalculates the floor of a big float.
roundzCalculates the integer rounding nearest to zero of a big float.
absCalculates the absolute value of a big float.
sqrtCalculates the square root of a big float.
logCalculates the logarithm of big float in big float base.
powCalculates the big float power of a big float base.



bmfloat auxiliar methods

normalizeAdjusts internal representation of big float.
GetNumberStatusGets 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.
Error codes table
Numerical valuedescription
0No error
1Insufficient memory
2Division by zero
3Indeterminate division
4Not a number
5Overflow
6Internal error
7Invalid value
8Indetermined
9Underflow


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.
Personal tools