namespace BigNum
{
  /*
    Unsigned::copy 部分コピー

    const Unsigned& num : 対象の Unsigned
    size_t s, e : コピーする要素の位置(開始・終了)

    this == &num の場合は処理しないことに注意
  */
  void Unsigned::copy( const Unsigned& num, size_t s, size_t e )
  {
    if ( this == &num ) return;

    number_.clear();
    if ( e - s + 1 > number_.capacity() )
      number_.reserve( e - s + 1 );
    while ( s <= e ) {
      if ( s >= num.size() ) break;
      push_upper( num.number_[s++] );
    }
    if ( size() == 0 ) push_upper();
    negZero();
  }

  /*
    Unsigned::karaMul Karatsuba乗算

    const Unsigned& v : 乗数
    UnsignedBuff recLvl : 再帰処理を行う指数のしきい値(2^recLvlをサイズのしきい値とする)
  */
  Unsigned& Unsigned::karaMul( const Unsigned& v, UnsignedBuff recLvl )
  {
    if ( isNaN( v ) ) return( *this );

    UnsignedBuff i = ( size() > v.size() ) ? size() : v.size();
    // i以上で 2のべき乗になる数値を取得する
    UnsignedBuff sz = 2;
    while ( i > sz )
      sz <<= 1;

    // recLvlから再帰を行うサイズのしきい値を計算する
    UnsignedBuff recSz = std::pow( 2, recLvl );

    Unsigned u( *this );
    karaMul_Main( u, v, *this, 0, sz, recSz );

    return( *this );
  }

  /*
    Unsigned::karaMul_Main Karatsuba乗算メインルーチン

    const Unsigned& u : 被乗数
    const Unsigned& v : 乗数
    Unsigned& ans : 結果を格納する多倍長整数
    UnsignedBuff start : u,vの中の部分数列の開始位置
    UnsignedBuff sz : u,vの中の部分数列のサイズ
    UnsignedBuff recSz : 再帰処理を行うサイズのしきい値
  */
  void Unsigned::karaMul_Main( const Unsigned& u, const Unsigned& v, Unsigned& ans, UnsignedBuff start, UnsignedBuff sz, UnsignedBuff recSz )
  {
    if ( start >= u.number_.size() || start >= v.number_.size() ) {
      ans.clear();
      return;
    }

    // 再帰レベル以下になったら通常の乗算処理
    if ( sz <= recSz ) {
      if ( sz == 1 ) {
        ans.clear();
        ans.number_[0] = u.number_[start];
        ans.mulOneDigit( v.number_[start] );
      } else {
        ans.copy( u, start, start + sz - 1 );
        Unsigned v2( v, start, start + sz - 1 );
        ans *= v2;
      }
      return;
    }

    // |u0 - u1|, |v0 - v1| を計算
    sz >>= 1;
    Unsigned u01, v01;
    bool bu = u.partialSub( u01, start, sz );
    bool bv = v.partialSub( v01, start, sz );
    bool sign = ( bu == bv ) ? false : true; // (u0 - u1)(v0 - v1)の正負判定

    // u0v0, u1v1, (u0 - u1)(v0 - v1) の積を計算
    Unsigned uv0, uv1, uv01;
    karaMul_Main( u, v, uv0, start, sz, recSz );
    karaMul_Main( u, v, uv1, start + sz, sz, recSz );
    karaMul_Main( u01, v01, uv01, 0, sz, recSz );

    // u1v0 + u0v1 の計算
    ans = uv0;
    ans += uv1;
    if ( sign )
      ans += uv01;
    else
      ans -= uv01;

    // u1v1とu0v0をシフトさせながら加算
    uv1.ushift( sz * 2 );
    ans.ushift( sz );
    ans += uv0;
    ans += uv1;

    return;
  }

  /*
    Unsigned::partialSub 数列の一部を前半と後半に分割して減算処理を行う

    xxxxxxxxAAAAAAAABBBBBBBBxxxxxxxxxxxx -> |AAAAAAAA-BBBBBBBB|
            start   start+sz

    Unsigned& u : 減算結果を格納する多倍長整数
    UnsignedBuff start : 前半数列の開始位置
    UnsignedBuff sz : 部分数列のサイズ

    戻り値 : 前半部分の方が小さければTrueを返す
  */
  bool Unsigned::partialSub( Unsigned& u, UnsignedBuff start, UnsignedBuff sz ) const
  {
    bool b = partialLess( start, sz );
    if ( b ) {
      u.copy( *this, start + sz, start + sz * 2 - 1 );
      u -= Unsigned( *this, start, start + sz - 1 );
    } else {
      u.copy( *this, start, start + sz - 1 );
      u -= Unsigned( *this, start + sz, start + sz * 2 - 1 );
    }

    return( b );
  }

  /*
    Unsigned::partialLess 数列の一部を前半と後半に分割して比較処理を行う

    xxxxxxxx+--------+--------+xxxxxxxxxxxx
            start    start+sz

    UnsignedBuff start : 比較開始位置
    UnsignedBuff sz : 比較する部分数列のサイズ

    戻り値 : 前半部分の方が小さければTrueを返す
  */
  bool Unsigned::partialLess( UnsignedBuff start, UnsignedBuff sz ) const
  {
    for ( UnsignedBuff i = sz ; i > 0 ; i-- ) {
      Digit l = ( start + i - 1 >= size() ) ? 0 : number_[start + i - 1];
      Digit u = ( start + sz + i - 1 >= size() ) ? 0 : number_[start + sz + i - 1];
      if ( l != u ) return( l < u );
    }

    return( false );
  }
}

namespace BigNum
{
  /*
    Unsigned::toomCook Toom-Cook法による乗算

    被乗数 uと乗数 vに対して

     u = Σ(ur * x^r) , v = Σ(vr * x^r)

    の形に分解し、それぞれの係数を求める

    const Unsigned& v : 乗数
    UnsignedBuff r : 分割単位 - 1 (u,vを多項式と見たときの最大指数)
  */
  Unsigned& Unsigned::toomCook( const Unsigned& v, UnsignedBuff r )
  {
    if ( r == 0 ) {
      operator*=( v );
      return( *this );
    }
    if ( isNaN( v ) ) return( *this );

    UnsignedBuff i = ( size() > v.size() ) ? size() : v.size();
    r++;
    UnsignedBuff sz = i / r; // 分割後のサイズ
    if ( ( i % r ) != 0 ) sz++;

    // 値を分割して配列に代入
    Unsigned uArray[r];
    Unsigned vArray[r];
    for ( i = 0 ; i < r ; i++ ) {
      uArray[i] = Unsigned( *this, i * sz, ( i + 1 ) * sz - 1 );
    }
    for ( i = 0 ; i < r ; i++ ) {
      vArray[i] = Unsigned( v, i * sz, ( i + 1 ) * sz - 1 );
    }

    // uvの指数を計算(=求めるべき係数の数)
    UnsignedBuff k = r * 2 + 1;

    // w(i) = u(i)v(i)を計算
    vector< Unsigned > w;
    w.push_back( uArray[0] * vArray[0] );
    for ( i = 1 ; i < k ; i++ ) {
      Unsigned u2( uArray[0] );
      Unsigned v2( vArray[0] );
      for ( UnsignedBuff j = 1 ; j < r ; j++ ) {
        Unsigned p( i );
        p.pow( j );
        u2 += uArray[j] * p;
        v2 += vArray[j] * p;
      }
      u2 *= v2;
      w.push_back( u2 );
    }

    // ( w(i+1) - w(i) ) / i を計算
    for ( i = 1 ; i < k ; i++ ) {
      vector< Unsigned > d;
      for ( UnsignedBuff j = i ; j < k ; j++ )
        d.push_back( w[j] - w[j-1] );
      for ( UnsignedBuff j = i ; j < k ; j++ ) {
        w[j] = d[j-i];
        w[j] /= i;
      }
    }

    clear();

    // 係数の計算
    vector< Unsigned > d;
    for ( i = k - 2 ; i > 0 ; i-- )
      d.push_back( w[k-1] );
    for ( i = k - 2 ; i > 0 ; i-- ) {
      for ( UnsignedBuff j = 0 ; j < i ; j++ ) {
        d[j] *= i - j;
        w[i] -= d[j];
        d[j] = w[i];
      }
    }

    // 係数を使って結果を算出
    for ( i = k ; i > 0 ; --i )
      partialAdd( w[i - 1], ( i - 1 ) * sz );

    return( *this );
  }
}

/*
  有効ビット数をカウントする

  short s : 対象の数値

  戻り値 : 有効ビット数
*/
unsigned int countBit( short s )
{
  if ( s < 0 ) s *= -1;
  unsigned int bitCnt = 0;
  while ( s != 0 ) {
    s >>= 1;
    bitCnt++;
  }

  return( bitCnt + 1 );
}

/*
  ブースの乗算処理

  short u : 被乗数
  short v : 乗数

  戻り値 : 算術結果

  u は15Bit(-16384〜16383) , v は16Bit(-32768〜32767)までとする。
  範囲外だった場合は0を返す。
*/
int boothMul( short u, short v )
{
  if ( u == 0 || v == 0 ) return( 0 );

  if ( countBit( u ) > 15 ) return( 0 );
  unsigned int vBit = countBit( v );
  unsigned short vMask = ( 1 << ( vBit + 1 ) ) - 1;

  int a = u << ( vBit + 1 );    // add(加算)
  int s = (-u) << ( vBit + 1 ); // sub(減算)
  int p = ( v << 1 ) & vMask;   // product(積)

  for ( unsigned int i = 0 ; i < vBit ; i++ ) {
    int bits = p & 3; // pの下位2Bits
    if ( bits == 1 )
      p += a;
    else if ( bits == 2 )
      p += s;
    p >>= 1;
  }

  return( p >> 1 );
}