I am referring the given links for optimizing floating-point expressions
https://herbie.uwplse.org/ https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/02Numerics/Double/paper.pdf *T**o Do* - *1]* *databases of rules **to find rearrangements*(the database can be updated by user) - Including those for the commutativity, associativity, distributivity - Identity of basic arithmetic operators - Fraction arithmetic - Laws of squares, square roots, exponents, logarithms - Some basic facts of trigonometry - *2]* *sampling points* - These input points are sampled uniformly from the set of floating point bit patterns. - Each sampled point is a combination of a random mantissa, exponent, and a sign bit. - By sampling exponents uniformly, We can generate both very small and very large input points, as well as inputs of normal size - *3]* *error calculation* - STOKE: error = no_of_floating_point_values_between(approximate and exact_answer) - E(x, y) = log 2 |{z ∈ FP | min(x, y) ≤ z ≤ max(x, y)}| - mpmath can be used for this operation. - *4]* *localizing the error points and operators* - We use a greedy, hill-climbing search to tracks a set of candidate programs - apply rules at various locations in these candidates, evaluates each resulting program, and repeats the process on the best candidates. - For polynomial approximations, we can use sympy specialized series expansion pass to handle inaccuracies near 0 and ±∞ - *7] recursively solving the subparts* - Simplifying the equation - Replacing the expression using the different equations from the database. - Series expansion - recursively solving the candidate keys. - *5]* *finding operati**ons** with the highest error* - using srepr tree for getting subexpressions. - For each operation, we will average the local error for all sample points, - focuse its rewrites at the operations with the highest average - simplifying rewrites after every step. - *6]* *Updating** program Table* - keeping only those candidates that achieve the best accuracy on at least one sample point. - store the processed program - after adding the candidate it might happen that previously added are no longer best so they can also be removed from the table. - above mentioned paper suggests that in practice, running until the table reaches saturation does not give better results than running for 3 iterations. - *7] returning the split Piecewise expression for different ranges* - based on the sample points *Functions (refering the above mentioned lines), I want to implement the following functions for my GSOC project* Definition-main(program) : points := sample-inputs(program) exacts := evaluate-exact(program, points) table := make-candidate-table(simplify(program)) repeat N times candidate:= pick-candidate(table) locations := sort-by-local-error(all-locations(candidate)) locations.take(M ) rewritten := recursive-rewrite(candidate, locations) new-candidates := simplify-each(rewritten) table.add(new-candidates) approximated := series-expansion(candidate, locations) table.add(approximated) return infer-regimes(table).as-program - Definition local-error(expr, points) : for point ∈ points : args := evaluate-exact(expr.children) exact-ans := F(expr.operation.apply-exact(args)) approx-ans := expr.operation.apply-approx(F(args)) accumulate E(exact-ans, approx-ans) - Definition recursive-rewrite(expr, target) : select and where are non-deterministic choice and requirement select input output from RULES where input.head = expr.operator ∧ output.head = target.head for (subexpr, subpattern) ∈ zip(expr.children, input.children) : if ¬matches(subexpr, subpattern) : recursive-rewrite(subexpr, subpattern) where matches(expr, input) expr.rewrite(input -> output) - Definition simplify(expr) : iters := iters-needed(expr) egraph := make-egraph(expr) repeat iters times : for node ∈ egraph : for rule ∈ SIMPLIFY - RULES : attempt-apply(rule, node) return extract-smallest-tree(egraph) - Definition iters-needed(expr) : if is-leaf(expr) : return 0 else : sub-iters := map(iters-needed, expr.children) iters-at-node := if is-commutative(expr.head) then 2 else 1 return max(sub-iters) + iters-at-node - Definition infer-regimes(candidates, points) : for x i ∈ points : best-split 0 [x i ] = [regime(best-candidate(−∞, x i ), −∞, x i )] for n ∈ N until best-split n+1 = best-split n : for x i ∈ points ∪ {∞} : for x j ∈ points, x j < x i : extra-regime := regime(best-candidate(x j , x i ), x i , x j ) option[x j ] := best-split[x j ] ++ [extra-regime] best-split n+1 [x i ] := lowest-error(option) if best-split n [x i ].error − 1 ≤ best-split n+1 [x i ].error : best-split n+1 [x i ] := best-split n [x i ] split := best-split ∗ [∞] split.refine-by-binary-search() return split Please share your insights on this topic. -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/5f6d47be-bd92-4e18-a71a-c54dfeb3438a%40googlegroups.com.
