Changes between Initial Version and Version 1 of Ticket #1216, comment 2
 Timestamp:
 Mar 4, 2014 11:39:09 PM (7 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #1216, comment 2
initial v1 4 4 {{{ 5 5 Changes between GMP version 5.1.* and 5.2.0 6 * Plain division of large operands is faster and more monotonous in operand 7 size. 6 8 * Speedup for Intel Sandy Bridge, Ivy Bridge, Haswell, thanks to rewritten 7 9 and vastly expanded assembly support. … … 37 39 addition of many new Toom function, and by selecting underlying 38 40 functions better from the main multiply functions. 41 * Division and mod have been overhauled: 42 (1) Plain "schoolbook" division is reimplemented using faster quotient 43 approximation. 44 (2) Division Q = N/D, R = N mod D where both the quotient and remainder 45 are needed now runs in time O(M(log(N))). This is an improvement of 46 a factor log(log(N)) 47 (3) Division where just the quotient is needed is now O(M(log(Q))) on 48 average. 49 (4) Modulo operations using Montgomery REDC form now take time O(M(n)). 50 (5) Exact division Q = N/D by means of mpz_divexact has been improved 51 for all sizes, and now runs in time O(M(log(N))). 52 39 53 * The function mpz_powm is now faster for all sizes. Its complexity has 40 54 gone from O(M(n)log(n)m) to O(M(n)m) where n is the size of the modulo … … 43 57 and performs two smaller modexp operations, then uses CRT. 44 58 }}} 59 60 Perhaps multiplication/division improvements since you last tried them (which GMP version? the one we ship? 32bit or 64bit?) have improved to the point they could be useful?