[C/C++] 프로젝트 오일러 #16 : 2의 1000승의 모든 자릿수 합 구하기(BigInteger)

사실 이번 프로그램은 Big integer를 사용할 줄 아느냐 아니냐에 따라서 달라진다고 봅니다.

많은 언어가 기본으로 Big Integer를 지원하기 때문에, 언어에 따라서 구현 난이도도 차이가 많을겁니다.

 

문제에서 요구하는 것은 2의 1000제곱을 한 후, 모든 자리의 수를 합해서 결과를 내달라는 것입니다.

 

예를 들어서 python을 이용하면, 가볍게 이 문제를 해결할 수 있습니다.

 

>>> 2**1000

10715086071862673209484250490600018105614048117055336074437503883703510

51124936122493198378815695858127594672917553146825187145285692314043598

45775746985748039345677748242309854210746050623711418779541821530464749

83581941267398767559165543946077062914571196477686542167660429831652624

386837205668069376L

 

파이썬, 자바, C# 등에서는 BigInteger 자료형을 제공하고, 파이썬에서는 별도의 import 없이 정수형 자료가 자동으로 BigInteger 자료형으로 변환되므로 손쉽게 원하는 답을 얻을 수 있습니다.

 

# 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)

 

C/C++을 이용하기 위해서는 별도의 Big Integer 라이브러리를 이용하시거나 직접 해당 라이브러리와 비슷한 것을 작성하셔야 합니다.

 

제 경우에는 오래전부터 작성했던 Big Integer 라이브러리가 있었는데, 그동안 다른 일에 밀려서 손을 놓았던터라, 이번에 프로그램을 좀 작성했습니다.

 

이번 프로그램은 어떤 Big Integer 프로그램을 이용하든 별반 다를 것 없을거라 생각합니다.

 

power of 2

 

제가 작성한 프로그램 코드는 다음과 같습니다.

//------------------------------------------------
//    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;
}

 

2의 1000승을 매번 2를 1000번 곱하시는 분들도 계시던데, 1000비트만큼 쉬프트 연산을 하는 것이 더 유리합니다.  물론 Big Integer 라이브러리가 그것을 지원하지 않는다면, 어쩔 수 없겠지만요.

 

ConvertToArray 함수는 Big Integer 수를 배열로, 지정된 진법(radix 기본값이 여기서는 10)으로 변환해서 저장합니다.  보통은 문자열로 만들지만, 여기서는 계산에 더 편리한 방법을 택했습니다.

 

//-------------------------------------------------------------------
//  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)
{
}