MathBigInteger.hpp

Go to the documentation of this file.

/*****************************************************************************
 * Copyright (C) 2012 by Benjamin Hadorn (b_hadorn@bluewin.ch)
 *****************************************************************************
 * Project    : Zeus Base Library
 * Module     : MathBigInteger
 * Package    : Zeus.ZeusBase.Math
 * Author     : Benjamin Hadorn
 * Date       : 08.01.2012
 * System     : Zeus-Framework
 *****************************************************************************
 * Licence:                                                                  *
 *   This library is free software; you can redistribute it and/or modify    *
 *   it under the terms of the GNU Lesser General Public License as          *
 *   published by the Free Software Foundation; either version               *
 *   2.1 of the License, or (at your option) any later version.              *
 *                                                                           *
 *   This library is distributed in the hope that it will be useful,         *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of          *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the            *
 *   GNU Lesser General Public License for more details.                     *
 *                                                                           *
 *   You should have received a copy of the GNU Lesser General Public        *
 *   License along with this library; if not, write to the Free Software     *
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110, USA    *
 *****************************************************************************/

/*****************************************************************************
 * Changes:
 *****************************************************************************/

#ifndef MathBigIntegerHPP
#define MathBigIntegerHPP

#include <zeusbase/System/BigInteger.hpp>

BEGIN_NAMESPACE_Zeus

/**************************************************************************/
/**************************************************************************/
template <int N> class TMathBigInteger
{
  public:
    /**********************************************************************/
    /**********************************************************************/
    static TBigInteger<N> gcd(const TBigInteger<N>& rA,
                              const TBigInteger<N>& rB,
                              TBigInteger<N>& rX,
                              TBigInteger<N>& rY)
    {
      rX = 1;
      rY = 0;
      TBigInteger<N> X1 = 0;
      TBigInteger<N> Y1 = 1;
      TBigInteger<N> A(rA);
      TBigInteger<N> B(rB);

      while (!B.isZero())
      {
        TBigInteger<N> Temp = B;

        //Quotient = A / B;
        //B = A % B;
        TBigInteger<N> Quotient(A);
        Quotient.divideExt(Temp, B); //integer div

        //B = A % B;
        //B = A.mod(B);
        A = Temp;

        Temp = X1;
        //X1 = rX - Quotient * X1;
        X1 = Quotient;
        X1.multiply(Temp);
        X1.negate();
        X1.add(rX);
        rX = Temp;

        Temp = Y1;
        //Y1 = rY - Quotient * Y1;
        Y1 = Quotient;
        Y1.multiply(Temp);
        Y1.negate();
        Y1.add(rY);
        rY = Temp;
      }
      return A;
    }
};

END_NAMESPACE_Zeus

#endif