bigint

2021年6月19日

このオブジェクトは任意精度の符号なし整数を表します。とても簡単です。そのインターフェースは普通のint型のようなものです。どれだけのメモリを使うべきか、あるいは何か変わったことを言う必要はありません。それだけです:) 

#include <dlib / bigint.h>

実装:

bigint_kernel_1

 この実装は符号なしshort型の配列を使って行われます。それはまた参照カウントです。詳細については上記のリンクを参照してください。また、kernel_2はほとんどすべての場合において高速であるはずなので、実際にはそのバージョンのbigintオブジェクトを使用する必要があります。

kernel_1abigint_kernel_1のtypedefです。
kernel_1a_cその前提条件をチェックするkernel_1aのtypedefです。

bigint_kernel_2

 この実装は基本的にkernel_1と同じですが、高速フーリエ変換を使用して乗算をはるかに高速に実行します。

kernel_2abigint_kernel_2のtypedefです。
kernel_2a_cその前提条件をチェックするkernel_2aのtypedefです。
// Copyright (C) 2003  Davis E. King (davis@dlib.net)
// License: Boost Software License   See LICENSE.txt for the full license.
#undef DLIB_BIGINT_KERNEl_ABSTRACT_
#ifdef DLIB_BIGINT_KERNEl_ABSTRACT_

#include <iosfwd>
#include "../algs.h"
#include "../serialize.h"
#include "../uintn.h"

namespace dlib
{

    class bigint 
    {
        /*!
            INITIAL VALUE
                *this == 0

            WHAT THIS OBJECT REPRESENTS
                This object represents an arbitrary precision unsigned integer

                the following operators are supported:
                operator +
                operator +=
                operator -
                operator -=
                operator *
                operator *=
                operator /
                operator /=
                operator %
                operator %=
                operator ==
                operator <
                operator =
                operator << (for writing to ostreams)
                operator >> (for reading from istreams)
                operator++       // pre increment
                operator++(int)  // post increment
                operator--       // pre decrement
                operator--(int)  // post decrement


                the other comparason operators(>, !=, <=, and >=) are 
                available and come from the templates in dlib::relational_operators

            THREAD SAFETY
                bigint may be reference counted so it is very unthread safe.
                use with care in a multithreaded program

        !*/

    public:

        bigint (
        );
        /*!
            ensures
                - #*this is properly initialized
            throws
                - std::bad_alloc
                    if this is thrown the bigint will be unusable but 
                    will not leak memory
        !*/

        bigint (
            uint32 value
        );
        /*!
            requires
                - value <= (2^32)-1
            ensures
                - #*this is properly initialized
                - #*this == value
            throws
                - std::bad_alloc
                    if this is thrown the bigint will be unusable but 
                    will not leak memory
        !*/

        bigint (
            const bigint& item
        );
        /*!
            ensures
                - #*this is properly initialized 
                - #*this == value
            throws
                - std::bad_alloc
                    if this is thrown the bigint will be unusable but 
                    will not leak memory
        !*/

        virtual ~bigint (
        );
        /*!
            ensures
                - all resources associated with #*this have been released
        !*/

        const bigint operator+ (
            const bigint& rhs
        ) const;
        /*!
            ensures
                - returns the result of adding rhs to *this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator+= (
            const bigint& rhs
        );
        /*!
            ensures
                - #*this == *this + rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect                                        
        !*/

        const bigint operator- (
            const bigint& rhs
        ) const;
        /*!
            requires
                - *this >= rhs
            ensures
                - returns the result of subtracting rhs from *this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator-= (
            const bigint& rhs
        );
        /*!
            requires
                - *this >= rhs            
            ensures
                - #*this == *this - rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        const bigint operator* (
            const bigint& rhs
        ) const;
        /*!
            ensures
                - returns the result of multiplying *this and rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator*= (
            const bigint& rhs
        );
        /*!
            ensures
                - #*this == *this * rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        const bigint operator/ (
            const bigint& rhs
        ) const;
        /*!
            requires
                - rhs != 0
            ensures
                - returns the result of dividing *this by rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator/= (
            const bigint& rhs
        );
        /*!
            requires
                - rhs != 0
            ensures
                - #*this == *this / rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        const bigint operator% (
            const bigint& rhs
        ) const;
        /*!
            requires
                - rhs != 0
            ensures
                - returns the result of *this mod rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator%= (
            const bigint& rhs
        );
        /*!
            requires
                - rhs != 0
            ensures
                - #*this == *this % rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bool operator < (
            const bigint& rhs
        ) const;
        /*!
            ensures
                - returns true if *this is less than rhs 
                - returns false otherwise
        !*/

        bool operator == (
            const bigint& rhs
        ) const;
        /*!
            ensures
                - returns true if *this and rhs represent the same number 
                - returns false otherwise
        !*/

        bigint& operator= (
            const bigint& rhs
        );
        /*!
            ensures
                - #*this == rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/


        friend std::ostream& operator<< (
            std::ostream& out,
            const bigint& rhs
        );
        /*!
            ensures
                - the number in *this has been written to #out as a base ten number
            throws
                - std::bad_alloc
                    if this function throws then it has no effect (nothing
                    is written to out)
        !*/

        friend std::istream& operator>> (
            std::istream& in,
            bigint& rhs
        );
        /*!
            ensures
                - reads a number from in and puts it into #*this 
                - if (there is no positive base ten number on the input stream ) then 
                    - #in.fail() == true
            throws
                - std::bad_alloc
                    if this function throws the value in rhs is undefined and some
                    characters may have been read from in.  rhs is still usable though,
                    its value is just unknown.
        !*/


        bigint& operator++ (
        );
        /*!
            ensures
                - #*this == *this + 1 
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        const bigint operator++ (
            int
        );
        /*!
            ensures
                - #*this == *this + 1
                - returns *this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator-- (
        );
        /*! 
            requires
                - *this != 0
            ensures
                - #*this == *this - 1
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        const bigint operator-- (
            int
        );
        /*!
            requires
                - *this != 0
            ensures
                - #*this == *this - 1
                - returns *this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        void swap (
            bigint& item
        );
        /*!
            ensures
                - swaps *this and item
        !*/ 


        // ------------------------------------------------------------------
        // ----    The following functions are identical to the above   -----
        // ----  but take uint16 as one of their arguments. They  ---
        // ----  exist only to allow for a more efficient implementation  ---
        // ------------------------------------------------------------------


        friend const bigint operator+ (
            uint16 lhs,
            const bigint& rhs
        );
        /*!
            requires
                - lhs <= 65535
            ensures
                - returns the result of adding rhs to lhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        friend const bigint operator+ (
            const bigint& lhs,
            uint16 rhs
        );
        /*!
            requires
                - rhs <= 65535
            ensures
                - returns the result of adding rhs to lhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator+= (
            uint16 rhs
        );
        /*!
            requires
                - rhs <= 65535
            ensures
                - #*this == *this + rhs                
                - returns #this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        friend const bigint operator- (
            uint16 lhs,
            const bigint& rhs
        );
        /*!
            requires
                - lhs >= rhs 
                - lhs <= 65535
            ensures
                - returns the result of subtracting rhs from lhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        friend const bigint operator- (
            const bigint& lhs,
            uint16 rhs
        );
        /*!
            requires
                - lhs >= rhs 
                - rhs <= 65535
            ensures
                - returns the result of subtracting rhs from lhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator-= (
            uint16 rhs
        );
        /*!
            requires
                - *this >= rhs 
                - rhs <= 65535
            ensures
                - #*this == *this - rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        friend const bigint operator* (
            uint16 lhs,
            const bigint& rhs
        );
        /*!
            requires
                - lhs <= 65535
            ensures
                - returns the result of multiplying lhs and rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        friend const bigint operator* (
            const bigint& lhs,
            uint16 rhs
        );
        /*!
            requires
                - rhs <= 65535
            ensures
                - returns the result of multiplying lhs and rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator*= (
            uint16 rhs
        );
        /*!
            requires
                - rhs <= 65535
            ensures
                - #*this == *this * rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        friend const bigint operator/ (
            uint16 lhs,
            const bigint& rhs
        );
        /*!
            requires
                - rhs != 0 
                - lhs <= 65535
            ensures
                - returns the result of dividing lhs by rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        friend const bigint operator/ (
            const bigint& lhs,
            uint16 rhs
        );
        /*!
            requires
                - rhs != 0 
                - rhs <= 65535
            ensures
                - returns the result of dividing lhs by rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator/= (
            uint16 rhs
        );
        /*!
            requires
                - rhs != 0 
                - rhs <= 65535
            ensures
                - #*this == *this / rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        friend const bigint operator% (
            uint16 lhs,
            const bigint& rhs
        );
        /*!
            requires
                - rhs != 0 
                - lhs <= 65535
            ensures
                - returns the result of lhs mod rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        friend const bigint operator% (
            const bigint& lhs,
            uint16 rhs
        );
        /*!
            requires
                - rhs != 0 
                - rhs <= 65535
            ensures
                - returns the result of lhs mod rhs
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

        bigint& operator%= (
            uint16 rhs
        );
        /*!
            requires
                - rhs != 0 
                - rhs <= 65535
            ensures
                - #*this == *this % rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/


        friend bool operator < (
            uint16 lhs,
            const bigint& rhs
        );
        /*!
            requires
                - lhs <= 65535
            ensures
                - returns true if lhs is less than rhs 
                - returns false otherwise
        !*/

        friend bool operator < (
            const bigint& lhs,
            uint16 rhs
        );
        /*!
            requires
                - rhs <= 65535
            ensures
                - returns true if lhs is less than rhs 
                - returns false otherwise
        !*/

        friend bool operator == (
            const bigint& lhs,
            uint16 rhs
        );
        /*!
            requires
                - rhs <= 65535
            ensures
                - returns true if lhs and rhs represent the same number 
                - returns false otherwise
        !*/

        friend bool operator == (
            uint16 lhs,
            const bigint& rhs
        );
        /*!
            requires
                - lhs <= 65535
            ensures
                - returns true if lhs and rhs represent the same number 
                - returns false otherwise
        !*/

        bigint& operator= (
            uint16 rhs
        );
        /*!
            requires
                - rhs <= 65535
            ensures
                - #*this == rhs
                - returns #*this
            throws
                - std::bad_alloc
                    if this function throws then it has no effect
        !*/

    };   
   
    inline void swap (
        bigint& a, 
        bigint& b 
    ) { a.swap(b); }   
    /*!
        provides a global swap function
    !*/

    void serialize (
        const bigint& item, 
        std::istream& in
    );   
    /*!
        provides serialization support 
    !*/

    void deserialize (
        bigint& item, 
        std::istream& in
    );   
    /*!
        provides deserialization support 
    !*/

    inline bool operator>  (const bigint& a, const bigint& b) { return b < a; } 
    inline bool operator!= (const bigint& a, const bigint& b) { return !(a == b); }
    inline bool operator<= (const bigint& a, const bigint& b) { return !(b < a); }
    inline bool operator>= (const bigint& a, const bigint& b) { return !(a < b); }
}

#endif // DLIB_BIGINT_KERNEl_ABSTRACT_


// Copyright (C) 2003  Davis E. King (davis@dlib.net)
// License: Boost Software License   See LICENSE.txt for the full license.
#ifndef DLIB_BIGINT_KERNEl_1_
#define DLIB_BIGINT_KERNEl_1_

#include "bigint_kernel_abstract.h"
#include "../algs.h"
#include "../serialize.h"
#include "../uintn.h"
#include <iosfwd>

namespace dlib
{
    

    class bigint_kernel_1 
    {
        /*!
            INITIAL VALUE
                slack               == 25
                data->number[0]     == 0 
                data->size          == slack 
                data->references    == 1 
                data->digits_used   == 1
                

            CONVENTION
                slack  == the number of extra digits placed into the number when it is 
                    created.  the slack value should never be less than 1

                data->number == pointer to an array of data->size uint16s.
                    data represents a string of base 65535 numbers with data[0] being
                    the least significant bit and data[data->digits_used-1] being the most 
                    significant


                NOTE: In the comments I will consider a word to be a 16 bit value


                data->digits_used == the number of significant digits in the number.
                    data->digits_used tells us the number of used elements in the 
                    data->number array so everything beyond data->number[data->digits_used-1] 
                    is undefined

                data->references == the number of bigint_kernel_1 objects which refer
                    to this data_record



        !*/


        struct data_record
        {


            explicit data_record(
                uint32 size_
            ) : 
                size(size_),
                number(new uint16[size_]),
                references(1),
                digits_used(1)
            {*number = 0;}
            /*!
                ensures
                    - initializes *this to represent zero
            !*/

            data_record(
                const data_record& item,
                uint32 additional_size
            ) :
                size(item.digits_used + additional_size),
                number(new uint16[size]),
                references(1),
                digits_used(item.digits_used)
            {
                uint16* source = item.number;
                uint16* dest = number;
                uint16* end = source + digits_used;
                while (source != end)
                {
                    *dest = *source;
                    ++dest;
                    ++source;
                }
            }
            /*!
                ensures
                    - *this is a copy of item except with 
                      size == item.digits_used + additional_size
            !*/

            ~data_record(
            )
            {
                delete [] number;
            }


            const uint32 size;
            uint16* number;
            uint32 references;            
            uint32 digits_used;

        private:
            // no copy constructor
            data_record ( data_record&);
        };



        // note that the second parameter is just there 
        // to resolve the ambiguity between this constructor and 
        // bigint_kernel_1(uint32)
        explicit bigint_kernel_1 (
            data_record* data_, int
        ): slack(25),data(data_) {}
        /*!
            ensures
                - *this is initialized with data_ as its data member
        !*/


    public:

        bigint_kernel_1 (
        );

        bigint_kernel_1 (
            uint32 value
        );

        bigint_kernel_1 (
            const bigint_kernel_1& item
        );

        virtual ~bigint_kernel_1 (
        );

        const bigint_kernel_1 operator+ (
            const bigint_kernel_1& rhs
        ) const;

        bigint_kernel_1& operator+= (
            const bigint_kernel_1& rhs
        );

        const bigint_kernel_1 operator- (
            const bigint_kernel_1& rhs
        ) const;

        bigint_kernel_1& operator-= (
            const bigint_kernel_1& rhs
        );

        const bigint_kernel_1 operator* (
            const bigint_kernel_1& rhs
        ) const;

        bigint_kernel_1& operator*= (
            const bigint_kernel_1& rhs
        );

        const bigint_kernel_1 operator/ (
            const bigint_kernel_1& rhs
        ) const;

        bigint_kernel_1& operator/= (
            const bigint_kernel_1& rhs
        );

        const bigint_kernel_1 operator% (
            const bigint_kernel_1& rhs
        ) const;

        bigint_kernel_1& operator%= (
            const bigint_kernel_1& rhs
        );

        bool operator < (
            const bigint_kernel_1& rhs
        ) const;

        bool operator == (
            const bigint_kernel_1& rhs
        ) const;

        bigint_kernel_1& operator= (
            const bigint_kernel_1& rhs
        );

        friend std::ostream& operator<< (
            std::ostream& out,
            const bigint_kernel_1& rhs
        );

        friend std::istream& operator>> (
            std::istream& in,
            bigint_kernel_1& rhs
        );

        bigint_kernel_1& operator++ (
        );

        const bigint_kernel_1 operator++ (
            int
        );

        bigint_kernel_1& operator-- (
        );

        const bigint_kernel_1 operator-- (
            int
        );

        friend const bigint_kernel_1 operator+ (
            uint16 lhs,
            const bigint_kernel_1& rhs
        );

        friend const bigint_kernel_1 operator+ (
            const bigint_kernel_1& lhs,
            uint16 rhs
        );

        bigint_kernel_1& operator+= (
            uint16 rhs
        );

        friend const bigint_kernel_1 operator- (
            uint16 lhs,
            const bigint_kernel_1& rhs
        );

        friend const bigint_kernel_1 operator- (
            const bigint_kernel_1& lhs,
            uint16 rhs
        );

        bigint_kernel_1& operator-= (
            uint16 rhs
        );

        friend const bigint_kernel_1 operator* (
            uint16 lhs,
            const bigint_kernel_1& rhs
        );

        friend const bigint_kernel_1 operator* (
            const bigint_kernel_1& lhs,
            uint16 rhs
        );

        bigint_kernel_1& operator*= (
            uint16 rhs
        );

        friend const bigint_kernel_1 operator/ (
            uint16 lhs,
            const bigint_kernel_1& rhs
        );

        friend const bigint_kernel_1 operator/ (
            const bigint_kernel_1& lhs,
            uint16 rhs
        );

        bigint_kernel_1& operator/= (
            uint16 rhs
        );

        friend const bigint_kernel_1 operator% (
            uint16 lhs,
            const bigint_kernel_1& rhs
        );

        friend const bigint_kernel_1 operator% (
            const bigint_kernel_1& lhs,
            uint16 rhs
        );

        bigint_kernel_1& operator%= (
            uint16 rhs
        );

        friend bool operator < (
            uint16 lhs,
            const bigint_kernel_1& rhs
        );

        friend bool operator < (
            const bigint_kernel_1& lhs,
            uint16 rhs
        );

        friend bool operator == (
            const bigint_kernel_1& lhs,
            uint16 rhs
        );

        friend bool operator == (
            uint16 lhs,
            const bigint_kernel_1& rhs
        );

        bigint_kernel_1& operator= (
            uint16 rhs
        );


        void swap (
            bigint_kernel_1& item
        ) { data_record* temp = data; data = item.data; item.data = temp; }


    private:

        void long_add (
            const data_record* lhs,
            const data_record* rhs,
            data_record* result
        ) const;
        /*!
            requires
                - result->size >= max(lhs->digits_used,rhs->digits_used) + 1
            ensures
                - result == lhs + rhs
        !*/

        void long_sub (
            const data_record* lhs,
            const data_record* rhs,
            data_record* result
        ) const;
        /*!
            requires
                - lhs >= rhs 
                - result->size >= lhs->digits_used
            ensures
                - result == lhs - rhs
        !*/

        void long_div (
            const data_record* lhs,
            const data_record* rhs,
            data_record* result,
            data_record* remainder
        ) const;
        /*!
            requires 
                - rhs != 0 
                - result->size >= lhs->digits_used 
                - remainder->size >= lhs->digits_used 
                - each parameter is unique (i.e. lhs != result, lhs != remainder, etc.)
            ensures
                - result == lhs / rhs
                - remainder == lhs % rhs
        !*/

        void long_mul (
            const data_record* lhs,
            const data_record* rhs,
            data_record* result
        ) const;
        /*!
            requires
                - result->size >= lhs->digits_used + rhs->digits_used 
                - result != lhs 
                - result != rhs
            ensures
                - result == lhs * rhs
        !*/

        void short_add (
            const data_record* data,
            uint16 value,
            data_record* result            
        ) const;
        /*!
            requires
                - result->size >= data->size + 1
            ensures
                - result == data + value
        !*/

        void short_sub (
            const data_record* data,
            uint16 value,
            data_record* result
        ) const;
        /*!
            requires
                - data >= value 
                - result->size >= data->digits_used
            ensures
                - result == data - value
        !*/

        void short_mul (
            const data_record* data,
            uint16 value,
            data_record* result            
        ) const;
        /*!
            requires
                - result->size >= data->digits_used + 1
            ensures
                - result == data * value
        !*/

        void short_div (
            const data_record* data,            
            uint16 value,
            data_record* result,
            uint16& remainder
        ) const;
        /*!
            requires
                - value != 0 
                - result->size >= data->digits_used
            ensures
                - result = data*value 
                - remainder = data%value
        !*/

        void shift_left (
            const data_record* data,
            data_record* result,
            uint32 shift_amount
        ) const;
        /*!
            requires
                - result->size >= data->digits_used + shift_amount/8 + 1
            ensures
                - result == data << shift_amount
        !*/

        void shift_right (
            const data_record* data,
            data_record* result
        ) const;
        /*!
            requires
                - result->size >= data->digits_used 
            ensures
                - result == data >> 1
        !*/

        bool is_less_than (
            const data_record* lhs,
            const data_record* rhs
        ) const;
        /*! 
            ensures
                - returns true if lhs < rhs 
                - returns false otherwise
        !*/ 

        bool is_equal_to (
            const data_record* lhs,
            const data_record* rhs
        ) const;
        /*!
            ensures
                - returns true if lhs == rhs 
                - returns false otherwise
        !*/

        void increment (
            const data_record* source,
            data_record* dest
        ) const;
        /*!
            requires
                - dest->size >= source->digits_used + 1
            ensures
                - dest = source + 1
        !*/

        void decrement (
            const data_record* source,
            data_record* dest
        ) const;
        /*!
            requires
                source != 0
            ensuers
                dest = source - 1
        !*/

        // member data
        const uint32 slack;
        data_record* data;     
        
        

    };

    inline void swap (
        bigint_kernel_1& a,
        bigint_kernel_1& b
    ) { a.swap(b); }

    inline void serialize (
        const bigint_kernel_1& item, 
        std::ostream& out
    )
    { 
        std::ios::fmtflags oldflags = out.flags();  
        out.flags(); 
        out << item << ' '; 
        out.flags(oldflags); 
        if (!out) throw serialization_error("Error serializing object of type bigint_kernel_c"); 
    }   

    inline void deserialize (
        bigint_kernel_1& item, 
        std::istream& in
    ) 
    { 
        std::ios::fmtflags oldflags = in.flags();  
        in.flags(); 
        in >> item; in.flags(oldflags); 
        if (in.get() != ' ')
        {
            item = 0;
            throw serialization_error("Error deserializing object of type bigint_kernel_c"); 
        }
    }   

    inline bool operator>  (const bigint_kernel_1& a, const bigint_kernel_1& b) { return b < a; } 
    inline bool operator!= (const bigint_kernel_1& a, const bigint_kernel_1& b) { return !(a == b); }
    inline bool operator<= (const bigint_kernel_1& a, const bigint_kernel_1& b) { return !(b < a); }
    inline bool operator>= (const bigint_kernel_1& a, const bigint_kernel_1& b) { return !(a < b); }
}

#ifdef NO_MAKEFILE
#include "bigint_kernel_1.cpp"
#endif

#endif // DLIB_BIGINT_KERNEl_1_
// Copyright (C) 2003  Davis E. King (davis@dlib.net)
// License: Boost Software License   See LICENSE.txt for the full license.
#ifndef DLIB_BIGINT_KERNEl_2_
#define DLIB_BIGINT_KERNEl_2_

#include "bigint_kernel_abstract.h"
#include "../algs.h"
#include "../serialize.h"
#include "../uintn.h"
#include <iosfwd>
#include <cmath>
#include <complex>
#include <vector>

namespace dlib
{
    
    class bigint_kernel_2 
    {
        /*!
            INITIAL VALUE
                slack               == 25
                data->number[0]     == 0 
                data->size          == slack 
                data->references    == 1 
                data->digits_used   == 1
                

            CONVENTION
                slack  == the number of extra digits placed into the number when it is 
                    created.  the slack value should never be less than 1

                data->number == pointer to an array of data->size uint16s.
                    data represents a string of base 65535 numbers with data[0] being
                    the least significant bit and data[data->digits_used-1] being the most 
                    significant


                NOTE: In the comments I will consider a word to be a 16 bit value


                data->digits_used == the number of significant digits in the number.
                    data->digits_used tells us the number of used elements in the 
                    data->number array so everything beyond data->number[data->digits_used-1] 
                    is undefined

                data->references == the number of bigint_kernel_2 objects which refer
                    to this data_record
        !*/


        struct data_record
        {


            explicit data_record(
                uint32 size_
            ) : 
                size(size_),
                number(new uint16[size_]),
                references(1),
                digits_used(1)
            {*number = 0;}
            /*!
                ensures
                    - initializes *this to represent zero
            !*/

            data_record(
                const data_record& item,
                uint32 additional_size
            ) :
                size(item.digits_used + additional_size),
                number(new uint16[size]),
                references(1),
                digits_used(item.digits_used)
            {
                uint16* source = item.number;
                uint16* dest = number;
                uint16* end = source + digits_used;
                while (source != end)
                {
                    *dest = *source;
                    ++dest;
                    ++source;
                }
            }
            /*!
                ensures
                    - *this is a copy of item except with 
                      size == item.digits_used + additional_size
            !*/

            ~data_record(
            )
            {
                delete [] number;
            }


            const uint32 size;
            uint16* number;
            uint32 references;            
            uint32 digits_used;

        private:
            // no copy constructor
            data_record ( data_record&);
        };


        // note that the second parameter is just there 
        // to resolve the ambiguity between this constructor and 
        // bigint_kernel_2(uint32)
        explicit bigint_kernel_2 (
            data_record* data_, int
        ): slack(25),data(data_) {}
        /*!
            ensures
                - *this is initialized with data_ as its data member
        !*/

    public:

        bigint_kernel_2 (
        );

        bigint_kernel_2 (
            uint32 value
        );

        bigint_kernel_2 (
            const bigint_kernel_2& item
        );

        virtual ~bigint_kernel_2 (
        );

        const bigint_kernel_2 operator+ (
            const bigint_kernel_2& rhs
        ) const;

        bigint_kernel_2& operator+= (
            const bigint_kernel_2& rhs
        );

        const bigint_kernel_2 operator- (
            const bigint_kernel_2& rhs
        ) const;

        bigint_kernel_2& operator-= (
            const bigint_kernel_2& rhs
        );

        const bigint_kernel_2 operator* (
            const bigint_kernel_2& rhs
        ) const;

        bigint_kernel_2& operator*= (
            const bigint_kernel_2& rhs
        );

        const bigint_kernel_2 operator/ (
            const bigint_kernel_2& rhs
        ) const;

        bigint_kernel_2& operator/= (
            const bigint_kernel_2& rhs
        );

        const bigint_kernel_2 operator% (
            const bigint_kernel_2& rhs
        ) const;

        bigint_kernel_2& operator%= (
            const bigint_kernel_2& rhs
        );

        bool operator < (
            const bigint_kernel_2& rhs
        ) const;

        bool operator == (
            const bigint_kernel_2& rhs
        ) const;

        bigint_kernel_2& operator= (
            const bigint_kernel_2& rhs
        );

        friend std::ostream& operator<< (
            std::ostream& out,
            const bigint_kernel_2& rhs
        );

        friend std::istream& operator>> (
            std::istream& in,
            bigint_kernel_2& rhs
        );

        bigint_kernel_2& operator++ (
        );

        const bigint_kernel_2 operator++ (
            int
        );

        bigint_kernel_2& operator-- (
        );

        const bigint_kernel_2 operator-- (
            int
        );

        friend const bigint_kernel_2 operator+ (
            uint16 lhs,
            const bigint_kernel_2& rhs
        );

        friend const bigint_kernel_2 operator+ (
            const bigint_kernel_2& lhs,
            uint16 rhs
        );

        bigint_kernel_2& operator+= (
            uint16 rhs
        );

        friend const bigint_kernel_2 operator- (
            uint16 lhs,
            const bigint_kernel_2& rhs
        );

        friend const bigint_kernel_2 operator- (
            const bigint_kernel_2& lhs,
            uint16 rhs
        );

        bigint_kernel_2& operator-= (
            uint16 rhs
        );

        friend const bigint_kernel_2 operator* (
            uint16 lhs,
            const bigint_kernel_2& rhs
        );

        friend const bigint_kernel_2 operator* (
            const bigint_kernel_2& lhs,
            uint16 rhs
        );

        bigint_kernel_2& operator*= (
            uint16 rhs
        );

        friend const bigint_kernel_2 operator/ (
            uint16 lhs,
            const bigint_kernel_2& rhs
        );

        friend const bigint_kernel_2 operator/ (
            const bigint_kernel_2& lhs,
            uint16 rhs
        );

        bigint_kernel_2& operator/= (
            uint16 rhs
        );

        friend const bigint_kernel_2 operator% (
            uint16 lhs,
            const bigint_kernel_2& rhs
        );

        friend const bigint_kernel_2 operator% (
            const bigint_kernel_2& lhs,
            uint16 rhs
        );

        bigint_kernel_2& operator%= (
            uint16 rhs
        );

        friend bool operator < (
            uint16 lhs,
            const bigint_kernel_2& rhs
        );

        friend bool operator < (
            const bigint_kernel_2& lhs,
            uint16 rhs
        );

        friend bool operator == (
            const bigint_kernel_2& lhs,
            uint16 rhs
        );

        friend bool operator == (
            uint16 lhs,
            const bigint_kernel_2& rhs
        );

        bigint_kernel_2& operator= (
            uint16 rhs
        );


        void swap (
            bigint_kernel_2& item
        ) { data_record* temp = data; data = item.data; item.data = temp; }


    private:

        typedef double t;
        typedef std::complex<t> ct;

        void fft(
            ct* data, 
            unsigned long len
        ) const;
        /*!
            requires
                - len == x^n for some integer n (i.e. len is a power of 2)
                - len > 0
            ensures
                - #data == the FT decimation in frequency of data
        !*/

        void ifft(
            ct* data, 
            unsigned long len
        ) const;
        /*!
            requires
                - len == x^n for some integer n (i.e. len is a power of 2)
                - len > 0
            ensures
                - #data == the inverse decimation in frequency of data. 
                  (i.e. the inverse of what fft(data,len,-1) does to data)
        !*/

        void long_add (
            const data_record* lhs,
            const data_record* rhs,
            data_record* result
        ) const;
        /*!
            requires
                - result->size >= max(lhs->digits_used,rhs->digits_used) + 1
            ensures
                - result == lhs + rhs
        !*/

        void long_sub (
            const data_record* lhs,
            const data_record* rhs,
            data_record* result
        ) const;
        /*!
            requires
                - lhs >= rhs 
                - result->size >= lhs->digits_used
            ensures
                - result == lhs - rhs
        !*/

        void long_div (
            const data_record* lhs,
            const data_record* rhs,
            data_record* result,
            data_record* remainder
        ) const;
        /*!
            requires 
                - rhs != 0 
                - result->size >= lhs->digits_used 
                - remainder->size >= lhs->digits_used 
                - each parameter is unique (i.e. lhs != result, lhs != remainder, etc.)
            ensures
                - result == lhs / rhs
                - remainder == lhs % rhs
        !*/

        void long_mul (
            const data_record* lhs,
            const data_record* rhs,
            data_record* result
        ) const;
        /*!
            requires
                - result->size >= lhs->digits_used + rhs->digits_used 
                - result != lhs 
                - result != rhs
            ensures
                - result == lhs * rhs
        !*/

        void short_add (
            const data_record* data,
            uint16 value,
            data_record* result            
        ) const;
        /*!
            requires
                - result->size >= data->size + 1
            ensures
                - result == data + value
        !*/

        void short_sub (
            const data_record* data,
            uint16 value,
            data_record* result
        ) const;
        /*!
            requires
                - data >= value 
                - result->size >= data->digits_used
            ensures
                - result == data - value
        !*/

        void short_mul (
            const data_record* data,
            uint16 value,
            data_record* result            
        ) const;
        /*!
            requires
                - result->size >= data->digits_used + 1
            ensures
                - result == data * value
        !*/

        void short_div (
            const data_record* data,            
            uint16 value,
            data_record* result,
            uint16& remainder
        ) const;
        /*!
            requires
                - value != 0 
                - result->size >= data->digits_used
            ensures
                - result = data*value 
                - remainder = data%value
        !*/

        void shift_left (
            const data_record* data,
            data_record* result,
            uint32 shift_amount
        ) const;
        /*!
            requires
                - result->size >= data->digits_used + shift_amount/8 + 1
            ensures
                - result == data << shift_amount
        !*/

        void shift_right (
            const data_record* data,
            data_record* result
        ) const;
        /*!
            requires
                - result->size >= data->digits_used 
            ensures
                - result == data >> 1
        !*/

        bool is_less_than (
            const data_record* lhs,
            const data_record* rhs
        ) const;
        /*! 
            ensures
                - returns true if lhs < rhs 
                - returns false otherwise
        !*/ 

        bool is_equal_to (
            const data_record* lhs,
            const data_record* rhs
        ) const;
        /*!
            ensures
                - returns true if lhs == rhs 
                - returns false otherwise
        !*/

        void increment (
            const data_record* source,
            data_record* dest
        ) const;
        /*!
            requires
                - dest->size >= source->digits_used + 1
            ensures
                - dest = source + 1
        !*/

        void decrement (
            const data_record* source,
            data_record* dest
        ) const;
        /*!
            requires
                source != 0
            ensuers
                dest = source - 1
        !*/

        // member data
        const uint32 slack;
        data_record* data;     
        
        

    };

    inline void swap (
        bigint_kernel_2& a,
        bigint_kernel_2& b
    ) { a.swap(b); }

    inline void serialize (
        const bigint_kernel_2& item, 
        std::ostream& out
    )
    { 
        std::ios::fmtflags oldflags = out.flags();  
        out.flags(); 
        out << item << ' '; 
        out.flags(oldflags); 
        if (!out) throw serialization_error("Error serializing object of type bigint_kernel_c"); 
    }   

    inline void deserialize (
        bigint_kernel_2& item, 
        std::istream& in
    ) 
    { 
        std::ios::fmtflags oldflags = in.flags();  
        in.flags(); 
        in >> item; in.flags(oldflags); 
        if (in.get() != ' ')
        {
            item = 0;
            throw serialization_error("Error deserializing object of type bigint_kernel_c"); 
        }
    }   

    inline bool operator>  (const bigint_kernel_2& a, const bigint_kernel_2& b) { return b < a; } 
    inline bool operator!= (const bigint_kernel_2& a, const bigint_kernel_2& b) { return !(a == b); }
    inline bool operator<= (const bigint_kernel_2& a, const bigint_kernel_2& b) { return !(b < a); }
    inline bool operator>= (const bigint_kernel_2& a, const bigint_kernel_2& b) { return !(a < b); }

}

#ifdef NO_MAKEFILE
#include "bigint_kernel_2.cpp"
#endif

#endif // DLIB_BIGINT_KERNEl_2_

Posted by kinya