//This code written and owned by Terry Richards.
//terryrichards999@gmail.com
//You may use this code for personal use only.
//For commercial use, please contact me and we
//can discuss the matter.
//For the purposes of the above statements,
//"commercial use" is any use of my code in a
//product that you sell or otherwise realise
//financial gain from. It does not include, for
//example, writing a tool that you use to help
//you with your work as long as that tool is not
//subsequently included in any commercial product.
//"Personal use" is any use that is not commercial!
//About version numbers:
//The version number consists of 3 nodes A.B.C
//C changes for bug fixes, performance improvements etc.
//If C changes, you do not need to modify your code and
//it will continue to work as it did before (less any
//fixed bugs). The public interface will remain the same
//or any new parameters will have default values that
//give the same results as before.
//B changes when the public interface is expanded.
//The existing public interface will remain the same
//or will have suitable defaults as above. The interface
//will however have expanded with new functions. You do
//not need to modify your code but you might want to so
//you can use the new functionality.
//A will only change if the public interface has changed
//significantly. Changes in your code will be required. I
//hope this will never happen but I'm allowing for the
//possibility.
//Version 1.1.0
//Change log
//Version - Modification
//1.0.0 - Initial release.
//1.1.0 - Added Trig functions Sin, Cos, Tan and their Arcs.
// - Fixed % and %= operators to only use the integer part.
// They really didn't make much sense using the decimal part.
// - Provided TwoPi and HalfPi constants.
// - Tidied up all calls to Divide function to use decimal
// places parameter correctly.
// - Major performance improvement in AlignDecimals which is
// called by all of the comparison operators and add and
// subtract which, in turn, are called by just about everything.
// - Fixed a bug in streaming where the leading zeros were being
// lost for numbers less than 0.1
// - Tracked down the last few internal uses of operator / and
// replaced them with calls to Divide.
// - Expanded the E and PI constants to 40 decimals.
// - Fixed bug in ResolveDP.
// - Fixed bug in string -> XInt conversion where numbers in the
// form 0.xxx were treated as octal if all x < 8.
// - Major performance enhancement in StreamOut() for decimal
// format.
// - Added Add, Subtract and Multiply functions to act as
// surrogates for the existing operators. This will allow
// future expansion.
//1.1.1 - Simplified the comparison operators. They now use the
// Compare function which does one pass and returns the
// result (GT/LT/EQ).
// - Changed memory management. Whenever new words are needed
// the code now allocates more than necessary. Seperate counts
// are kept of the number of words being used and the number
// actually allocated and any growth can simply grow into the
// unused words. Similarly, any shrinkage does not actually
// release the words, it just reduces the count of the words in
// use. Note that the content of the unused words is not
// guaranteed and we have to take care to initialise any words
// used from this pool. This is a classic space versus speed
// trade-off. If you are in a tight memory situation, you
// can set XI_EXTRA_WORDS to zero which will result in words
// only being allocated one at a time as they are needed. All
// memory management is now performed by GrowBy()/GrowTo().
// - Fixed bug in Round() where zero was sometimes rounding up.
// - Incorporated the MatchWords() logic into AlignDecimals() as
// it was always called immediately after AlignDecimals() and
// not from anywhere else. In honour of its added duties,
// AlignDecimals() is now called Align().
XInt is a big number class that is designed to be a "drop-in"
replacement for both integers and all floating point types. In
theory, you could take an existing programme, replace all
integer and floating point types with XInt and it should
compile and run exactly as it did before but with greater
precision.
There are some exceptions (aren't there always?) Obviously,
if you are relying on over/underflow behaviour, it won't work,
XInt does not overflow! It will underflow but in a controlled
fashion and you can specify how it behaves.
XInt stands for eXtended Integer. In fact, they are extended in
two directions - left and right. The left extension is the fact
that they do not have a size limit (except for available memory)
and the right extension is that they have decimal places (also
unlimited except for available memory).
A large part of math.h has been overloaded for XInt and the rest
will follow. The functions that have not been overloaded (e.g. sin
cos, etc.) can still be accessed as there are conversion operators
to and from long double. Obviously, these will be limited to the
precision of a long double but that's what you have now. In a future
release I will provide native versions of at least some of these
functions. If you have a particular one you would like implemented
please let me know and I will try and prioritise it.
Similarly, I would love to hear any comments you have on the code,
positive or negative! I would especially like to hear from you if you
find any bugs or if you write your own #elif block (see below).
I will credit anybody that sends me bug reports and/or code in a
suitable comment. If you do not want your name added, please let me
know.
While much attention has been paid to performance, it was not
my primary concern. I was more interested in reliable and
understandable code. For instance, division uses a straightforward
subtract and shift algorithm. There are faster division algorithms
but they are a pig to implement and to understand and, at the end
of the day, they aren't *that* much faster. For values that will
fit in a single integer, performance should be similar to native
code. In a similar vein, wherever possible functions have been
implemented using other, thoroughly tested, functions. For an
example, see the comparison operators which are all implemented using
the Compare function. This at least has the advantage of keeping all
the bugs in one place!
Internally, an XInt is implemented as a dynamic array of unsigned
words, a sign bit and flags for special cases (infinity and NaN).
The word array grows dynamically as needed. I did NOT use a std
array for this as it is the very core of the class and I did not
want the performance overhead involved. This is just about the only
exception to the previous paragraph.
The #elif block
If you are compiling for platforms other than 32 or 64 bit Windows,
you will need to provide your own #elif block at the top of XInt.h.
If you do write your own, please send me a copy and I will merge it
into the code base and maintain it (if necessary for future releases)
along with my own.
The #elif block will look something like this (this is the one for 32
bit Windows):
#elif defined (_WIN32)
#define XI_WORD UINT32
#define XI_MAX 100000000
#define XI_HALF_MAX 10000
#define XI_DECS_PER_WORD 8
typedef int XI_IX;
#define XI_IX_MAX INT_MAX
On the first line you should replace _WIN32 with something that uniquely
defines your system and the build in the same way that _WIN32 defines a
32-bit Windows build.
XI_WORD should be defined as the natural unsigned integer on your system.
This may be unsigned int or unsigned long or some other.
XI_MAX should be the largest decimal number that will fit in an XI_WORD and
has an even number of zeros. You should leave at least 3 bits available
for temporary overflows.
XI_HALF_MAX should be the same as XI_MAX with half the number of zeros.
XI_DECS_PER_WORD is the number of zeros in XI_MAX.
The values below are good for the number of bits given.
BITS XI_MAX XI_HALF_MAX XI_DECS_PER_WORD
8 100 10 2
16 10000 100 4
32 100000000 10000 8
64 1000000000000000000 1000000000 18
XI_IX should be a signed integer suitable for array indexes etc.
XI_IX_MAX should be the largest positive value that will fit in an XI_IX.
It will probably be defined in limits.h as INT_MAX.
You will also need to delete or comment out the following line in XInt.cpp:
#include "stdafx.h"
and replace it with:
#include "XInt.h"
The public interfaces
Constructors:
XInt(XI_IX Val = 0, XI_IX Decimals = 0);
Used to construct an XInt ether from an integer or an integer plus
a number of decimals. E.g. XInt(5) will construct an XInt with a value
of 5, XInt(5,1) will construct an XInt with a value of 0.5.
XInt(const XInt* pOther);
XInt(const XInt& Other) :XInt(&Other){};
These two are used for copying XInts
XInt(const std::string str);
This version constructs an XInt from a string. E.G. XInt("3.14159")
will do what you would think it does. You can provide a leading or
trailing sign and white space is permitted before and after the sign
and the number. E.G. " - 2.2 " will be accepted. Hex and Octal
numbers are accepted ("0x123ff" or "01234567"). Exponential formats
("1.2 E5") are not currently supported. If a non-compliant string is
passed, results will be indeterminate and may change in future releases.
Actions
void MakeInfinite();
Sets the value of the XInt to infinity. The current sign is not changed.
void MakeNaN();
Sets the value of the XInt to not a number.
void MakeZero();
Sets the value of the XInt to zero. Zero is always positive for XInt.
void Flip();
Reverses the sign of an XInt. Note that Zero stays positive.
void Round(XI_IX Position = 0, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero);
Rounds the number to the specified position using the specified rounding
rules. Note that position 0 is the first digit left of the decimal place
so Round(0) will round to an integer value, Round (-1) will round to one
decimal place, etc. If Position is out of range, it is simply ignored and
the original number is returned. Round does not remove any digits, any
digits after the rounding position are set to zero. See SetDecimals().
There are more ways to round a number than you are probably aware of
(certainly, more than I was aware of). The defualt parameters will round
the way you learned at school (round to the nearest, fives go up). See the
XI_RoundingType and XI_RoundingFive enums for more information.
void SetDecimals(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero);
Rounds the number exactly the same that Round() does (in fact, it calls
Round() to do it). SetDecimals also removes any trailing zeros after the
specified number. Note that the NumDecimals parameter has the opposite sign
to the Position parameter for Round(). E.G. XInt("2.09").SetDecimals(1) will
return a value of 2.1. NumDecimals can be negative which will round to the
appropriate power of ten. E.G. XInt("12.09").SetDecimals(-1) will return a
value of 10.
void CopySign(const XInt& Other);
Sets the sign of an XInt to be the same as the sign of another. Note that
vales of zero and NaN will not be changed.
Query functions
bool IsZero() const;
bool IsInfinite() const;
bool IsNegative() const;
bool IsNaN() const;
bool IsNumber() const;
These all query the current state of an XInt and return what you would expect.
XInt Abs() const;
Returns the absolute (i.e. positive sign) value of an XInt.
XInt IntPart() const;
Returns everything to the left of the decimal point.
XInt FracPart() const;
Returns everything to the right of the decimal point.
XI_WORD operator [](const XI_IX Index) const;
Returns the decimal digit at an Index. Index 0 is the first digit left of the
decimal place. If Index is out of range, an implied zero is returned. E.G.
XInt("123.456")[0] returns 3, XInt("123.456")[-2] returns 5, XInt("123.456")[7]
returns 0, XInt("123.456")[-5] returns 0.
XI_IX NumSignificantDigits() const;
The total number of significant digits in a number. This is the total number
of digits before the decimal point plus the total number of digits after the
decimal point including any trailing zeros but ignoring leading zeros. E.G.
XInt("0012.3456700").NumSignificantDigits() returns 9.
Arithmetic & Math functions
XInt Add(const XInt& Other) const;
XInt Subtract(const XInt& Other) const;
Adds one XInt to another. Full precision is maintained throughout. E.G.
XInt("23.456").Add(XInt("100.0007")) will return 123.4567
Subtract just flips the sign of Other and then Adds it.
XInt Multiply(const XInt& Other) const;
Multiplies one XInt by another. Full precision is maintained throughout. E.G.
XInt("0.02").Multiply(XInt("0.03")) will return 0.006
XInt Divide(const XInt& Other, XI_IX Dec = DP_LHS, XI_RoundingType RT = RT_Truncate, XI_RoundingFive R5 = RT5_AwayFromZero) const;
Divides one Xint by another. The Dec parameter determines the number of
decimal places in the answer. Normally, this should be a positive number or
zero. There are some (currently 4) "magic" values that are negative. These
allow the code to determine a suitable number of decimal places itself. Any
other negative value is treated as zero. See the DP_ defines in the header
for more information. The rounding parameters are the same as for the Round()
function.
XInt Pow(const XInt Exp) const;
Returns the current value to the power of Exp. If Exp has a fractional part,
this is evaluated using logarithms to 30 decimal places. Otherwise it is
multiplied out to full precision. This can lead to a LOT of decimal places
in the result and you might want to call SetDecimals() afterwards. If Exp
is less than zero, this function returns one over the positive power
(i.e. 2 ** -2 = 1 / (2 ** 2)) using the decimal places of the exponential
calculation.
XInt Root(const XInt N) const;
This returns the Nth root of a number. This is evaluated using logarithms to
30 decimal places so N can be positive or negative, integer or real.
XInt Log(const XInt& Base = 2, XI_IX NumDecimals = 30) const;
Calculates the logarithm of a number. This is calculated internally to base
two and then converted, if necessary, to the requested base which means that
base 2 is slightly faster and slightly more accurate. For natural logs, use a
base of E.
XInt AntiLog(const XInt& Base = 2, XI_IX NumDecimals = 30) const;
Turns a logarithm back to a number. Once again, bases are converted to two
internally so use base 2 where possible.
XInt Sin(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
XInt Cos(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
XInt Tan(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
These convert an angle in radians to their corresponding trig. value. The
parameters are the same as for Divide.
XInt ArcSin(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
XInt ArcCos(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
XInt ArcTan(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
And these convert the trig. value back to radians.
XInt DSin(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
XInt DCos(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
XInt DTan(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
XInt DArcSin(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
XInt DArcCos(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
XInt DArcTan(XI_IX NumDecimals, XI_RoundingType RT = RT_Nearest, XI_RoundingFive R5 = RT5_AwayFromZero) const;
These are exactly the same as the equivalent without the D except that they
take/return degrees instead of radians. Internally, these are converted to/from
radians so the radian version is slightly faster and slightly more accurate.
Arithmetic operators
Note: The following overloads are mainly provided for compatability with existing code.
For new code, it is preferable to use the native functions provided by the class as they
give you more control (in some cases) whereas these use (hopefully reasonable) defaults.
XInt& operator =(const XInt& Other);
XInt operator -() const;
XInt operator +(const XInt& Other) const;
XInt& operator +=(const XInt& Other);
XInt operator -(const XInt& Other) const;
XInt& operator -=(const XInt& Other);
XInt operator *(const XInt& Other) const;
XInt& operator *=(const XInt& Other);
XInt operator /(const XInt& Other) const;
XInt& operator /=(const XInt& Other);
All of the above do what you would expect them to and are mainly implemented by passing
through to the native functions given above.
XInt operator %(const XInt N) const;
XInt& operator %=(const XInt N);
These work as you would expect them to if both values are integers. If either (or both)
have fractional parts, they are simply ignored. E.G. XInt("7.0001") % XInt("4.12134")
will return 7 % 4 = 3.
XInt& operator ++(); //++x
XInt& operator --(); //--x
XInt operator ++(int); //x++
XInt operator --(int); //x--
These add/subtract one from a value. E.G. XInt("2.345")++ will return 2.345 and set the
XInt to 3.345.
Bit operators
XInt operator ~() const;
This does work but the results may not be what you first expected! Because we don't
actually use all of the bits in the stored words, it only flips the bits that are used.
This has the interesting effect that the results are different for different sized
builds. However, when it is used for creating bit masks, those masks (used with the
other bit operators) work as expected.
XInt operator |(const XInt& Other) const;
XInt& operator |=(const XInt& Other);
XInt operator &(const XInt& Other) const;
XInt& operator &=(const XInt& Other);
XInt operator ^(const XInt& Other) const;
XInt& operator ^=(const XInt& Other);
These all work as you would expect and also work with bit masks that have been created
by operator ~.
XInt operator >>(const XI_IX Places) const;
XInt operator >>=(const XI_IX Places);
XInt operator <<(const XI_IX Places) const;
XInt operator <<=(const XI_IX Places);
These multiply/divide by powers of 2.
Comparison operators
bool operator ==(const XInt& Other) const;
bool operator !=(const XInt& Other) const;
bool operator <(const XInt& Other) const;
bool operator >(const XInt& Other) const;
bool operator <=(const XInt& Other) const;
bool operator >=(const XInt& Other) const;
These all work as you would expect them to for valid numbers.
See the comments in the code for the behaviour for INF and NaN.
Streaming
void StreamOut(std::ostream& os) const;
void StreamIn(std::istream& os);
These are used by the external >> and << operators and also internally.
Conversion operators
void operator = (const CString& Source);
operator CString () const;
Convert to/from an MFC CString. These are only defined for MFC builds
(_AFX is defined).
void operator = (const std::string& Source);
operator std::string() const;
Convert to/from a std::string
void operator = (const XI_IX Source);
operator XI_IX() const;
Convert to/from an XI_IX (and therefore, most flavours of integer)
void operator = (const long double Source);
operator long double() const;
Convert to/from floating point
void operator = (bool Source);
operator bool() const;
Convert to/from a bool. Like integers, any non-zero value is true
Math.h overloads
Note: The following overloads are mainly provided for compatability with existing code.
For new code, it is preferable to use the native functions provided by the class as they
give you more control (in some cases) whereas these use (hopefully reasonable) defaults.
These are not declared as friends because they only use public interfaces
Any functions not specifically overloaded here (e.g. the less common trig functions) can still be
used via the long double conversion operators. However, this may result in loss of precision
and/or overflow conditions. I am currently working on implementing these functions natively.
inline XInt abs(const XInt A);
inline XInt acos(const XInt A);
inline XInt asin(const XInt A);
inline XInt atan(const XInt A);
inline XInt atan2(const XInt A, const XInt B);
inline XInt cbrt(const XInt A);
inline XInt ceil(const XInt A);
inline XInt copysign(const XInt A, const XInt B);
inline XInt cos(const XInt A);
inline XInt exp(const XInt A);
inline XInt exp2(const XInt A);
inline XInt expm1(const XInt A);
inline XInt fabs(const XInt A);
inline XInt fdim(const XInt A, const XInt B);
inline XInt floor(const XInt A);
inline XInt fma(const XInt A, const XInt B, const XInt C);
inline XInt fmax(const XInt A, const XInt B);
inline XInt fmin(const XInt A, const XInt B);
inline XInt fmod(const XInt A, const XInt B);
inline XInt ldexp(const XInt A, int B);
inline XInt log(const XInt A);
inline XInt log10(const XInt A);
inline XInt log1p(const XInt A);
inline XInt log2(const XInt A);
inline XInt logb(const XInt A);
inline XInt lrint(const XInt A);
inline XInt llround(const XInt A);
inline XInt modf(const XInt A, XInt* B);
inline XInt nearbyint(const XInt A);
inline XInt pow(const XInt A, const XInt B);
inline XInt remainder(const XInt A, const XInt B);
inline XInt remquo(const XInt A, const XInt B, XInt* C);
inline XInt rint(const XInt A);
inline XInt round(const XInt A);
inline XInt sin(const XInt A);
inline XInt sqrt(const XInt A);
inline XInt tan(const XInt A);
inline XInt trunc(const XInt A);
Streaming
These are not declared as friends because they only use public interfaces
std::ostream& operator<<(std::ostream& os, const XInt& A);
std::istream& operator>>(std::istream& os, XInt& A);
These will insert or extract an XInt to/from a stream. Stream formatting
of dec, hex and oct are respected and fill and width are provided by the
stream itself. Exponential format (2E5) is not yet supported. Only XInts
without a fractional part can be streamed in hex or oct modes.
Download Latest Version
XInt.zip (16.7 kB)
