[C/C++] Project Euler #16 Power Digit Sum(BigInteger)

The program essentially revolves around whether you can use a Big Integer implementation or not.

Many programming languages natively support Big Integer types, which greatly influences the implementation difficulty depending on the language.

The task is straightforward: compute \(2^{1000}\), and then sum all the digits of the resulting number.

For instance, if you use Python, this problem can be solved quite effortlessly.

 

>>> 2**1000
10715086071862673209484250490600018105614048117055336074437503883703510
51124936122493198378815695858127594672917553146825187145285692314043598
45775746985748039345677748242309854210746050623711418779541821530464749
83581941267398767559165543946077062914571196477686542167660429831652624
386837205668069376

 

In languages like Python, Java, or C#, BigInteger is readily available, and in Python, integers automatically convert to arbitrary-precision integers without needing any special imports, making it easy to compute the desired result.

For C/C++, however, you would need to rely on a third-party Big Integer library or write one yourself.

I had an old Big Integer library that I wrote a long time ago, but I hadn’t worked on it for years. This challenge inspired me to dust it off and implement this functionality.

Regardless of which Big Integer implementation you use, the logic of the program should remain largely the same.

Here’s an example of how you can solve this problem in Python:

# Calculate 2^1000
result = 2**1000

# Sum the digits of the result
digit_sum = sum(int(digit) for digit in str(result))

print(digit_sum)

 

This implementation efficiently computes the solution using Python’s built-in capabilities.

 

power of 2

 

Here’s a source code that I wrote to solve this problem in C++:

//------------------------------------------------
//    Project Euler #16 - Power Digit Sum
//        - by Aubrey Choi
//        - created at 2015-01-13
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"
#include "NxBigInt.h"

void solve1()
{
    NxBigInt c = 1;

    c <<= 1000;

    uint8_t buf[1024];
    int k = c.ConvertToArray(buf, 1024);
    int sum = 0;
    for( int i = 0 ; i < k ; i++ )
    {
        sum += buf[i];
    }
    printf("Ans = %d\n", sum);
}

int main()
{
    clock_t t;

    t = clock();
    solve1();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    return 0;
}

 

Some people calculate \(2^{1000}\) by multiplying 2 a thousand times, but using a 1000-bit shift operation is more efficient. Of course, if the Big Integer library you are using doesn’t support such operations, there isn’t much choice.

The ConvertToArray function converts a Big Integer into an array, storing it in a specified radix (with the default radix being 10 in this case). Typically, the number would be converted into a string, but in this case, an approach that is more convenient for calculations was chosen.

 

//-------------------------------------------------------------------
//  File:       NxBigInt.h
//  Author:     Aubrey Choi
//  Date:       2009.03.23.
//  Update:
//        - 2014.04.07.    Update to 32bit-64bit operation.
//-------------------------------------------------------------------
#ifndef _NXBIGINT_H_
#define    _NXBIGINT_H_
#include <iostream>
#include <stdint.h>

class NxBigInt;

///    @brief    Big integer class.
class NxBigInt
{
public:
    ///    @brief    Constructor from C integer;
    ///    @param    value                            [IN] C integer number
    NxBigInt(int value = 0);

    ///    @brief    Copy constructor.
    ///    @param    value                            [IN] big integer number
    NxBigInt(const NxBigInt &value);

    ///    @brief    Constructor from string.
    ///    @param    value                            [IN] number string
    NxBigInt(const char *value);

    ///    @brief    Constructor from string.
    ///    @param    pszNumberString                    [IN] number string
    NxBigInt(const wchar_t *value);

    ///    @brief    Destructor.
    ~NxBigInt();

    ///    @brief    Add big number and integer number.
    ///    @param    value                            [IN] second parameter to add
    ///    @return    Return the Result of big number and integer number.
    NxBigInt operator+(int value) const;

    ///    @brief    Add two big numbers.
    ///    @param    value                            [IN] second parameter to add
    ///    @return    Return the sum of two big numbers.
    NxBigInt operator+(const NxBigInt &value) const;

    ///    @brief    Add big number and integer number.
    ///    @param    first                            [IN] first parameter to add
    ///    @param    second                            [IN] second parameter to add
    ///    @return    Return the Result of big number and integer number.
    ///    @note    Integer number cannot exceed unsigned short range
    friend NxBigInt operator+(int first, const NxBigInt &second);

    ///    @brief    Minus sign.
    ///    @return    Return negative big integer.
    NxBigInt operator-() const;

    ///    @brief    Subtract big number and integer number.
    ///    @param    value                            [IN] second parameter to subtract
    ///    @return    Return the result big number.
    NxBigInt operator-(int value) const;

    ///    @brief    Subtract big number from big number.
    ///    @param    value                            [IN] second parameter to subtract
    ///    @return    Return the result big number.
    NxBigInt operator-(const NxBigInt &value) const;

    ///    @brief    Subtract big number from int number.
    ///    @param    first                            [IN] first parameter
    ///    @param    second                            [IN] second parameter to subtract
    ///    @return    Return the result big number.
    friend NxBigInt operator-(int first, const NxBigInt &second);

    ///    @brief    Multiply big number and integer number.
    ///    @param    value                            [IN] second parameter to multiply
    ///    @return    Return the result of multiplying big number and integer number.
    NxBigInt operator*(int value) const;

    ///    @brief    Multiply big number and integer number.
    ///    @param    value                            [IN] second parameter to multiply
    ///    @return    Return the result of multiplying big number and integer number.
    NxBigInt operator*(uint32_t value) const;

    ///    @brief    Multiply big number and integer number.
    ///    @param    value                            [IN] Second parameter to multiply
    ///    @return    Return the result of multiplying big number and integer number.
    NxBigInt operator*(const NxBigInt &value) const;

    //    @brief    Multiply big number and integer number.
    ///    @param    first                            [IN] first parameter
    ///    @param    second                            [IN] second parameter
    //    @return    Return the result of multiplying big number and integer number.
    friend NxBigInt operator*(int first, const NxBigInt &second);

    //    @brief    Divide big number and integer number
    //    @param    value                            [IN] second parameter to divide
    //    @return    Return the Result of big number and integer number.
    NxBigInt operator/(int value) const;

    //    @brief    Divide big number and integer number
    //    @param    value                            [IN] second parameter to divide
    //    @return    Return the Result of big number and integer number.
    NxBigInt operator/(const NxBigInt &value) const;

    //    @brief    Modular big number and integer number
    //    @param    value                            [IN] second parameter to divide
    //    @return    Return the result of modula big number.
    int operator%(int value) const;

    ///    @brief    Shift operator.
    ///    @param    value                            [IN] shift value
    ///    @return    Return big integer shifted by value.
    NxBigInt operator<<(int value) const;

    ///    @brief    Shift operator.
    ///    @param    value                            [IN] shift value
    ///    @return    Return big integer shifted by value.
    NxBigInt operator>>(int value) const;

    ///    @brief    Assign big number with integer number
    ///    @param    value                            [IN] Integer number to assign
    ///    @return    Return NxBigInt object.
    NxBigInt &operator=(int value);

    ///    @brief    Assign big number with integer number
    ///    @param    value                            [IN] Integer number to assign
    ///    @return    Return NxBigInt object.
    NxBigInt &operator=(int64_t value);

    ///    @brief    Assign big number with big integer.
    ///    @param    value                            [IN] value to assign
    ///    @return    Return NxBigInt result.
    NxBigInt &operator=(const NxBigInt &value);

    ///    @brief    Assign big number with string number
    ///    @brief    value                            [IN] String number to assign
    ///    @return    Return NxBigInt object.
    NxBigInt &operator=(const char *value);

    ///    @brief    Assign big number with string number
    ///    @brief    value                            [IN] String number to assign
    ///    @return    Return NxBigInt object.
    NxBigInt &operator=(const wchar_t *value);

    ///    @brief    Add big number with integer number
    ///    @param    value                            [IN] value to be added
    ///    @return    Return added result.
    NxBigInt &operator+=(int value);

    ///    @brief    Add big number with big integer.
    ///    @param    value                            [IN] value to be added
    ///    @return    Return added result.
    NxBigInt &operator+=(const NxBigInt &value);

    ///    @brief    Multiply big number with integer number.
    ///    @param    value                            [IN] value to be multiplied
    ///    @return    Return multiplied result.
    NxBigInt &operator*=(int value);

    ///    @brief    Multiply big number with big integer.
    ///    @param    value                            [IN] value to be multiplied
    ///    @return    Return multiplied result.
    NxBigInt &operator*=(const NxBigInt &value);

    ///    @brief    Divide big number with integer number.
    ///    @param    value                            [IN] value to be devided
    ///    @return    Return devided result.
    NxBigInt &operator/=(int value);

    ///    @brief    Divide big number with big integer.
    ///    @param    value                            [IN] value to be devided
    ///    @return    Return devided result.
    NxBigInt &operator/=(const NxBigInt &value);

    ///    @brief    Modula big number with big integer.
    ///    @param    value                            [IN] value to be devided
    ///    @return    Return modula result.
    NxBigInt &operator%=(int value);

    ///    @brief    Modula big number with big integer.
    ///    @param    value                            [IN] value to be devided
    ///    @return    Return modula result.
    NxBigInt &operator%=(const NxBigInt &value);

    ///    @brief    Shift big number with integer.
    ///    @param    value                            [IN] value to be shifted.
    ///    @return    Return result big integer.
    NxBigInt &operator<<=(int value);

    ///    @brief    Shift big number with integer.
    ///    @param    value                            [IN] value to be shifted.
    ///    @return    Return result big integer.
    NxBigInt &operator>>=(int value);

    ///    @brief    Type cast (bool).
    operator bool() const;

    ///    @brief    Compare ==
    ///    @param    value                            [IN] value to be compared
    ///    @return    Return true if equal, otherwise, return false.
    bool operator==(const NxBigInt &value);

    ///    @brief    Compare <
    ///    @param    value                            [IN] value to be compared
    ///    @return    Return true if equal, otherwise, return false.
    bool operator<(const NxBigInt &value);

    ///    @brief    Compare >
    ///    @param    value                            [IN] value to be compared
    ///    @return    Return true if equal, otherwise, return false.
    bool operator>(const NxBigInt &value);

    ///    @brief    Divide and store remains.
    ///    @param    divisor                            [IN] divider
    ///    @param    residue                            [OUT] remain number
    ///    @return    Return this object.
    ///    @note    Big integer object will be changed after this function is called.
    NxBigInt &DivideAndStoreRemain(int divisor, int *residue);

    ///    @brief    Streaming out big integer number.
    ///    @param    output                            [IN] output stream
    ///    @param    number                            [IN] big integer number
    ///    @return    Return output stream
    friend std::ostream &operator<<(std::ostream &output, const NxBigInt &number);

    ///    @brief    Convert from string.
    ///    @param    string                            [IN] number string
    ///    @param    radix                            [IN] radix
    void ConvertFromString(const char *string, int radix = 10);

    ///    @brief    Convert from string.
    ///    @param    string                            [IN] number string
    ///    @param    radix                            [IN] radix
    void ConvertFromString(const wchar_t *string, int radix = 10);

    ///    @brief    Convert to string.
    ///    @param    output                            [OUT] output buffer
    ///    @param    size                            [IN] output max buffer size
    ///    @param    radix                            [IN] radix
    int ConvertToString(char *output, int size, int radix = 10) const;

    ///    @brief    Convert to string.
    ///    @param    output                            [OUT] output buffer
    ///    @param    size                            [IN] output max buffer size
    ///    @param    radix                            [IN] radix
    int ConvertToString(wchar_t *output, int size, int radix = 10) const;

    ///    @brief    Convert to Array.
    ///    @param    output                            [OUT] output buffer
    ///    @param    size                            [IN] output max buffer size
    ///    @param    radix                            [IN] radix
    int ConvertToArray(uint8_t *output, int size, int radix = 10) const;

    ///    @brief    Convert to Array. (Little endian version)
    ///    @param    output                            [OUT] output buffer
    ///    @param    size                            [IN] output max buffer size
    ///    @param    radix                            [IN] radix
    int ConvertToArrayLE(uint8_t *output, int size, int radix = 10) const;

public:
    static const NxBigInt Zero;
    static const NxBigInt One;
    static const NxBigInt Undefined;

private:
    ///    @brief    Get the order of value by 2.
    ///    @param    value                            [IN] value
    ///    @return    Return the order of value by 2.
    int GetOrder2(int value);

    ///    @brief    Add value.
    ///    @param    value                            [IN] value
    void AddTo(int value);

    ///    @brief    Add value.
    ///    @param    value                            [IN] value
    void AddTo(const NxBigInt &value);

    ///    @brief    Subtract value.
    ///    @param    value                            [IN] value
    void SubtractTo(int value);

    ///    @brief    Subtract value.
    ///    @param    value                            [IN] value
    void SubtractTo(const NxBigInt &value);

    ///    @brief    Multiply value.
    ///    @param    value                            [IN] value
    void MultiplyTo(int value);

    ///    @brief    Multiply value.
    ///    @param    value                            [IN] value
    void MultiplyTo(uint32_t value);

    ///    @brief    Multiply value.
    ///    @param    value                            [IN] value
    void MultiplyTo(const NxBigInt &value);

    ///    @brief    Divide value.
    ///    @param    value                            [IN] value
    void DivideTo(int value);

    ///    @brief    Divide value.
    ///    @param    value                            [IN] value
    void DivideTo(const NxBigInt &value);

    ///    @brief    Modula value.
    ///    @param    value                            [IN] value
    void ModulaTo(int value);

    ///    @brief    Modula value.
    ///    @param    value                            [IN] value
    void ModulaTo(const NxBigInt &value);

    ///    @brief    Shift value.
    ///    @param    value                            [IN] value
    void ShiftToLeft(int value);

    ///    @brief    Shift value.
    ///    @param    value                            [IN] value
    void ShiftToRight(int value);

private:
    bool m_bNegative;                            //<    Negative of positive
    int m_nLen;                                    //<    Length of integers' array
    int m_nSize;                                //<    allocation size
    uint32_t *m_pnData;                            //<    integers' array
};

#endif

 

 

//-------------------------------------------------------------------
//  File:       NxBigInt.cpp
//  Author:     Aubrey Choi
//  Date:       2009.03.23.
//  Update:
//              
//-------------------------------------------------------------------
#include "NxBigInt.h"

#include <stdio.h>
#include <memory.h>

#include <assert.h>

#define    ALLOCSIZE    4

const NxBigInt NxBigInt::Zero = 0;
const NxBigInt NxBigInt::One = 1;
const NxBigInt NxBigInt::Undefined;

NxBigInt::NxBigInt(int value)
{
    if( value < 0 ) { m_bNegative = true; value = -value; } 
    else { m_bNegative = false; }
    m_nLen = 1;
    m_nSize = ALLOCSIZE;
    m_pnData = new uint32_t[m_nSize];
    m_pnData[0] = value;
    assert(m_nLen <= m_nSize);
}

NxBigInt::NxBigInt(const NxBigInt &value)
{
    m_bNegative = value.m_bNegative;
    m_nLen = value.m_nLen;
    m_nSize = value.m_nSize;
    m_pnData = new uint32_t[m_nSize];
    memcpy(m_pnData, value.m_pnData, m_nLen*sizeof(uint32_t));
    assert(m_nLen <= m_nSize);
}

NxBigInt::NxBigInt(const char *value)
{
    m_nLen = 1;
    m_nSize = ALLOCSIZE;
    m_pnData = new uint32_t[m_nSize];
    ConvertFromString(value);
    assert(m_nLen <= m_nSize);
}

NxBigInt::NxBigInt(const wchar_t *value)
{
    m_nLen = 1;
    m_nSize = ALLOCSIZE;
    m_pnData = new uint32_t[m_nSize];
    ConvertFromString(value);
    assert(m_nLen <= m_nSize);
}

NxBigInt::~NxBigInt()
{
    if( m_pnData != 0 )
    {
        delete[] m_pnData;
    }
}

NxBigInt NxBigInt::operator+(int value) const
{
    NxBigInt out(*this);
    out.AddTo(value);

    return out;
}

NxBigInt NxBigInt::operator+(const NxBigInt &value) const
{
    NxBigInt out(*this);
    out.AddTo(value);

    return out;
}

NxBigInt operator+(int first, const NxBigInt &second)
{
    return second + first;
}

NxBigInt NxBigInt::operator-() const
{
    NxBigInt out(*this);
    out.m_bNegative = !out.m_bNegative;

    return out;
}

NxBigInt NxBigInt::operator-(int value) const
{
    NxBigInt out(*this);
    out.SubtractTo(value);
    
    return out;
}

NxBigInt NxBigInt::operator-(const NxBigInt &value) const
{
    NxBigInt out(*this);
    out.SubtractTo(value);

    return out;
}

NxBigInt operator-(int first, const NxBigInt &second)
{
    NxBigInt out(first);
    out.SubtractTo(second);

    return out;
}

NxBigInt NxBigInt::operator*(int value) const
{
    NxBigInt out(*this);
    out.MultiplyTo(value);

    return out;
}

NxBigInt NxBigInt::operator*(uint32_t value) const
{
    NxBigInt out(*this);
    out.MultiplyTo(value);

    return out;
}

NxBigInt NxBigInt::operator*(const NxBigInt &value) const
{
    NxBigInt out(*this);
    out.MultiplyTo(value);

    return out;
}

NxBigInt operator*(int first, const NxBigInt &second)
{
    return second * first;
}

NxBigInt NxBigInt::operator/(int value) const
{
    NxBigInt out(*this);
    out.DivideTo(value);

    return out;
}

NxBigInt NxBigInt::operator/(const NxBigInt &value) const
{
    NxBigInt out(*this);
    out.DivideTo(value);

    return out;
}

int NxBigInt::operator%(int value) const
{
    if( value < 0 ) { value = -value; }
    uint64_t r = 0;
    for( int i = m_nLen-1 ; i >= 0 ; i-- )
    {
        r <<= 32;
        r |= m_pnData[i];
        r %= value;
    }

    return (int)r&0x7fffffff;
}

NxBigInt NxBigInt::operator<<(int value) const
{
    NxBigInt out = *this;
    out.ShiftToLeft(value);

    return out;
}

NxBigInt NxBigInt::operator>>(int value) const
{
    NxBigInt out = *this;
    out.ShiftToRight(value);

    return out;
}

NxBigInt &NxBigInt::operator=(int value)
{
    if( value < 0 ) { m_bNegative = true; value = -value; } else { m_bNegative = false; }
    m_nLen = 1;
    m_pnData[0] = value;
    return *this;
}

NxBigInt &NxBigInt::operator=(int64_t value)
{
    if( value < 0 ) { m_bNegative = true; value = -value; } else { m_bNegative = false; }
    m_pnData[0] = value & 0xffffffff;
    m_pnData[1] = value >> 32;
    m_nLen = m_pnData[1]?2:1;
    return *this;
}

NxBigInt &NxBigInt::operator=(const NxBigInt &value)
{
    if( m_nSize < value.m_nLen )
    {
        m_nSize = ((value.m_nLen+ALLOCSIZE-1)/ALLOCSIZE)*ALLOCSIZE;
        delete[] m_pnData;
        m_pnData = new uint32_t[m_nSize];
    }
    m_bNegative = value.m_bNegative;
    m_nLen = value.m_nLen;
    memcpy(m_pnData, value.m_pnData, m_nLen*sizeof(uint32_t));
    assert(m_nLen <= m_nSize);
    return *this;
}

NxBigInt &NxBigInt::operator=(const char *value)
{
    ConvertFromString(value);
    return *this;
}

NxBigInt &NxBigInt::operator=(const wchar_t *value)
{
    ConvertFromString(value);
    return *this;
}

NxBigInt &NxBigInt::operator+=(int value)
{
    AddTo(value);

    return *this;
}

NxBigInt &NxBigInt::operator+=(const NxBigInt &value)
{
    AddTo(value);

    return *this;
}

NxBigInt &NxBigInt::operator*=(int value)
{
    MultiplyTo(value);

    return *this;
}

NxBigInt &NxBigInt::operator*=(const NxBigInt &value)
{
    MultiplyTo(value);

    return *this;
}

NxBigInt &NxBigInt::operator/=(int value)
{
    DivideTo(value);

    return *this;
}

NxBigInt &NxBigInt::operator/=(const NxBigInt &value)
{
    DivideTo(value);

    return *this;
}

NxBigInt &NxBigInt::operator%=(int value)
{
    DivideTo(value);

    return *this;
}

NxBigInt &NxBigInt::operator<<=(int value)
{
    ShiftToLeft(value);

    return *this;
}

NxBigInt &NxBigInt::operator>>=(int value)
{
    ShiftToRight(value);

    return *this;
}

NxBigInt::operator bool() const
{
    return !(m_nLen <= 1 && m_pnData[0] == 0);
}

bool NxBigInt::operator==(const NxBigInt &value)
{
    if( m_nLen != value.m_nLen ) return false;
    if( m_bNegative != value.m_bNegative ) return false;
    return memcmp(m_pnData, value.m_pnData, m_nLen*sizeof(uint32_t)) == 0;
}

bool NxBigInt::operator<(const NxBigInt &value)
{
    if( m_bNegative && !value.m_bNegative ) return true;
    if( !m_bNegative && value.m_bNegative ) return false;
    if( m_nLen < value.m_nLen ) return !m_bNegative;
    else if( m_nLen > value.m_nLen ) return m_bNegative;
    for( int i = m_nLen-1 ; i >= 0 ; i-- )
    {
        if( m_pnData[i] < value.m_pnData[i] ) return !m_bNegative;
        else if( m_pnData[i] > value.m_pnData[i] ) return m_bNegative;
    }

    return false;
}

bool NxBigInt::operator>(const NxBigInt &value)
{
    if( m_bNegative && !value.m_bNegative ) return false;
    if( !m_bNegative && value.m_bNegative ) return true;
    if( m_nLen < value.m_nLen ) return m_bNegative;
    else if( m_nLen > value.m_nLen ) return !m_bNegative;
    for( int i = m_nLen-1 ; i >= 0 ; i-- )
    {
        if( m_pnData[i] < value.m_pnData[i] ) return m_bNegative;
        else if( m_pnData[i] > value.m_pnData[i] ) return !m_bNegative;
    }

    return false;
}

NxBigInt &NxBigInt::DivideAndStoreRemain(int divisor, int *residue)
{
    if( divisor <= 0 ) return *this;

    uint64_t n = 0, q;
    bool flag = true;
    int maxlen = m_nLen;
    for( int i = m_nLen-1 ; i >= 0 ; i-- )
    {
        n <<= 32;
        n |= m_pnData[i];
        q = n/divisor;
        m_pnData[i] = q;
        n %= divisor;
        if( flag && q == 0 ) maxlen = i; else flag = false;
    }

    *residue = n;
    m_nLen = maxlen >= 1?maxlen:1;

    return *this;
}

std::ostream &operator <<(std::ostream &output, const NxBigInt &number)
{
    char buf[2048];

    number.ConvertToString(buf, 2048);
    
    output << buf;

    return output;
}

void NxBigInt::ConvertFromString(const char *string, int radix)
{
    m_pnData[0] = 0;
    m_nLen = 1;
    while( *string )
    {
        int c = *string++ - '0';
        MultiplyTo(radix);
        AddTo(c);
    }
}

void NxBigInt::ConvertFromString(const wchar_t *string, int radix)
{
    m_pnData[0] = 0;
    m_nLen = 1;
    while( *string )
    {
        int c = *string++ - '0';
        MultiplyTo(radix);
        AddTo(c);
    }
}

int NxBigInt::ConvertToString(char *output, int size, int radix) const
{
    NxBigInt t = *this;

    if( t.m_nLen == 1 && t.m_pnData[0] == 0 )
    {
        output[0] = '0';
        output[1] = 0;
        return 1;
    }

    int k = 0;
    while( t && k < size )
    {
        int c;
        t.DivideAndStoreRemain(radix, &c);
        *(output+k++) = c+'0';
    }

    for( int i = 0 ; i < k/2 ; i++ )
    {
        int c = *(output+i);
        *(output+i) = *(output+k-i-1);
        *(output+k-i-1) = c;
    }
    if( k < size ) *(output+k) = 0;
    return k;
}

int NxBigInt::ConvertToString(wchar_t *output, int size, int radix) const
{
    NxBigInt t = *this;

    if( t.m_nLen == 1 && t.m_pnData[0] == 0 )
    {
        output[0] = '0';
        output[1] = 0;
        return 1;
    }

    int k = 0;
    while( t && k < size )
    {
        int c;
        t.DivideAndStoreRemain(radix, &c);
        *(output+k++) = c+'0';
    }

    for( int i = 0 ; i < k/2 ; i++ )
    {
        int c = *(output+i);
        *(output+i) = *(output+k-i-1);
        *(output+k-i-1) = c;
    }
    if( k < size ) *(output+k) = 0;
    return k;
}

int NxBigInt::ConvertToArray(uint8_t *output, int size, int radix) const
{
    NxBigInt t = *this;

    if( t.m_nLen == 1 && t.m_pnData[0] == 0 )
    {
        output[0] = 0;
        return 1;
    }

    int k = 0;
    while( t && k < size )
    {
        int c;
        t.DivideAndStoreRemain(radix, &c);
        *(output+k++) = c;
    }

    for( int i = 0 ; i < k/2 ; i++ )
    {
        int c = *(output+i);
        *(output+i) = *(output+k-i-1);
        *(output+k-i-1) = c;
    }
    return k;
}

int NxBigInt::ConvertToArrayLE(uint8_t *output, int size, int radix) const
{
    NxBigInt t = *this;

    if( t.m_nLen == 1 && t.m_pnData[0] == 0 )
    {
        output[0] = 0;
        return 1;
    }

    int k = 0;
    while( t && k < size )
    {
        int c;
        t.DivideAndStoreRemain(radix, &c);
        *(output+k++) = c;
    }

    return k;
}

int NxBigInt::GetOrder2(int value)
{
    return (int)(0x100000000/value);
}

void NxBigInt::AddTo(int value)
{
    int64_t out = value;
    for( int i = 0 ; i < m_nLen && out ; i++ )
    {
        out += m_pnData[i];
        m_pnData[i] = out;
        out >>= 32;
    }
    if( out == 0 ) return;
    if( m_nLen == m_nSize )
    {
        m_nSize = m_nSize+ALLOCSIZE;
        uint32_t *newData = new uint32_t[m_nSize];
        memcpy(newData, m_pnData, m_nLen*sizeof(uint32_t));
        delete[] m_pnData;
        m_pnData = newData;
    }
    m_pnData[m_nLen++] = out;
    assert(m_nLen <= m_nSize);
}

void NxBigInt::AddTo(const NxBigInt &value)
{
    if( m_nSize < value.m_nLen+1 )
    {
        m_nSize = ((value.m_nLen+ALLOCSIZE)/ALLOCSIZE) * ALLOCSIZE;
        uint32_t *newData = new uint32_t[m_nSize];
        memcpy(newData, m_pnData, m_nLen*sizeof(uint32_t));
        delete[] m_pnData;
        m_pnData = newData;
    }

    uint64_t c = 0;
    int i = 0;
    while( i < m_nLen && i < value.m_nLen )
    {
        c += m_pnData[i];
        c += value.m_pnData[i];
        m_pnData[i++] = c;
        c >>= 32;
    }
    while( i < m_nLen )
    {
        c += m_pnData[i];
        m_pnData[i++] = c;
        c >>= 32;
    }
    while( i < value.m_nLen )
    {
        c += value.m_pnData[i];
        m_pnData[i++] = c;
        c >>= 32;
    }

    m_nLen = i;
    if( c ) m_pnData[m_nLen++] = c;
    assert( m_nLen <= m_nSize );
}

void NxBigInt::SubtractTo(int value)
{
}

void NxBigInt::SubtractTo(const NxBigInt &value)
{
}

void NxBigInt::MultiplyTo(int value)
{
    if( value < 0 ) { m_bNegative = !m_bNegative; value = -value; }
    uint64_t r = 0;
    for( int i = 0 ; i < m_nLen ; i++ )
    {
        r = (uint64_t)m_pnData[i]*value + r;
        m_pnData[i] = r;
        r >>= 32;
    }
    if( r == 0 ) return;
    if( m_nLen == m_nSize )
    {
        m_nSize += ALLOCSIZE;
        uint32_t *newData = new uint32_t[m_nSize];
        memcpy(newData, m_pnData, m_nLen*sizeof(uint32_t));
        delete[] m_pnData;
        m_pnData = newData;
    }
    m_pnData[m_nLen++] = r;
    assert(m_nLen <= m_nSize);
}

void NxBigInt::MultiplyTo(uint32_t value)
{
    uint64_t r = 0;
    for( int i = 0 ; i < m_nLen ; i++ )
    {
        r = (uint64_t)m_pnData[i]*value + r;
        m_pnData[i] = r;
        r >>= 32;
    }
    if( r == 0 ) return;
    if( m_nLen == m_nSize )
    {
        m_nSize += ALLOCSIZE;
        uint32_t *newData = new uint32_t[m_nSize];
        memcpy(newData, m_pnData, m_nLen*sizeof(uint32_t));
        delete[] m_pnData;
        m_pnData = newData;
    }
    m_pnData[m_nLen++] = r;
    assert(m_nLen <= m_nSize);
}

void NxBigInt::MultiplyTo(const NxBigInt &value)
{
    if( value.m_bNegative ) m_bNegative = !m_bNegative; 
    NxBigInt src = *this;
    m_nLen = 0;
    for( int i = 0 ; i < value.m_nLen ; i++ )
    {
        *this <<= 32;
        *this += src*value.m_pnData[i];
    }
}

void NxBigInt::DivideTo(int value)
{
    if( value < 0 ) { m_bNegative = !m_bNegative; value = -value; }
    uint64_t r = 0;
    for( int i = m_nLen-1 ; i >= 0 ; i-- )
    {
        r <<= 32;
        r |= m_pnData[i];
        m_pnData[i] = r/value;
        r %= value;
    }
    while( m_nLen > 1 && m_pnData[m_nLen-1] == 0 ) m_nLen--;
}

void NxBigInt::DivideTo(const NxBigInt &value)
{
}

void NxBigInt::ModulaTo(int value)
{
    if( value < 0 ) { m_bNegative = !m_bNegative; value = -value; }
    uint64_t r = 0;
    for( int i = m_nLen-1 ; i >= 0 ; i-- )
    {
        r <<= 32;
        r %= value;
    }
    m_pnData[0] = r;
    m_nLen = 1;
}

void NxBigInt::ModulaTo(const NxBigInt &value)
{
}

void NxBigInt::ShiftToLeft(int value)
{
    int c = m_nLen*32;
    for( int i = 0 ; i < 32 ; i++ )
    {
        if( m_pnData[m_nLen-1] & (1<<(31-i)) ) { c-=i; break; }
    }

    int t = c + value;
    if( t > m_nSize*32 )
    {
        m_nSize = (t+31)/(32*ALLOCSIZE)*ALLOCSIZE;
        uint32_t *newData = new uint32_t[m_nSize];
        memcpy(newData, m_pnData, m_nLen*sizeof(uint32_t));
        delete[] m_pnData;
        m_pnData = newData;
    }

    int n = value/32;
    int r = value%32;
    int64_t u = m_pnData[m_nLen-1];
    if( u>>(32-r) ) m_pnData[n+m_nLen] = u>>(32-r);
    u <<= r;
    for( int i = m_nLen-2 ; i >= 0 ; i-- )
    {
        u |= m_pnData[i];
        m_pnData[n+i+1] = u>>(32-r);
        u <<= r;
    }
    m_nLen = (t+31)/32;
    m_pnData[n] = u;
    while( n > 0 ) m_pnData[--n] = 0;
    assert(m_nLen <= m_nSize);
}

void NxBigInt::ShiftToRight(int value)
{
}