Changes between Version 23 and Version 24 of Ticket #17601


Ignore:
Timestamp:
08/18/15 17:35:40 (4 years ago)
Author:
dkrenn
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #17601 – Description

    v23 v24  
    11113*k/n + O(k^2^ / n^2^) with |k| <= n^(1/2)^.
    1212
    13 Of course, O(n) - O(n) = O(n) must hold.
     13Of course, O(n) - O(n) = O(n) must hold and we want to perform various arithmetic operations with these asymptotic expressions. Eventually, specified O-constants shall also be supported.
    1414
    15 Eventually, specified O-constants shall also be supported.
    16 
    17 The current plan is to implement the following classes (plus derivatives for more concrete situations). For simplicity, the corresponding parents are not listed here.
    18 
    19 
    20  !AsymptoticGrowthElement:: hold _one_ term, e.g. n^2^ or k/n or n*log(n). This can compare, multiply etc., but has **no** coefficient. Here, only the order of magnitude shall be managed.
    21 
    22  !AsymptoticTerm::
    23 
    24   holds one !AsymptoticGrowthElement, plus information on the coefficient or that it is an O-term etc.
    25 
    26  !AsymptoticExpression::
    27 
    28   represents the sum of several !AsymptoticTerms.
    29 
    30 The idea is to override !AsymptoticGrowthElement to obtain specific behaviour (as mentioned in our wishlist) because it seems unlikely to be able to handle everything in one class.
    31 For starters, there will be an !GrowthGroupPowerElement.
    32 
    33 !AsymptoticTerm is expected to be more general; it might be necessary to override it for the case of specified O-constants.
    34 
    35 !AsymptoticExpression, however, can be general enough to deal with all cases; here, the sum, the product, the exponential function, etc. are implemented in a generic setting.
    36 
     15See #17716 for more examples.
    3716-------
    3817
     
    4120
    4221* Implementing a minimal working example
    43     * #17600 (!AsymptoticGrowthElement): elements which handle the asymptotic growth. Concretely: !MonomialGrowthElement, implementation for powers.
     22    * #17600 (!AsymptoticGrowthElement): elements which handle the asymptotic growth. Such an element holds, e.g. n^2^ or k/n or n*log(n). This can compare, multiply etc., but has **no** coefficient; the order of magnitude is managed here. Concretely for this ticket: !MonomialGrowthElement, implementation for powers.
    4423    * #18930: Factory for user-friendly generation of growth groups
    45     * #17715 (!AsymptoticTerm): "building blocks" for asymptotic expressions, they contain the growth and additional information on the type of the term. For starters, there will be big-Oh terms and exact terms.
     24    * #17715 (!AsymptoticTerm): a summand for asymptotic expressions. They contain the growth and additional information on the type of the summand. For starters, there will be big-Oh terms (e.g. `O(n)` and exact terms (e.g. `3*n^2`).
    4625    * #17693 (!MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
    4726    * #17716 (!AsymptoticRing and !AsymptoticExpression): sum of asymptotic terms.
     
    5534    * Improve the performance of computations in the !AsymptoticRing.
    5635    * #19048: `AsymptoticRing.an_element()`
     36        * #19047: `QQ.some_elements()`
    5737
    5838* Extending the functionality of growth groups
     
    7151    * #18182: pushout construction and finding common parents for/including cartesian products
    7252    * #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
    73     * #19047: `QQ.some_elements()`