Big Integers to Base 1e18

• Download source - 34.42 KB

Introduction

The download is a small library of big integer functions in the form of a Visual Studio 2008 project. It is currently set to .NET 3.5 but will probably compile and work fine with any of the earlier versions.

The subroutines provide representation for non-negative integers of arbitrary size and provide the simple arithmetic operations on them. There is a function named form_comma_grouped_numeric_string for converting an integer from the internal form to a traditional sequence of decimal digit characters for display.

An integer is represented internally by a C# array of C# 63 bit long integers. The array length is currently limited by the C# default array indexing that allows for array length of about 2^31, but C# has a way to remove that limitation if there should ever be a motive to do so. The arithmetic operations are performed to base 1e18 in order to:

1. take advantage of the arithmetic capability of the x86 and x64 processors
2. achieve reasonable storage efficiency on disk for very large integers, and
3. facilitate conversion between internal and external decimal representations

A square root function has not yet been included. There is a start on a function to provide rational approximations for the natural logarithms of 2, 3, 4, 5, 6, 8, 9, & 10 but it is not yet finished. (I got too busy on something else.)

Multiplication and division are done using the grammar school algorithms; there are not currently any number theoretic enhancements. Possible accelerations of multiplication via Booth's algorithm or FFT integer convolution have not been explored. The CodePlex site offers a package called IntX as an arbitrary precision integer library in pure C# that implements fast - O(N * log N) - multiplication & division algorithms.

Background

The author has no expertise in this area and does not know how any of the existing bit integer packages work.

Using the Code

There is a function named test_big_dec( ) which can be used to test various other functions and can be consulted for example, of how other functions are called. Various parts of test_big_dec( ) can be commented in or out.

The functions likely to be called by a user are the constructor cl_big_dec which instantiates new big_dec entities and the functions load_long_into_big_dec, sum, dif_pos_and_compare, prod, power, div, mult_by_long, and div_by_long whose roles should be clear from their names with the exception of div_by_long, which gives the remainder as well as the quotient and which gives both of them as big_decimals.

The following is a snippet from function test_big_dec( ) [with leading period chars to restrain the site software's reformatting instincts.]

const long base_1e18 = 1000000000000000000L;
...
cl_big_dec bd_numer = new cl_big_dec( 10 );
cl_big_dec bd_denom = new cl_big_dec( 6 );
...
cl_big_dec bd_quotient, bd_remainder, bd_whole, bd_reconstructed_numerator ;
...
bd_numer.long_array[ 0 ] = base_1e18 - 1;
bd_numer.long_array[ 1 ] = base_1e18 - 1;
bd_numer.long_array[ 2 ] = base_1e18 - 1;
bd_numer.long_array[ 3 ] = base_1e18 - 1;
bd_numer.long_array[ 4 ] = base_1e18 - 1;
bd_numer.long_array[ 5 ] = base_1e18 - 2;
bd_numer.long_array[ 6 ] = base_1e18 - 1;
bd_numer.long_array[ 7 ] = base_1e18 - 1;
bd_numer.long_array[ 8 ] = base_1e18 - 1;
bd_numer.long_array[ 9 ] = base_1e18 - 2;
...
bd_denom.long_array[ 0 ] = base_1e18 - 1;
bd_denom.long_array[ 1 ] = base_1e18 - 1;
bd_denom.long_array[ 2 ] = base_1e18 - 1;
bd_denom.long_array[ 3 ] = base_1e18 - 1;
bd_denom.long_array[ 4 ] = base_1e18 - 1;
bd_denom.long_array[ 5 ] = base_1e18 - 1;
...
div( bd_numer, bd_denom, out bd_quotient, out bd_remainder );
prod( bd_denom, bd_quotient, out bd_whole );
sum( bd_whole, bd_remainder, out bd_reconstructed_numerator );
if ( compare( bd_numer, bd_reconstructed_numerator ) != 0 )
{
...throw new Exception( string.Format
......( " {0} "
......, "test_big_dec( ) failed the test of div with large multi_element denominator"
......) );
}

Points of Interest

The one part of the package that might be considered interesting is the procedure for finding the next base 1e18 'digit' of the quotient in the long division operation. (See the code.)

History

• 2009_01_07, ltkj, moved some explanatory information from messages to section 'Using the Code' above and added mention of the IntX library