]> gitweb.factorcode.org Git - factor.git/commit
math.integers, bignum/f, improve performance.
authorJon Harper <jon.harper87@gmail.com>
Sun, 26 Jul 2015 16:07:10 +0000 (18:07 +0200)
committerJohn Benediktsson <mrjbq7@gmail.com>
Sun, 26 Jul 2015 19:33:55 +0000 (12:33 -0700)
commit5424ad5586cb2eaac8de5bea6b75edb012ac556b
treeaa010d03c30d4ca1c23074399fc3d8c8ab71bd0b
parentcc6d90a096d79bef6f106d80b04339b2596f7e26
math.integers, bignum/f, improve performance.

This changes avoids looping many times if the denominator is a power of
2. After this change, the implementation matches the linked sbcl
algorithm.  This was probably a mistake done when porting the algorithm.
Basically, as an optimization, all trailing zeros are removed from the
base2 representation of the denominator to have smaller bignums to
divide. But the previous factor implementation didn't take this into
account when making the initial guess of the shift of the numerator to
obtain a result in the range [2^54-1,2^53]. The loop would then correct
the initial guess by a factor of 2 at each iteration, so it would run as
many iteration as the denominator base2 power reduction, instead of only
a few times. For pathological cases, the speed up is huge (10^4):
1 1000 2^ bignum/f
core/math/integers/integers.factor