public class Multiplication {
	// rrrrgh
	static class DivResult {
		int q;
		int r;

		public DivResult(int q, int r) {
			this.q = q;
			this.r = r;
		}

		public String toString() {
			return "%d R %d".formatted(q, r);
		}
	}

	public static void main(String[] args) {
		System.out.println("Remember that \"exponential\" and \"linear\" refer to");
		System.out.println("how many steps the algorithm takes based on the number");
		System.out.println("of bits in the input numbers.");
		System.out.println();

		// Change these!
		int A = 4209;
		int B = 77;

		System.out.printf("dividing %d / %d (which should be %d R %d)\n", A, B, A / B, A % B);
		System.out.printf("exponential = %s\n", exponentialTime(A, B));
		System.out.printf("linear = %s\n", linearTime(A, B));

		// there IS no parallel division algorithm! at least, that's what I want you to think.
	}

	// The extremely stupid exponential time algorithm that subtracts the divisor from the dividend
	// until it can't be subtracted anymore. If you add one more bit to the input numbers, the
	// number of steps doubles.
	public static DivResult exponentialTime(int dividend, int divisor) {
		int iterations = 0;
		int quotient = 0;
		int remainder = dividend;

		// this code will just fall on its face with negative numbers.
		// not gonna bother.

		// here it is!
		while(remainder >= divisor) {
			quotient++;
			remainder -= divisor;
			iterations++;
		}

		System.out.printf("exponential time took %d iterations\n", iterations);

		return new DivResult(quotient, remainder);
	}

	// The grade school algorithm.
	public static DivResult linearTime(int dividend, int divisor) {
		int iterations = 0;
		int quotient = 0;
		long remainder = dividend;

		// we are forced to do a fixed 32 iterations here for all 32 bits of the ints.
		for(int i = 31; i >= 0; i--) {
			long partial = ((long)divisor) << i;

			if(partial <= remainder) {
				remainder -= partial;
				quotient = (quotient << 1) | 1; // append a 1
			} else {
				quotient = quotient << 1;       // append a 0
			}

			iterations++;
		}

		System.out.printf("linear time took %d iterations\n", iterations);

		return new DivResult(quotient, (int)remainder);
	}
}