/*
 * DSI utilities
 *
 * Copyright (C) 2012-2023 Sebastiano Vigna
 *
 * This program and the accompanying materials are made available under the
 * terms of the GNU Lesser General Public License v2.1 or later,
 * which is available at
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1-standalone.html,
 * or the Apache Software License 2.0, which is available at
 * https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This program 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.
 *
 * SPDX-License-Identifier: LGPL-2.1-or-later OR Apache-2.0
 */

package it.unimi.dsi.test;

import java.math.BigInteger;

public class XorShiftPoly116 {

	private XorShiftPoly116() {}

	/** The number of bits of state of the generator. */
	public static final int BITS = 116;

	/** The period of the generator (2<sup>{@value #BITS}</sup> &minus; 1). */
	public static BigInteger twoToBitsMinus1;

	/** Factors of 2<sup>{@value #BITS}</sup> &minus; - 1. */
	public static final BigInteger[] factor = {
		new BigInteger("3"),
		new BigInteger("5"),
		new BigInteger("59"),
		new BigInteger("233"),
		new BigInteger("1103"),
		new BigInteger("2089"),
		new BigInteger("3033169"),
		new BigInteger("107367629"),
		new BigInteger("536903681")
	};

	/** An array of cofactors. Entry 0 &le; {@code i} &lt; {@link #numCofactors} contains {@link #twoToBitsMinus1} divided by {@link #factor factor[i]}. Note that some
	 * entries can be {@code null} if {@link #BITS} is less then 4096. */
	public static final BigInteger[] cofactor = new BigInteger[factor.length];

	/** The actual number of valid entries in {@link #cofactor}. */
	public static int numCofactors;

	/** Computes the power to a given exponent, given the quadratures.
	 *
	 * @param e an exponent smaller than or equal to 2<sup>{@link #BITS}</sup>.
	 */
	public static void mPow(BigInteger e) {
		System.out.println("p := 1;");
		for(int i = 0; ! e.equals(BigInteger.ZERO); i++) {
			if (e.testBit(0)) System.out.println("p := *p * q[" + i + "];");
			e = e.shiftRight(1);
		}
	}

	public static void main(final String arg[]) {
		// Check factors
		BigInteger prod = BigInteger.ONE;
		for(final BigInteger f : factor) prod = prod.multiply(f);
		if (!prod.equals(BigInteger.valueOf(2).pow(BITS).subtract(BigInteger.ONE))) {
			System.err.println("Factors do not match");
			return;
		}

		BigInteger result = BigInteger.ONE;
		twoToBitsMinus1 = BigInteger.valueOf(2).pow(BITS).subtract(BigInteger.ONE);
		int n;
		// Initialize cofactors.
		for(n = 0; n < factor.length; n++) {
			cofactor[n] = twoToBitsMinus1.divide(factor[n]);
			result = result.multiply(factor[n]);
		}

		// Safety check (you know, those numbers are LONG).
		if (! twoToBitsMinus1.equals(result)) throw new AssertionError();

		System.out.println("Array q[" + (BITS + 1) + "];");
		// Quadratures
		System.out.println("q[0] := x;");
		for(int i1 = 1; i1 <= BITS; i1++) System.out.println("q[" + i1 + "] := q[" + (i1 - 1) + "] * q[" + (i1 - 1) + "];");
		System.out.println("!!('Check: ', if q[" + BITS + "] = x then 1 else 0; &q fi);");
		// Exponentiation to cofactors
		for (final BigInteger element : cofactor) {
			mPow(element);
			System.out.println("!!('Result: ', if p = 1 then 0; &q else 1 fi);");
		}
	}
}