/*  slong.h  by K.Tsuru  */
// file ID = 20
#ifndef S_LONG_H
#define S_LONG_H
/******************
  SLong class
*******************/
class SLong : public SNumber{
    friend class SInteger;
    friend class SDouble;   // LLMult() accesible
    friend struct Ldiv_t;   // SetType() accesible
    SLong& operator=(const SInteger& si);   // has no body
protected :
    void SetString(const char *s);  //set a number by string into figure[] 201
    void SetDouble(double d);           // double or long 202
    void SetSDouble(const SDouble& sd); // 203
    int  CharNthFig(long n) const;  //see source file "slmput.cpp" 204
public :
// fft is usable or not
    bool FFTMultUsable() const; // inline function defined bellow
// Radix conversion DRADIX --> BRADIX XConvToBin() was moved into the class SInteger.

//set a short number, m = 1 can be used but for speed
    void SetLong(long v);               // 205
    void SetShort(short v);             // 206 v within two figures
    void SetSmall(signed char v);       // 207 one figure
    void SetInt(int v){ SetLong(v); }   // an inline function Ver.2.18
//It estimates the number of figures in binary radix(BRADIX).
    uint FigInBRadix(){
        double f = (double)Head()*(double)DFIGURES/log10((double)BRADIX) + 1.0;
        return (uint)f;
    }
// constructor
    SLong():SNumber(DEC_INT){}
    SLong(double d):SNumber(DEC_INT){   SetDouble(d);   }
    SLong(const char* s):SNumber(DEC_INT){  SetString(s);   }
//If this constructor exists SD*SL yelds an ambiguous error in which
//it cannot distinguish SD*SD or SL*SL.It is natural to convert SD*SL into SD*SD.
//Use SL = SD.
#if 0
    SLong(const SDouble& a):SNumber(DEC_INT){
        SetSDouble(a);
    }
#endif
/*
Specifying the type and size.
When the necessary size is previously known use this constructor.
When v_sz > minArraySize it takes into the irreducible size mode.
When v_sz = 0 it does not allocate the memory of figure[].
*/
    SLong(NumberType tp, uint v_sz):SNumber(tp, v_sz){
        if(v_sz) SetZero(); //initialized by zero
    }
//Specifying an initial value.
    SLong(NumberType tp, uint v_sz, double initialValue):SNumber(tp, v_sz){
        SetDouble(initialValue);
    }
// destructor
    ~SLong(){}
// copy constructor
    SLong(const SLong& a):SNumber(a){}
//substitution operators
    SLong& operator=(const char *s) { SetString(s);  return *this; }
    SLong& operator=(double m){ SetDouble(m);  return *this; }
    SLong& operator=(const SDouble& sd){
        SetSDouble(sd);     return *this;
    }
#if 0
//These are not implemented. See SInteger class for the reason.
    SLong(const SInteger& si):SNumber(DEC_INT){
        SetSInteger(si);
    }
    SLong& operator=(const SInteger& si){
        SetSInteger(si);    return *this;
    }
#endif
    SLong& operator=(const SFraction& sf);  // return *this = sf.NumNR()/sf.DenNR(); // defined in "sfract.h"
    // Above cannot be the inline function because SFraction's functions are not given here.
    SLong& operator=(const SLong& a){
        if(this != &a) SNumber::CopyValue(a, SUBS);
        return *this;
    }
    SLong& operator=(const Ldiv_t& a);      // inline function
//It compares two absolute values and returns the same value as that of strcmp().
    friend int LLCompare(const SLong& m, const SLong& n);   // 206
//sub-functions for the fundamental operators.
    friend SLong LLAdd(const SLong& m, const SLong& n); // m+n (m and n have same sign) 207
    friend SLong LLSub(const SLong& m, const SLong& n); // m-n 208
    friend SLong LLMult(const SLong& m, const SLong& n);// m*n 209
//normal method for the multilication
    friend SLong NLLMult(const SLong& m, const SLong& n);// 210
//divide multiplication for the size less than fftMaxSize
    friend SLong DivLLMult(const SLong& m, const SLong& n); // 211
    friend SLong LsMult(const SLong& m, ulong n);                 // 212
//If rem != NULL it sets remainder into *rem.
    friend SLong LsDiv(const SLong& m, ulong n, long* rem = NULL);// 213
/*
division for long numbers
In KnuthLLDiv or NewtonLLDiv it is assumed thet the checking m > n > ULONG_MAX/m.Radix()
etc is already done in LLDiv().Pay attention for the direct call.
NewtonLLDiv can be used for SLong with radix DRADIX.
If you do not need the remainder set "rem" by false.
To avoid wrong use these functions are the protected members. ver. 2.81
*/
protected:
    Ldiv_t NewtonLLDiv(const SLong& m, const SLong& n, bool needRem);// 214
    Ldiv_t KnuthLLDiv(const SLong& m, const SLong& n, bool needRem); // 215
    static int llDivMode;
public:
    friend Ldiv_t LLDiv(const SLong& m, const SLong& n, bool needRem);  // 216
    friend SLong LLDiv(const SLong& m, const SLong& n); // 217 introduced since ver. 2.30
    enum { reset = 0, Knuth = 1, Newton = 2, SetByUser = 8 };
 // Do not add ") const {" to static functions
    static void SetLLDivMode(int dm) { llDivMode = dm ? (dm | SetByUser) : dm; }
    static int  LLDivMode()     {   return llDivMode & 3;   }   // return lower 2 bits.
    static void UseKnuthLLDiv() {   SetLLDivMode(Knuth);    }
    static void UseNewtonLLDiv(){   SetLLDivMode(Newton);   }
//It designates to use whether KnuthLLDiv or NewtonLLDiv routine.
//For many figures the Newton's method is faster.
    static bool KnuthLLDivIsFaster(const SLong& m, const SLong& n) {
        uint mf = m.Head(), nf = n.Head();
        return (diff(mf, nf) > 10u) && (mf + nf < 400u);    // diff(a,b) = |a-b|
    }
    static bool NewtonLLDivIsFaster(const SLong& m, const SLong& n) {
        return !KnuthLLDivIsFaster(m, n);
    }
/*
For huge number over 'fftMaxArraySize'.
*/
private:
// huge * huge
// default values : hhMultMode = Karatsuba_HH_MULT, pfHHMult = DisKHHMult  ver. 2.17
// default values : usesKaratsuba_HH_Mult = true
//  static int hhMultMode; //
    static bool usesKaratsuba_HH_Mult;
    
//  static void (*pfHHMult)(const SLong& x, const SLong& y, SLong& z);  // 209
public:
 // Do not add ") const {" to static functions
    static void KaratsubaMultSwitch(bool a) { usesKaratsuba_HH_Mult = a; }
    static bool UsesKaratsubaMult() { return usesKaratsuba_HH_Mult; }
/*
FFT multiplication.
It does not depend on radix.
*/
    uint FFTMaxArraySize() const {
        return (Type() == DEC_INT) ? fftMaxArraySize : fftMaxArraySize/8u;  // "/4u" --> "/8u" since version 2.30
    }
// protected: for test
// member functions in protected section from friend ones.
//  z = x*y
    void LLMultFFT(const SLong& x, const SLong& y, SLong& z, uint n); // z = x*y 217
protected:
/*
 z = (huge x) * (huge y)
*/
//normal method (default) It needs rather small memory.
//In the following three functions it must be satisfied that &z!=&x and &z!=&y.
//Using as xxxHHNult(x,y,x) yileds a run time error.
// Normal method using distribution law
    void NHHMult(const SLong& x, const SLong& y, SLong& z);     // 218
// Karatsuba's multiplication using recursive calls.
//z = (huge x) * (huge y) for x.Size() >= y.Size(), distribution method(Karatsuba's multiplication)
    void KaratsubaHHMult(const SLong& x, const SLong& y, SLong& z); // 219
//z = (huge x) * (huge y) for x.Size() == y.Size() same size
//It provides the Karatsuba's multiplication using recursive calls.
//It needs a large memory.
    void KHHMult(const SLong& x, const SLong& y, SLong& z);     // 220
/*
It puts the lower part of x into "lower" and the upper part into "upper".
sub-function for KHHMult()
*/
    void SLDivHalf(const SLong& x, SLong& lower, SLong& upper); // 221
/*
It cuts out from src[pos] with a length "size" and puts into
dest[0]...dest[size-1]. It attaches the same sign to "dest" as that of "src".
If pos > src.Head() dest=0.
*/
    void SLCutOut(SLong& dest, const SLong& src, uint pos, uint size);  // 222
public:
//fundamental operators
    friend SLong operator+(const SLong& m, const SLong& n); // m+n not "return LLAdd(m, n)" 224
    friend SLong operator-(const SLong& m, const SLong& n); // m-n not "return LLSub(m, n)" 225
//multiplication/division If n is small LsMult() or LsDiv() is faster.  // 226

    friend SLong operator*(const SLong& m, double d);   // m*d  227
    friend SLong operator*(double d, const SLong& n){ return n*d;   }
//  friend SLong operator/(const SLong& m, const SLong& n);     // defined below as inline function since ver. 2.30
    friend SLong operator/(const SLong& m, double d);           // 229
    friend SLong operator%(const SLong& m, const SLong& n);     // 230
    friend SLong operator%(const SLong& m, double d);           // 231

    SLong& operator+=(const SLong& n) { return (*this = *this + n); }
    SLong& operator-=(const SLong& n) { return (*this = *this - n); }
    SLong& operator*=(const SLong& n) { return *this = LLMult(*this, n); }
    SLong& operator*=(double d) { return (*this = *this * d); }
    SLong& operator/=(const SLong& n) { return *this = LLDiv(*this, n); }
    SLong& operator/=(double d) { return (*this = *this / d); }
    SLong& operator%=(const SLong& n) { return (*this = *this % n); }
    SLong& operator%=(double d) { return (*this = *this % d); }

    void    LsAdd(fType a); //It adds a small value. It is used in the radix convesion. 232
                            //I do not have LsSub().
    void    LsPlus(fType a);    //sub-function for operator++()     233
    void    LsMinus(fType a);   //operator--()                      234
//It divides by two. Except a large routine use m/2 or LsDiv(m,2).
//To judge even or odd see the value of n(0) % 2.
    friend SLong LDiv2(const SLong& n);                             // 235
/*
It divides m by the p-th power of two, i.e. q=m/(2^p),
where 2^p < ULONG_MAX/radix. It returns the remainder.
Comparing a statement
    q = LsDiv(m, 1uL << p);
it is faster a few times. It is used in ReduceByPow2Rdx(), etc.
*/
    friend long LDivPow2(const SLong& m, SLong& q, uint p);        // 236
    //prefix increment and decrement operators
    SLong& operator++(){    LsPlus(1);  return *this;   }
    SLong& operator--(){    LsMinus(1); return *this;   }
    //postfix incremant and decrement operators
    //See the source file "slopppsf.cpp" for details.
    const SLong operator++(int){// to inline function since ver. 2.30
        SLong oldValue(*this);  // keep the old value
        LsPlus(1);              // add one
        return oldValue;        // return the old value
    }
    const SLong operator--(int){// see above
        SLong oldValue(*this);
        LsMinus(1);
        return oldValue;
    }

//  bit(& | >> <<) operators
    friend SLong operator&(const SLong& m, const SLong& n);     // 241
    friend SLong operator|(const SLong& m, const SLong& n);     // 242
    friend SLong operator>>(const SLong& m, ulong n);               // 243
    friend SLong operator<<(const SLong& m, ulong n);               // 244
    SLong& operator>>=(ulong n) { return (*this = *this >> n); }
    SLong& operator<<=(ulong n) { return (*this = *this << n); }
    SLong& operator&=(const SLong& n) { return (*this = *this & n); }
    SLong& operator|=(const SLong& n) { return (*this = *this | n); }

private:    // Has no body and cannot use.
    SLong  operator^(const SLong& m) const;
    SLong& operator^=(const SLong& n);
    SLong  operator~() const;
public:
//It multiplies by n-th power of radix(DRADIX, BRADIX).
    SLong& MultPowRdx(int n){
        if(Sign(21) && n) ShiftArray(n);
        if(Sign() && (n < 0) ) DoCutDown();
        return *this;
    }
//It multiplies by p-th power of ten 10. DRADIX only
    SLong& MultPow10(long p);                               // 251
//It returns the number of figures in a decimal system. DRADIX only
    long    DFigures() const;                               // 252
//sign operators
    SLong operator+() const { return *this; }
    SLong operator-() const { // Move into inline since ver. 2.30
        SLong r(*this);
        r.ChangeSign(253);
        return r;
    }
// |*this| == 1 or not. When true it returns the sign(1 or -1).
    int IsOne() const {
        if(aHead) return 0;
        return figure(0) == 1 ? Sign(22) : 0;
    }
//It returns the lower two figures by unsigned long. It does not to check
//that the value is initialized or not.
    ulong Low2() const {
        return (ulong)figure(1)*(ulong)Radix() + (ulong)figure(0);
    }
/****************************************************************************
output functions
Put() : not carridge return, Puts() : feed new line
Insert delimiter given by "delmt" at intervals of "fig" characters.
If delmt == 0, no delimiter is inserted.
If fU (figUnit) == 0, it continuously outputs with neither delimiter nor carridge return.
perLine = the number of blocks which contains "fig" decimal per line
default : perLine = 0 automatically set perLine = displayWidth/(fig+1)
Give to "lineFormat" a value of bit sum of the following enumeration numbers
NO_CR : no '\n'
CRLF : Considering the width of display it puts a '\n' after putting an appropriate
digits.
CONTINUE : By putting '\' at the line end it makes a continuous line.
END_CR : It adds a '\n' at the last of output.
***********************************************************************/
    static long figUnit;
    static int  perLine;
    static int  lineFormat;
    static int  delmt;
    static long ioCount;    // the number of input or output characters
    enum { NO_CR = 0, CRLF = 1, CONTINUE = 2, END_CR =4 };
    static void SetFormat(long fU, long pL = 0, int lF = CRLF, int dm = ' ');
    static void DefaultFormat(); // It restores the default values.
    long Put(long fU=10, int pL = 0, int lF = CRLF, int dlmt=' ') const;    // 261
        // If fU < 0 parameters by SetFormat() are used example Put(-1);
    long Puts(long fU=10, int pL = 0, int lF = CRLF, int dlmt=' ') const;
//It outputs the inner expression.
    long RawPut(int crlf = 0) const;        // 262
    long RawPuts() const {  return RawPut(1);   }

    friend ostream& operator<<(ostream& os, const SLong& sl);   // 263 added since version 2.21
};
/******************** End of SLong class ********************/
inline SLong operator/(const SLong& m, const SLong& n){
    return LLDiv(m, n);
}
inline SLong operator*(const SLong& m, const SLong& n) {
    return LLMult(m, n);
}
//The FFT multiplication can be done by calling once or not.
inline bool SLong::FFTMultUsable() const {
    return ( 2u*aHead < fftMaxArraySize ) && FFTUse() && (aHead >= FFTMinSize());
}
//It returns the number of figures. SLong class only
inline long SLong::DFigures() const{
    if( !Sign(23) ) return 0;
    return (long)iFigures(figure(aHead)) + (long)aHead*(long)DFIGURES;
}
inline long SLong::Puts(long fig, int perLine, int lineFormat, int delmt) const {
    long l = Put(fig, perLine, lineFormat|END_CR, delmt);
    FPutc('\n');
    return l+1;
}
 
/***********************************************************************
It defines a structure which has a quotient and a remainder as members,
i.e. the SLong version of div_t.
  x = q*y + r
The quotient is decided by q = x/y and the remainder by r = x - q*y.
It can be r < 0. For example
 x = -5, y = -2
 (-5)/(-2) = 2 = q,  -5 = 2*(-2) -1
then  r = -1.
*************************************************************************/
struct Ldiv_t{
    friend class SLong;
    SLong   quot;   //quotient : a public member
    SLong   rem;    //remainder
//default constructor
    Ldiv_t(): quot(), rem(){}
// Ldiv_t f(){ return 0.0; } can be used.
    Ldiv_t(double q):quot(q), rem(0.0){}
// return Ldiv_t(q, m);
    Ldiv_t(const SLong& q, const SLong& r):quot(q), rem(r){}
// return q
    Ldiv_t(const SLong& q):quot(q), rem(q.Type(), minArraySize){}
// copy constructor.
    Ldiv_t(const Ldiv_t& m);                        // 275
//substitution oparator
    Ldiv_t& operator=(const Ldiv_t& a){
        if(this != &a){
            quot = a.quot;      rem = a.rem;
        }
        return *this;
    }
};
//substitution operator SLong = Ldiv_t
//a member of SLong class
//This is defined here where the structure of Ldiv_t is known.
inline SLong& SLong::operator=(const Ldiv_t& a){
    return *this = a.quot;
}
/* defined in template
inline istream& operator>>(istream& s, SLong& a) // added since version 2.21
{
    string buf;
    std::getline(s, buf);   // usage : cin >> a; ( s = cin )
    a = buf.data();
    return s;
}
*/
static const SLong SL_ONE(1.0);
#endif  // S_LONG_H