On 10/2/22 13:18, Qian Yun wrote:
For bigger inputs, I think current implementation is bad both ways: a) For sparse cases, simply chain the MxN terms together, sort and dedupe is O(N^2*log(N)) better than current O(N^3).
This way the time complexity is O(N^2*log(N^2)) -> O(2*N^2*log(N)), this is just the problem of merge N sorted list (each length is N), with "divide and conquer" (destructive in-place) merge sort (which is convenient for list), the time complexity is O(N^2*log(N)). We can implement it this way: Provide (and export) these 2 functions: add! : (%, %) -> % mul! : (%, %) -> % Which do addition and multiplication but may change the structure of its arguments. mul!(p, q) can be implemented as add!(mul!(p, first_half(q)), mul!(p, second_half(q))) which has the same "divide and conquer" spirit. - Qian -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" 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/fricas-devel/687e61cf-8ba5-fab9-5868-fa95acd3182d%40gmail.com.
