On Thursday, March 12, 2015 at 3:05:28 AM UTC+1, Shivam Vats wrote: > > Hi Ondrej > > I tried to compare a naive implementation of Knonecker in Python with what > Karatsuba that > Sympy currently uses for multiplication. I have modified pernici's code > for Kronecker. > > https://github.com/shivamvats/sympy/commit/99b1fa5fecccb7a46b19d0863b4e8f3315f555da > > ``` > res = 2*x+1 > t1 = clock() > for i in range(1000): > res = R.dup_pack_mul(2*x+1, res) > t2 = clock() > print(t2-t1) > > 31.3395597935 > ``` > > ```res = 2*x+1 > t1 = clock() > for i in range(1000): > res = R.dup_mul(2*x+1, res) > t2 = clock() > print(t2-t1) > > 6.16460609436 > ``` > > Karatsuba, and even normal multiplication is faster than Kronecker by a > large factor. > The main reason is of course, that we should use a fast library for the > integer multiplication. > Moreover, how much padding needs to be done, is also not a trivial > question. >
The integer multiplication could be an issue, but on top of that the packing and unpacking is done with O(n^2) complexity. Fredrik -- 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 post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/5a1a0ac2-2c3c-4351-a217-ba55c1534694%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
