This commit speeds up Context.Quo, replacing its per-digit long
division with a call to BigInt.QuoRem. This avoids per-digit
iteration. It also allows Context.Quo to benefit further from the
inline fast-path of BigInt.QuoRem for small coefficient values that
fit in a uint64.
This is a partial revert of 1eddda3, at least in spirit. Before that
commit, Context.Quo did try to use big.Int.Quo. Unfortunately, it
was inaccurate for certain values because it was not scaling the
coefficients correctly before dividing. It tried to compensate for this
by using a very large precision (c.Precision*2 + 8), but this was
insufficient on its own because it was not taking the size of the values
into account. So the commit abandoned that approach.
However, that commit, which was based on the description given on the
GDA site, did demonstrate how to scale the coefficients in a way that
would permit this kind of division. Specifically, it began adjusting the
operands so that the coefficient of the dividend was greater than or
equal to the coefficient of the divisor and was also less than ten times
the coefficient of the divisor.
This commit uses the coefficient adjustment introduced in 1eddda3 to
revive the call into BigInt.QuoRem. With the two operands adjusted, it
now is possible to scale the coefficient of the dividend by the desired
precision and then perform a direct division on the operands.
cockroach-teamcity
commented
2 years ago 
Fixes #98.
This commit speeds up
Context.Quo, replacing its per-digit long division with a call toBigInt.QuoRem. This avoids per-digit iteration. It also allowsContext.Quoto benefit further from the inline fast-path ofBigInt.QuoRemfor small coefficient values that fit in a uint64.This is a partial revert of 1eddda3, at least in spirit. Before that commit,
Context.Quodid try to usebig.Int.Quo. Unfortunately, it was inaccurate for certain values because it was not scaling the coefficients correctly before dividing. It tried to compensate for this by using a very large precision (c.Precision*2 + 8), but this was insufficient on its own because it was not taking the size of the values into account. So the commit abandoned that approach.However, that commit, which was based on the description given on the GDA site, did demonstrate how to scale the coefficients in a way that would permit this kind of division. Specifically, it began adjusting the operands so that the coefficient of the dividend was greater than or equal to the coefficient of the divisor and was also less than ten times the coefficient of the divisor.
This commit uses the coefficient adjustment introduced in 1eddda3 to revive the call into
BigInt.QuoRem. With the two operands adjusted, it now is possible to scale the coefficient of the dividend by the desired precision and then perform a direct division on the operands.Microbenchmarks
From the benchmark referenced in #98:
The reported results were:
After #103 and this PR, they are now: