4 ms·
Is there a reason compilers don't just use modular inverses and let overflow take care of things? 19 * 678,152,731 = 1 (mod 2^32) 19 * 9,708,812,670,373,448,2
by xelxebar 10y ago
Is there a reason compilers don't just use modular inverses and let overflow take care of things?
19 * 678,152,731 = 1 (mod 2^32)
19 * 9,708,812,670,373,448,219 = 1 (mod 2^64)
As long as we already know the size of an int Euclid's algorithm should be able to find these inverses if they exist.
- jwilk 10y agoI don't see how finding the modular inverse helps with division. What algorithm do you have in mind?
- SamReidHughes 10y agoThat only works when the value is known to be a multiple of whatever you're dividing by, and they do use that when it is the case, such as for pointer subtraction.