bigint
このオブジェクトは任意精度の符号なし整数を表します。とても簡単です。そのインターフェースは普通のint型のようなものです。どれだけのメモリを使うべきか、あるいは何か変わったことを言う必要はありません。それだけです：）
#include <dlib / bigint.h>
実装：
この実装は符号なしshort型の配列を使って行われます。それはまた参照カウントです。詳細については上記のリンクを参照してください。また、kernel_2はほとんどすべての場合において高速であるはずなので、実際にはそのバージョンのbigintオブジェクトを使用する必要があります。
| kernel_1a | bigint_kernel_1のtypedefです。 |
| kernel_1a_c | その前提条件をチェックするkernel_1aのtypedefです。 |
この実装は基本的にkernel_1と同じですが、高速フーリエ変換を使用して乗算をはるかに高速に実行します。
| kernel_2a | bigint_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_