/* The Great Computer Language Shootout
   http://shootout.alioth.debian.org/

   contributed by Alp Toker <alp@atoker.com>
*/

using System;
using System.Runtime.InteropServices;
using MPZ = BigInteger;

[StructLayout (LayoutKind.Sequential)]
class BigInteger
{
	const string GMP = "libgmp.so.3.3.3";

	[DllImport (GMP, EntryPoint="__gmpz_init")]
		static extern void mpz_init (MPZ mpz);

	[DllImport (GMP, EntryPoint="__gmpz_add")]
		static extern void mpz_add (MPZ dest, MPZ src1, MPZ src2);

	[DllImport (GMP, EntryPoint="__gmpz_sub")]
		static extern void mpz_sub (MPZ dest, MPZ src1, MPZ src2);

	[DllImport (GMP, EntryPoint="__gmpz_mul")]
		static extern void mpz_mul (MPZ dest, MPZ src1, MPZ src2);

	[DllImport (GMP, EntryPoint="__gmpz_divexact")]
		static extern void mpz_divexact (MPZ dest, MPZ src1, MPZ src2);

	[DllImport (GMP, EntryPoint="__gmpz_fdiv_q")]
		static extern void mpz_div (MPZ dest, MPZ src1, MPZ src2);

	[DllImport (GMP, EntryPoint="__gmpz_get_d")]
		static extern double mpz_get_d (MPZ mpz);

	[DllImport (GMP, EntryPoint="__gmpz_set_d")]
		static extern void mpz_set (MPZ mpz, double value);

	[DllImport (GMP, EntryPoint="__gmpz_get_si")]
		static extern int mpz_get_si (MPZ mpz);

	[DllImport (GMP, EntryPoint="__gmpz_set_si")]
		static extern void mpz_set (MPZ mpz, int value);

	/*
		 [DllImport (GMP, EntryPoint="__gmpz_get_str")]
		 static extern string mpz_get_str (string str, int len, MPZ mpz);

		 [DllImport (GMP, EntryPoint="__gmpz_out_str")]
		 static extern int mpz_out_str (uint fd, int x, MPZ src);
		 */

	//Number of limbs allocated and pointed to by the 'limbs' field
	protected int alloc;
	//sign of 'size' indicates the sign of the BigInt
	protected int size;
	//pointer to the limbs
	protected IntPtr limbs;

	protected BigInteger ()
	{
		mpz_init (this);
	}

	public static implicit operator BigInteger (int value)
	{
		BigInteger ret = new BigInteger ();
		mpz_set (ret, value);
		return ret;
	}

	public static explicit operator int (BigInteger value)
	{
		return mpz_get_si (value);
	}

	//TODO: mpz recycling pool
	/*
		 ~BigInteger ()
		 {
		 Console.Write (".");
		 }
		 */

	public static BigInteger operator * (BigInteger bi1, BigInteger bi2)
	{
		BigInteger ret = new BigInteger ();
		mpz_mul (ret, bi1, bi2);
		return ret;
	}

	public static BigInteger operator / (BigInteger bi1, BigInteger bi2)
	{
		BigInteger ret = new BigInteger ();
		mpz_div (ret, bi1, bi2);
		return ret;
	}

	public static BigInteger operator + (BigInteger bi1, BigInteger bi2)
	{
		BigInteger ret = new BigInteger ();
		mpz_add (ret, bi1, bi2);
		return ret;
	}

	public static BigInteger operator - (BigInteger bi1, BigInteger bi2)
	{
		BigInteger ret = new BigInteger ();
		mpz_sub (ret, bi1, bi2);
		return ret;
	}

	public Sign Sign {
		get {
			return size < 0 ? Sign.Negative : Sign.Positive;
		}
	}
}

enum Sign
{
	Negative,
	//Zero,
	Positive,
}