Changes between Initial Version and Version 1 of Ticket #1216, comment 2


Ignore:
Timestamp:
Mar 4, 2014 11:39:09 PM (7 years ago)
Author:
dg
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #1216, comment 2

    initial v1  
    44{{{
    55Changes between GMP version 5.1.* and 5.2.0
     6  * Plain division of large operands is faster and more monotonous in operand
     7    size.
    68  * Speedup for Intel Sandy Bridge, Ivy Bridge, Haswell, thanks to rewritten
    79    and vastly expanded assembly support.
     
    3739        addition of many new Toom function, and by selecting underlying
    3840        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
    3953  * The function mpz_powm is now faster for all sizes.  Its complexity has
    4054    gone from O(M(n)log(n)m) to O(M(n)m) where n is the size of the modulo
     
    4357    and performs two smaller modexp operations, then uses CRT.
    4458}}}
     59
     60Perhaps 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?