Opened 3 years ago

Closed 3 years ago

# Don't use Karatsuba for multiplying polynomials over fraction fields

Reported by: Owned by: mmezzarobba minor sage-8.3 basic arithmetic Marc Mezzarobba Bruno Grenet N/A c897ad5 c897ad5e74466c7a3fcc6fe69397ec8dd89c5d63

### Description

Before:

```sage: P.<x> = QQ[]
sage: Q.<y> = Frac(P)[]
sage: foo = ((-2*x^2 - 2*x + 3)/(x^2 + 1/3*x + 1/4))*y^20 + (-3/2/(-4/5*x^2))*y^19 + ((2/3*x + 4)/(1/8*x^2 - x - 1/7))*y^18 + ((1/16*x^2 + x - 1)/(-x^2 + 2*x - 5))*y^17 + ((
....: -5/716*x^2 - 1/4*x + 1/4)/(-1/2*x^2 + x - 1))*y^16 + ((-x^2 - 13*x)/(x^2 - 8*x - 2))*y^15 + ((x^2 + 4/5*x - 1)/(x^2 - 1/14*x + 1/145))*y^14 + ((-2*x^2 - 1/2*x - 1/2)/(
....: x^2 + x + 1))*y^13 + ((-x^2 + 14*x - 1)/(-6*x + 1/4))*y^12 + ((2*x^2 + 3*x - 2)/(-x^2 + 3*x - 2))*y^11 + ((-x + 1)/(1/4*x + 1/3))*y^10 + ((-1/8*x + 1/45)/(-x^2 - 1/4))
....: *y^9 + ((-9/11*x^2 - 2/7*x + 2/5)/(-4*x - 1))*y^8 + ((-x^2 + 1/2*x - 1)/(-x^2 + 7*x - 28))*y^7 + ((-3*x^2 + 2/25*x - 2)/(7*x^2 + 3/28*x))*y^6 + ((1/14*x^2 - x + 2/5)/(
....: -14*x^2 + 1/6))*y^5 + ((-3/2*x^2 + 3*x)/(1/43*x - 3))*y^4 + ((6*x^2 - 5*x + 1/27)/(1/20*x^2 + 3*x + 3))*y^3 + ((x^2 - 5*x - 4/5)/(2/5*x^2 - 2/9*x - 11/6))*y^2 + ((-1/1
....: 0*x^2 + x)/(-1/4*x^2 + 6*x - 1/2))*y + (43*x^2 + x + 1/3)/(-17/4*x - 6/7)
sage: %time _ = foo^4
CPU times: user 1.28 s, sys: 12 ms, total: 1.29 s
Wall time: 1.29 s
```

After:

```sage: %time _ = foo^4
CPU times: user 991 ms, sys: 0 ns, total: 991 ms
Wall time: 991 ms
```

### comment:1 Changed 3 years ago by mmezzarobba

• Status changed from new to needs_review

### comment:2 Changed 3 years ago by git

• Commit changed from 837d8cff12d69f086fdf57230637216d1b55a4bf to c6251c53b4b8f5fa7e9aac50db0a1f7de4292260

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​c6251c5 `don't use Karatsuba over fraction fields`

### comment:3 Changed 3 years ago by git

• Commit changed from c6251c53b4b8f5fa7e9aac50db0a1f7de4292260 to c897ad5e74466c7a3fcc6fe69397ec8dd89c5d63

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​c897ad5 `don't use Karatsuba over fraction fields`

### comment:4 follow-up: ↓ 5 Changed 3 years ago by bruno

Is it clear why it is a bad idea to use Karatusba's algorithm for polynomial over fraction fields? Since you test only one example, are you sure that this will always fasten the computation?

### comment:5 in reply to: ↑ 4 Changed 3 years ago by mmezzarobba

Is it clear why it is a bad idea to use Karatusba's algorithm for polynomial over fraction fields? Since you test only one example, are you sure that this will always fasten the computation?

My reasoning (cf. the commit message) was that Karatsuba's algorithm performs more additions in the base field, but additions in a fraction field are slower than multiplications—typically at least, I can't promise that this holds 100% of the time!

### comment:6 follow-up: ↓ 8 Changed 3 years ago by bruno

• Reviewers set to Bruno Grenet
• Status changed from needs_review to positive_review

I didn't read the full commit message, sorry! The argument makes sense, and my tests show that Karatsuba's algorithm indeed isn't a good idea for `FractionField`s. I haven't found (yet?) a case where Karatsuba's algorithm is faster...

Looks good to me!

### comment:7 follow-up: ↓ 9 Changed 3 years ago by alexjbest

Just a thought, how does extracting a common denominator, multiplying over the base integral domain (presumably with Karatsuba then), and putting the common denominators compare in general? That might be a useful approach for general fraction fields?

For comparison I get

```sage: P.<x> = QQ[]
....: Q.<y> = Frac(P)[]
....: foo = ((-2*x^2 - 2*x + 3)/(x^2 + 1/3*x + 1/4))*y^20 + (-3/2/(-4/5*x^2))*y^19 + ((2/3*x + 4)/(1/
....: 8*x^2 - x - 1/7))*y^18 + ((1/16*x^2 + x - 1)/(-x^2 + 2*x - 5))*y^17 + ((-5/716*x^2 - 1/4*x + 1/
....: 4)/(-1/2*x^2 + x - 1))*y^16 + ((-x^2 - 13*x)/(x^2 - 8*x - 2))*y^15 + ((x^2 + 4/5*x - 1)/(x^2 -
....: 1/14*x + 1/145))*y^14 + ((-2*x^2 - 1/2*x - 1/2)/(x^2 + x + 1))*y^13 + ((-x^2 + 14*x - 1)/(-6*x
....: + 1/4))*y^12 + ((2*x^2 + 3*x - 2)/(-x^2 + 3*x - 2))*y^11 + ((-x + 1)/(1/4*x + 1/3))*y^10 + ((-1
....: /8*x + 1/45)/(-x^2 - 1/4))*y^9 + ((-9/11*x^2 - 2/7*x + 2/5)/(-4*x - 1))*y^8 + ((-x^2 + 1/2*x -
....: 1)/(-x^2 + 7*x - 28))*y^7 + ((-3*x^2 + 2/25*x - 2)/(7*x^2 + 3/28*x))*y^6 + ((1/14*x^2 - x + 2/5
....: )/(-14*x^2 + 1/6))*y^5 + ((-3/2*x^2 + 3*x)/(1/43*x - 3))*y^4 + ((6*x^2 - 5*x + 1/27)/(1/20*x^2
....: + 3*x + 3))*y^3 + ((x^2 - 5*x - 4/5)/(2/5*x^2 - 2/9*x - 11/6))*y^2 + ((-1/10*x^2 + x)/(-1/4*x^2
....:  + 6*x - 1/2))*y + (43*x^2 + x + 1/3)/(-17/4*x - 6/7)
....:
sage: %time t = ((foo*foo.denominator())^4)/foo.denominator()^4
CPU times: user 451 ms, sys: 2.66 ms, total: 454 ms
Wall time: 463 ms
sage: %time t = foo^4
CPU times: user 1.79 s, sys: 15.7 ms, total: 1.81 s
Wall time: 1.84 s
```

I didn't try your non-karatsuba version on my laptop yet but given that the speedup is a factor of 4 in this example I believe it is better for this case at least. Maybe this is better on another ticket at any rate?

### comment:8 in reply to: ↑ 6 Changed 3 years ago by mmezzarobba

I didn't read the full commit message, sorry! The argument makes sense, and my tests show that Karatsuba's algorithm indeed isn't a good idea for `FractionField`s. I haven't found (yet?) a case where Karatsuba's algorithm is faster...

In fact, I forgot half of the explanation in my reply: it is no longer true for large degrees that Karatsuba's algorithm does more additions than the naive algorithm, but we'd have to take into account coefficient growth (for both methods) to make a meaningful comparison, and at least the naive method still seems better for example that take several seconds.