Changeset 31951 in project
 Timestamp:
 12/05/14 22:38:22 (5 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/eggref/4/numbers
r31909 r31951 217 217 === Version history 218 218 219 ; trunk: Convert internal digit representation to use full words. Improve performance by accessing halfdigits directly. Improve performance of number<>string conversions for radixes that are a power of two by directly operating on digits, avoiding inplace shifts. 219 ; trunk: Convert internal digit representation to use full words. Improve performance by accessing halfdigits directly. Improve performance of number<>string conversions for radixes that are a power of two by directly operating on digits, avoiding inplace shifts. Improve performance of number>string by using a divide and conquer algorithm. Implement Burnikel&Ziegler recursive division which is O(r*s^{log(3)1} + r*log(s)) instead of {{O(n^2)}} (this is mostly useful for very large numbers due to high constant overhead). 220 220 ; 3.1: Improve performance of string<>number conversions by chunking bignum digits off instead of using a binary digit at a time. Use a faster and shorter division algorithm from Hacker's Delight. Implement Lehmer's hybrid Euclidian GCD algorithm which is O(n^2/log n) instead of O(n^2) like Euclid and Stein's algorithms. Implement Karatsuba multiplication which is O(n^log2(3)) instead of O(n^2), but is only effective for larger bignums. Make a few more things inlineable. Fix stupid mistake which caused exact operations involving rational numbers to be needlessly slow. Improve performance for string<>number conversion using radix powers of two, and for multiplication of bignums with small powers of two. 221 221 ; 3.0.1: Fix quotient&remainder and derived procedures for 2 bignum arguments (it returned only the remainder). Fix crash bug in flonum comparison.
Note: See TracChangeset
for help on using the changeset viewer.