Update utils.ts

[KhalidMustafin]

Replace recursion with more stable binary search for root calc

[KhalidMustafin]

Hey, guys! Could you please approve the workflow?

[crispheaney]

the square root fn as is right now looks like it's about 2-5x faster, which is important for drift ui and why we have the recursive implementation

any ideas on making it faster and more stable?

import {BN} from "@coral-xyz/anchor";

const squareRootBN = (n) => {
	if (n.lt(new BN(0))) {
		throw new Error('Sqrt only works on non-negative inputs');
	}
	if (n.lt(new BN(2))) {
		return n;
	}

	let low = new BN(1);
	let high = n;
	const two = new BN(2);

	while (low.lt(high)) {
		const mid = low.add(high).div(two);
		const midSquared = mid.mul(mid);
		if (midSquared.eq(n)) {
			return mid;
		} else if (midSquared.lt(n)) {
			low = mid.add(new BN(1));
		} else {
			high = mid.sub(new BN(1));
		}
	}
	return high;
};

const squareRootBN2 = (n) => {
	if (n.lt(new BN(0))) {
		throw new Error('Sqrt only works on non-negative inputs');
	}
	if (n.lt(new BN(2))) {
		return n;
	}
	const smallCand = squareRootBN(n.shrn(2)).shln(1);
	const largeCand = smallCand.add(new BN(1));

	if (largeCand.mul(largeCand).gt(n)) {
		return smallCand;
	} else {
		return largeCand;
	}
};


const benchmark = (fn, numbers) => {
	console.time(fn.name);
	numbers.forEach(n => fn(n));
	console.timeEnd(fn.name);
};

const generateTestNumbers = (count, max) => {
	const numbers = [];
	for (let i = 0; i < count; i++) {
		numbers.push(new BN(Math.floor(Math.random() * max)));
	}
	return numbers;
};

const testNumbers = generateTestNumbers(1000, 1000000);

benchmark(squareRootBN, testNumbers);
benchmark(squareRootBN2, testNumbers);

squareRootBN: 47.171ms
squareRootBN2: 11.706ms

[KhalidMustafin]

@crispheaney Hi! I apologize for such a long response. I don’t quite understand why you are calling my function from yours? It seems that therefore the time is measured incorrectly.