Click here to Skip to main content
Click here to Skip to main content

Big Integers to Base 1e18

, 7 Jan 2009
Rate this:
Please Sign up or sign in to vote.
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 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Louis T Klauder Jr
Software Developer Track Shape & Use LLC
United States 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 VS2008 on Vista 64bit. Located near Lancaster, PA. e-mail: lklauder@wsof.com.

Comments and Discussions

 
Generala code example PinmemberLouis T Klauder Jr7-Jan-09 9:26 
GeneralRe: a code example PinmemberPIEBALDconsult7-Jan-09 12:22 
GeneralRe: a code example PinmemberLouis T Klauder Jr7-Jan-09 14:14 
Generalanother function PinmemberLouis T Klauder Jr7-Jan-09 8:58 
GeneralMore explanation is required PinmemberPIEBALDconsult7-Jan-09 8:46 
Generaloverview of functions in the cl_big_dec library PinmemberLouis T Klauder Jr7-Jan-09 8:30 
GeneralRe: overview of functions in the cl_big_dec library PinmvpMika Wendelius7-Jan-09 11:59 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140827.1 | Last Updated 7 Jan 2009
Article Copyright 2009 by Louis T Klauder Jr
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid