Login | Register

MFC Template Class CLongInt

Posted by Thomas Holte on March 28th, 2002

The template class template <UINT bits, class T = USHORT, class LT = ULONG> class CLongInt<bits> supports long integer arithmetic. Internally, a CLongInt is represented by n digits of the integral type T (specified by the second template parameter). T must be unsigned. The first digit is the most significant digit, the last digit is the least significant digit. The number base of the internal representation of a CLongInt is 2sizeof(T)*CHAR_BIT. For example, if T is an unsigned short, the number base of the CLongInt is 65536. For internal calculations, there must also exist an unsigned integral type LT (specified by the third template parameter) which must have double the size as T. To achieve maximum portability to other C++ compilers, I've chosen unsigned short for T and unsigned long for LT.

The template parameter bits specifies the size of a CLongInt in bits. bits should be at least 64+sizeof(T)*CHAR_BIT. For smaller bit numbers, use any of the built-in simple types int, long, or __int64.

The CLongInt class implements the complete integer arithmetic. There are friend operator functions to mix CLongInt operands with int or long operands. You can easily expand the class CLongInt to mix it with __int64 operands, too.

To prevent the specification of an invalid template parameter for T or LT, the technique of compile-time assertions is applied (see header file StaticCheck.h). This technique is presented by Andrei Alexandrescu in his book Modern C++ Design (see Chapter 2.1).

CLongInt class members:

Constructors:
CLongInt() Constructs an uninitialized CLongInt.
CLongInt(const CLongInt& u) Constructs a CLongInt from another CLongInt u.
CLongInt(int u)
CLongInt(UINT u)
CLongInt(long u)
CLongInt(ULONG u)		 Constructs a CLongInt from an integral number u.
CLongInt(LPCTSTR psz, UINT nBase=10) Constructs a CLongInt from the string psz which represents an integral number with the base nBase.
Public member functions:
int Compare(const CLongInt& v) const Returns zero if the CLongInts are identical, <0 if this CLongInt is less than v, or >0 if this CLongInt is greater than v.
CLongInt Divide(CLongInt v, CLongInt* pRem = 0, bool bSigned = true) const Divides this CLongInt by v. The quotient will be returned. The remainder will be stored in *pRem if pRem is unequal zero. If bSigned is false, the division will be performed unsigned.
int ToInt() const
UINT ToUINT() const
long ToLong() const
ULONG ToULONG()		 Converts this CLongInt to an integral quantity of type int, unsigned int, long, or unsigned long.
CString ToString(UINT nBase = 10) const Converts this CLongInt to a string representing the number with base nBase.
Cast operator functions:
LPCVOID
LPVOID		 Gives access to the internal digit buffer (e.g. for copying directly from memory to a CLongInt or vice versa).
Assignment operator functions:
=, +=, -=, *=, /=, %=, <<=, >>=, &=, |=, ^=
Unary operator functions:
+, -, ++ (pre- and postincrement), -- (pre- and postdecrement), !, ~
Binary operator functions:
+, -, *, /, %, <<, >>, &, |, ^, <, <=, ==, !=, >=, >

About the Author

Thomas Holte

Born in 1953 I'm a passionate programmer since 30 years. I'm employed as a software developer at a large company in Nuremberg, Germany. My hobbies are programming (what else) and digital photography.

Downloads

IT Offers

Comments

  • Expanding the basic types T and T2 to UINT32 and UINT64; Fast Modulus

    Posted by Legacy on 03/18/2003 12:00am

    Originally posted by: Anton 

    1.) ---- UINT32 and UINT64 ----


    I replaced 

      	typedef USHORT T;

      	typedef ULONG LT;

    with

      	typedef UINT32 T;

      	typedef UINT64 LT;

    and got a performance improvement of about 20 percent with VC6


    Unfortunately the division did not work.


    I solved the problem by replacing the line

    	LT d = (1 << T_BIT)   

    with

    	LT d = (LT(1) << T_BIT)   


    2.) ---- Fast Modulus ----


    I found a nice procedure to calculate 

    	CLongInt<bits> % long

    at http://www2.ics.hawaii.edu/~wes/ICS623/Arith.html


    	(UL means UINT32, a is Little Endian)


    <Quote>

    /* This function calculates a mod k where  */

    /* a is a 512-bit (16 word) number and k   */

    /* is less than 2^15.        WP--10/02     */


    UL rr(UL *a, UL k)

    {

        int i;

        UL m, ans;

        

        m = ((0xffffffff % k) + 1) %k; /* 2^32 mod k */

        ans = 0;

        for(i = 15; i>=0; i--) {

            ans = (ans*m) % k;

            ans = (ans + a[i])%k;

        }

        return ans%k;

    }

    </Quote>


    I would be happy if you translate this algorithm into your excellent work. If you do this, the audience will probably ask for corresponding optimizations for

    	CLongInt<bits> / long

    	CLongInt<bits> * long

    	CLongInt<bits> + long

    	CLongInt<bits> - long


    

    Best regards

    Anton

    Reply

  • Bug in ToString()?

    Posted by Legacy on 03/15/2003 12:00am

    Originally posted by: Pawel Guzowski

    Why do I always get "0077042C" as the result when I do ToString(base), whatever the actual number, whatever the size, whatever the base? (maybe it's bug in my compiler, dont know, but using MSVC++).

    Cheers.

    Reply

  • This a good work! But performance is very limit

    Posted by Legacy on 01/15/2003 12:00am

    Originally posted by: Solomon Wu

    This a good work! But performance isn't very good.
    For CLongInt<T> a , when T>1000000, performance speedy change to bad

    Reply

  • Excellent. "Scientific Expression"?

    Posted by Legacy on 10/14/2002 12:00am

    Originally posted by: X Tan

    Thank you very much for your excellent work, Mr Thomas Holte.

    If the numbers could automatically expressed as scientific expression (e.g. 4e-32, 1.35e40) when the numbers are too large to appear in the fix room, it will be perfect.

    Could you please provide with some clues to do that, Thomas. Or anyone know how to do it?

    Reply

  • Beautiful

    Posted by Legacy on 10/06/2002 12:00am

    Originally posted by: Bappi 

    Hi;

    Its totally helpfull for every programmer.

    I also include my website... for my friends.

    Excellent work....I can call it ,"Our Bossom Friend".


    Thanks for everything

    Thanks again

    Bappi


    But if there some security program code then it will be more helpfull.

    Reply

  • Nice work!!

    Posted by Legacy on 09/13/2002 12:00am

    Originally posted by: Gilbert

    Thank you very much.

    It's so nice and useful thing.

    Reply

  • great work, thanks!

    Posted by Legacy on 08/20/2002 12:00am

    Originally posted by: Stefan Ganscha

    as per subject

    Reply

  • Good work, but there's a better implementation.

    Posted by Legacy on 03/21/2002 12:00am

    Originally posted by: Gabriel Praino

    Good code!!! but there's a problem with this implementation.

    In many applications, it's very common to work with very different integer sizes.

    A situation where long integers are very used are encryption algorithms. Allmost all public key algorithms used to sign and encrypt information all over the world are based on long integers, which may have 1024 or more bits.

    In this kind of applications, it's very common to work with integer of 512, 768, 1024 and 2048 bits.
    In some situations, you require even more bits to perform some kind of operations.

    If you use the maximun bit size allways, you'll get a very poor performance (encryption requires extremely fast algorithms), but compiling the code with many different integer sizes would result in an inneficient code also. If we also consider converting from a bit size to another this would becomes a caos.

    I once had to programm a class to do this, and I rather prefer to use a code which dinamically allocates memory and can handle any bit size.

    Of course, allocating memory has a cost, but in many application this is preferred.

    Reply

  • Bug in function Divide. Here's the fix...

    Posted by Legacy on 03/11/2002 12:00am

    Originally posted by: Serge Debner 

    Very nice class, but I found a bug in Divide function.

    When working with very large numbers (I'm working with 1024 bit values) 

    the result of the Divide function is not always correct.

    This happens due to the error in the implementation of Knuth's long division algorithm.

    Here's the fix I've come up with. 

    Maybe someone can come up with the better one, but this seems to be working fine for me.

    I've done a lot of testing.


    Replace the following original code:


    // Problem code starts

    /*

    for (;; q_hat--)

    {

        // The following statements build up... blah...blah...

        // ...

        union

        {

            LT L[2];

            T  S[4];

        } u_j_q_hat;

        

        u_j_q_hat.L[0] = 0;

        u_j_q_hat.S[2] = uv[j];

        u_j_q_hat.S[3] = uv[j + 1];

        // ... - vv[0] * q_hat

        u_j_q_hat.L[1] -= vv[0] * q_hat;

        if (u_j_q_hat.S[2] != 0)

            break;


        // ... * base

        u_j_q_hat.S[2] = u_j_q_hat.S[3];

        // ... + uv[j+2]

        u_j_q_hat.S[2] = uv[j + 2];

        if ((vv[1] * q_hat) <= u_j_q_hat.L[1])

            break;

    }

    */

    // Problem code ends


    

    with this code:


    

    // New code starts

    if (vv[1] * q_hat > (((((uv[j] << T_BIT) + uv[j + 1]) - vv[0] * q_hat) << T_BIT) + uv[j + 2]))

    {

        LT q_test = (static_cast < T>(~0));

        if (q_hat != q_test && q_hat != 0)

            q_hat--;

    }

    // New code ends


    

    Hope this helps someone...


    Serge

    Reply

  • Min and max

    Posted by Legacy on 03/11/2002 12:00am

    Originally posted by: Per Nilsson 

    Nice article. Useful and clear.


    I added Min and Max static methods that returns lowest

    and highest possible values:

      static CLongInt Max()

      {


        CLongInt w;

        // Update this if the typedef T is changed

        for (int i = 1; i < T_LEN; i++) w.m_data[i] = USHRT_MAX;

        w.m_data[0] = USHRT_MAX/2;

        return w;

      }


      static CLongInt Min()

      {

        return ~Max();

      }


    

    So, elsewhere in my code I can present the valid

    range like:

      CLongInt<256> l;

      CString s;

      s.Format("Valid range [%s,%s]", 

      l.Min().ToString(),

      l.Max().ToString());

    Reply

  • Loading, Please Wait ...

Leave a Comment
  • Your email address will not be published. All fields are required.

Go Deeper

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds