Take a very long time to wait result

[mohanson]

use numext_fixed_uint::U4096;

fn main() {
    let a = U4096::from_dec_str("3930061525912861057173624287137506221892737197425280369698987").unwrap();
    let b = U4096::from_dec_str("57896044618658097711785492504343953926634992332820282019728792003956564819968").unwrap();
    println!("{}", &a * &a % b);
}

I have wait serveral minutes and finally I give up.

[chaoticlonghair]

rust-numext/constructor/src/fixed_uint/core/internal/private_ops.rs

Lines 554 to 564 in 1481b3d

	minuend_tmp
	};
	let (copy_new, _) = copy._sub(&minuend);
	copy = copy_new;
	}
	let mut more: #unit_suffix = 0;
	while copy >= *other {
	let (copy_new, _) = copy._sub(other);
	copy = copy_new;
	more += 1;
	}

It hangs in the loop of while (line 560-564).

[chaoticlonghair]

Preliminaries

I use the max significant(highest) units (u64 in this example) of both dividend and divisor to predict the quotient.
(This is why my / and % are fast than others similar crates)

To insure remainder-part-of-full-dividend > ((divisor * quotient) << difference-of-digits), I do divisor -= 1.

Why it hangs

In this example, ((divisor * quotient) << difference-of-digits) is far small than remainder-part-of-full-dividend (borrow a u64 from the higher unit), so copy is far bigger than other, so it hangs in that loop.

rust-numext/constructor/src/fixed_uint/core/internal/private_ops.rs

Lines 560 to 564 in 1481b3d

	while copy >= *other {
	let (copy_new, _) = copy._sub(other);
	copy = copy_new;
	more += 1;
	}

So, the result will be right, but the computation will be very slow.

How to fix

It should not break the previous loop (estimate stage) too earlier, if borrow a higher unit (else part).

rust-numext/constructor/src/fixed_uint/core/internal/private_ops.rs

Lines 518 to 528 in 1481b3d

	let dividend = if lhs_highest >= divisor {
	lhs_highest
	} else {
	if ret_idx == 0 {
	break;
	}
	lhs_idx -= 1;
	ret_idx -= 1;
	(lhs_highest << #unit_bits_size)
	+ copy.inner()[lhs_idx] as #double_unit_suffix
	};