Add nth root support for u256 and u128 types

[xgreenx]

fuel-vm/fuel-vm/src/interpreter/executors/instruction.rs

Lines 248 to 304 in 9478991

	pub fn checked_nth_root(target: u64, nth_root: u64) -> Option<u64> {
	if nth_root == 0 {
	// Zeroth root is not defined
	return None
	}
	if nth_root == 1 || target <= 1 {
	// Corner cases
	return Some(target)
	}
	if nth_root >= target || nth_root > 64 {
	// For any root >= target, result always 1
	// For any n>1, n**64 can never fit into u64
	return Some(1)
	}
	let nth_root = u32::try_from(nth_root).expect("Never loses bits, checked above");
	// Use floating point operation to get an approximation for the starting point.
	// This is at most off by one in either direction.
	#[cfg(feature = "std")]
	let powf = f64::powf;
	#[cfg(not(feature = "std"))]
	let powf = libm::pow;
	#[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
	let guess = powf(target as f64, (nth_root as f64).recip()) as u64;
	debug_assert!(guess != 0, "This should never occur for {{target, n}} > 1");
	// Check if a value raised to nth_power is below the target value, handling overflow
	// correctly
	let is_nth_power_below_target = |v: u64| match v.checked_pow(nth_root) {
	Some(pow) => target < pow,
	None => true, // v**nth_root >= 2**64 and target < 2**64
	};
	// Compute guess**n to check if the guess is too large.
	// Note that if guess == 1, then g1 == 1 as well, meaning that we will not return
	// here.
	if is_nth_power_below_target(guess) {
	return Some(guess.saturating_sub(1))
	}
	// Check if the initial guess was correct
	let guess_plus_one = guess.checked_add(1).expect(
	"Guess cannot be u64::MAX, as we have taken a root > 2 of a value to get it",
	);
	if is_nth_power_below_target(guess_plus_one) {
	return Some(guess)
	}
	// If not, then the value above must be the correct one.
	Some(guess_plus_one)
	}

We already implement this for u64, but are missing it for the other types

[Dentosal]

This is really hard to do, as the floating point approximation method used in the u64 implementation cannot be used with wider types. We could do binary search using rougher guesses, or even attempt Newton's method. But those have high upper bound costs.

[MitchTurner]

It sounds like Mira is already trying to come up with a solution for this. If our users need this feature, we might as well provide a native way of doing it. It might be expensive, but still less expensive than implementing it using the VM.