11,928,732 members (52,811 online)
alternative version

17.7K views
10 bookmarked
Posted

# Big Integers to Base 1e18

, 7 Jan 2009 CPOL
 Rate this:
A C# project providing arbitrary size integers and simple arithmetic to base 1e18

## 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 `char`s 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

## Share

 Software Developer Track Shape & Use LLC United States
Develop software for railroad track geometry engineering and track maintenance and some for rail vehicle performance. Dabble in big integers and prime numbers. Work in C# in Visual Studio. Located in Marshall, MI. e-mail: lou@klauder.org.

## You may also be interested in...

 First Prev Next
 a code example Louis T Klauder Jr7-Jan-09 10:26 Louis T Klauder Jr 7-Jan-09 10:26
 Re: a code example PIEBALDconsult7-Jan-09 13:22 PIEBALDconsult 7-Jan-09 13:22
 Re: a code example Louis T Klauder Jr7-Jan-09 15:14 Louis T Klauder Jr 7-Jan-09 15:14
 another function Louis T Klauder Jr7-Jan-09 9:58 Louis T Klauder Jr 7-Jan-09 9:58
 More explanation is required PIEBALDconsult7-Jan-09 9:46 PIEBALDconsult 7-Jan-09 9:46
 overview of functions in the cl_big_dec library Louis T Klauder Jr7-Jan-09 9:30 Louis T Klauder Jr 7-Jan-09 9:30
 Re: overview of functions in the cl_big_dec library Mika Wendelius7-Jan-09 12:59 Mika Wendelius 7-Jan-09 12:59
 Last Visit: 31-Dec-99 19:00     Last Update: 28-Nov-15 14:48 Refresh 1