Ticket #10255 (needs_review defect)
Correct karatsuba multiplication of univariate polynomials for different degree polynomials
|Reported by:||lftabera||Owned by:||AlexGhitza|
|Component:||basic arithmetic||Keywords:||karatsuba, multiplication, polynomial|
|Authors:||Luis Felipe Tabera Alonso||Merged in:|
Description (last modified by lftabera) (diff)
In the generic implementation of univariate polynomials over exact rings, plain karatsuba is used.
However, for different degree polynomials, the karatsuba code makes more products and additions than the classical multiplication code. Moreover, for equally sized polynomials, the degree in which karatsuba starts to be better than plain multiplication looks too high for me.
See attachments comparison_product_50_400.png and comparison_addition_50_400.png for the number of operations multiplying degree 50 and 400 polynomials, in yellow, the number of operations using _mul_generic, in red using current _mul_karatsuba as of 4.6.1 and in blue with the patch proposed.
sage: K=QQ[I][x] sage: f=K.random_element(1500) sage: g=K.random_element(1500) sage: %time _ = f._mul_generic(g) CPU times: user 6.03 s, sys: 0.08 s, total: 6.11 s Wall time: 6.43 s sage: %time _ = f._mul_karatsuba(g) CPU times: user 6.95 s, sys: 0.06 s, total: 7.01 s Wall time: 7.76 s
See comment:13 for some benchmarks
comment:18 Changed 2 years ago by lftabera
- Status changed from new to needs_review
- Authors set to Luis Felipe Tabera Alonso
comment:20 Changed 3 months ago by lftabera
- Type changed from enhancement to defect
- Description modified (diff)
- Summary changed from improve karatsuba multiplication of univariate polynomials to Correct karatsuba multiplication of univariate polynomials for different degree polynomials