Some test code for checking the buffer size needed for karatsuba multiplication in std.internal.math.biguintcore.d of Phobos

kuratsubaBufferSize.d

// See:
// https://issues.dlang.org/show_bug.cgi?id=20493

import std;
void main() {
	foreach(i; 2..10_000) {
		if ((i % 1000) == 0) writeln("i: ", i);
		foreach(j; cast(int) (i * 0.7)..i) {
			check(i, j, i*8/4);   
		}
	}
	writeln("done");
}

enum limit = 2; // karatsuba limit

void check(int ox, int oy, int ob) {
	void kuratsuba(int x, int y, int b) {
		//writeln("x, y, b: ", x, ", ", y, ", ", b);
		if (x <= limit) {
			return;
		}
		const half = (x / 2) + (x & 1);
		b -= half * 2;
		if (b < 0) {
			throw new Exception(text(ox, ", ", oy, ", ", ob));
		}
		kuratsuba(half, half, b);

		const x1 = x-half;
		const y1 = y-half;

		if (2 * y1 * y1 < x1 * x1) {
			if (y1 <= limit) return;
			const quarter = (x1 >> 1) + (x1 & 1);

			if (quarter >= y1) {
				kuratsuba(quarter, y1, b);
			} else {
				kuratsuba(y1, quarter, b);
			}

			if ((x1 - quarter) >= y1) {   
				kuratsuba(x1-quarter, y1, b - y1);
			} else {
				kuratsuba(y1, x1-quarter, b - y1);
			}
			kuratsuba(x1, y1, b);
		} else {
			kuratsuba(x1, y1, b);
		}
	}
	kuratsuba(ox, oy, ob);
}