AbstractAlgebra.jl
AbstractAlgebra.jl copied to clipboard
Nemocas
Implement crossovers for mul_karatsuba and mul_KS and make multiplication use them in appropriate characteristics
Does AbstractAlgebra support non-classical poly mul? Looking at the code, there is mul_karastuba - but as it is non-recursive, it is not really asymptotically fast.
Then there is mul_ks which similarly is also not recursive.
I'd like to multiply smallish degree polynomials over extremely expensive coefficients. Clearly, that cannot be done automatically, but I wonder if this is (currently) supported at all.
Similarly, it would be good if power series could also use fast multiplications...
Those were basically set up so that if * ever used other methods, they would call back into *. You need crossovers somewhere, but these depend on the ring.
What you have found is all there is.
Here is some benchmark code for comparing the speed of mul_classical and mul_ks in the case of BigInt coeffs, by length and bits:
function legend(cutoff::Int)
bits = 1; i = 1; print(" ")
while bits < cutoff
if iseven(i)
print(" "^(6-ndigits(bits, base=10)))
print(bits)
end
i += 1
bits = Int(round(bits*1.2)) + 1
end
println(""); print(" ")
bits = 1; i = 1;
while bits < cutoff
if isodd(i)
print(" "^(6-ndigits(bits, base=10)))
print(bits)
end
i += 1
bits = Int(round(bits*1.2)) + 1
end
println("")
end
function polytime(R::AbstractAlgebra.Ring, cutoff::Int)
# warm up jit
for i = -1:5
f = rand(R, i, -10:10)
g = rand(R, i, -10:10)
h = mul_classical(f, g)
k = mul_karatsuba(f, g)
end
println("1 = classical is better, 2 = karatsuba is better")
println("horizontal axis = bits, vertical axis = length")
legend(cutoff)
len = 1
while len < 2000
bits = 1
print(" "^(4-ndigits(len, base=10))); print(len, ": ")
while bits < cutoff && len*bits < 60000
f = R([rand(ZZ(2)^(bits-1):ZZ(2)^bits-1) for j in 1:len])
g = R([rand(ZZ(2)^(bits-1):ZZ(2)^bits-1) for j in 1:len])
t1 = time_ns(); mul_classical(f, g); t1 = time_ns() - t1
t2 = time_ns(); mul_karatsuba(f, g); t2 = time_ns() - t2
if t1 > t2*1.2
print(" 2 ")
elseif t2 > t1*1.2
print(" 1 ")
else
print(" ")
end
bits = Int(round(bits*1.2) + 1)
end
println("")
len = Int(round(len*1.2) + 1)
end
end
The results seem to indicate that mul_ks is better for lengths > 175, regardless of bitsize.
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55 81 119 174 253 367 530 765 1104
1 3 7 12 19 30 45 67 98 144 210 305 441 637 919
1: 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
7: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
9: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
12: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
19: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
24: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
30: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
37: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
45: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
55: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
67: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
81: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
98: 1
119: 2 1 1 1 2
144: 1 1
174: 2
210:
253: 2 2 1 2 2
305: 2 2 2
367: 2 2 2 2 2 2
441: 2 2 2 2 2 2 2 2 2 2
530: 2 2 2 2 2 2 2 2 2 2 2 2
637: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
765: 2 2 2 2 2 2 2 2 2 2 2 2 2 2
919: 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1104: 2 2 2 2 2 2 2 2 2 2 1 2
1326: 2 2 2 2 2 2 2 2 2 2 2 2 2
1592: 2 2 2 2 2 2 2 2 2 2 2 2
1911: 2 2 2 2 2 2 2 2 2 2
Here is the same chart transposed, for lengths up to 100, but much bigger bit sizes, suggesting in this range karatsuba is better when bits*length > 30000:
1 = classical is better, 2 = karatsuba is better
horizontal axis = length, vertical axis = bits
2 5 9 15 24 37 55 81
1 3 7 12 19 30 45 67 98
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
7: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
9: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
12: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
19: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
24: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
30: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
37: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
45: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
55: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
67: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
81: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
98: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
119: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
144: 1 1 1 1 1 1 1 1 1 1 1 1 1
174: 1 1 1 1 1 1 1 1 1 1 1 1 1 1
210: 1 1 1 1 1 1 1 1 1 1 1 1
253: 1 1 1 1 1 1 1 1 1 1 1 1 1
305: 1 1 1 1 1 1 1 1 1 1 1 1 1 1
367: 1 1 1 1 1 1 1 1 1 1 1 1
441: 1 1 1 1 1 1 1 1 1 1
530: 1 1 1 1 1 1 1 1 1 1 2
637: 1 1 1 1 1 1 1 1 1 1 2
765: 1 1 1 1 1 1 1 1 1 1 2
919: 1 1 1 1 1 1 1 1 1 1 2
1104: 1 1 1 1 1 1 2 2 2
1326: 1 1 1 1 1 2 2 2 2
1592: 1 1 1 1 1 2 2 2 2 2 2
1911: 1 1 1 1 1 2 2 2 2 2 2
2294: 1 1 1 1 1 1 2 2 2 2 2 2 2
2754: 1 1 1 1 2 2 2 2 2 2 2 2
3306: 1 1 1 2 2 2 2 2 2 2 2
3968: 1 1 2 2 2 2 2 2 2 2
4763: 1 2 2 2 2 2 2 2 2 2
5717: 1 1 2 2 2 2 2 2 2
6861: 2 1 1 2 2 2 2 2 2 2 2 2
8234: 2 2 2 2 2 2 2 2 2 2 2 2
9882: 2 1 2 2 2 2 2 2 2 2 2 2
11859: 2 2 2 2 2 2 2 2 2 2
14232: 2 2 2 2 2 2 2 2 2 2 2
17079: 2 2 2 2 2 2 2 2 2 2
Here is the code:
function polytime(R::AbstractAlgebra.Ring, cutoff::Int)
# warm up jit
for i = -1:5
f = rand(R, i, -10:10)
g = rand(R, i, -10:10)
h = mul_classical(f, g)
k = mul_karatsuba(f, g)
end
println("1 = classical is better, 2 = karatsuba is better")
println("horizontal axis = length, vertical axis = bits")
legend(cutoff)
bits = 1
while bits < 20000
len = 1
print(" "^(5-ndigits(bits, base=10))); print(bits, ": ")
while len < cutoff
f = R([rand(ZZ(2)^(bits-1):ZZ(2)^bits-1) for j in 1:len])
g = R([rand(ZZ(2)^(bits-1):ZZ(2)^bits-1) for j in 1:len])
t1 = time_ns(); mul_classical(f, g); t1 = time_ns() - t1
t2 = time_ns(); mul_karatsuba(f, g); t2 = time_ns() - t2
if t1 > t2*1.2
print(" 2 ")
elseif t2 > t1*1.2
print(" 1 ")
else
print(" ")
end
len = Int(round(len*1.2) + 1)
end
println("")
bits = Int(round(bits*1.2) + 1)
end
end
Over QQ it looks like the cutoff should be about length > 17:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55 81 119 174 253 367 530 765 1104
1 3 7 12 19 30 45 67 98 144 210 305 441 637 919
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1
5: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
7: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
9: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1
12: 1 1 1 2 2
15: 1
19: 1 2 2
24: 2 2 2 2 2 2 2 2
30: 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2
37: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
45: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
55: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2
67: 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2
81: 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 1 2
98: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
119: 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2
144: 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 1 2 1 2 2 2
174: 2 2 2 1 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2
210: 2 2 2 1 2 1 2 1 2 2 2 2 1 2 1 2 2 1 2 1 2
253: 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 2 2
305: 2 1 1 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2
367: 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2
441: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
530: 2 2 2 2 2 2 2 2 2 2
637: 2 2 2 2 2
765: 2 2 2 2 2 2 2 2 2 2 2 2 2 2
919: 2 2 2 2 2 2 2 2 2 2 2 2 2
1104: 2 2 2 2 2 2 2 2 2 2 2 2 2
1326: 2 2 2 2 2 2 2 2 2 2 2 2 2
1592: 2 2 2 2 2 2 2 2 2 2 2 2
1911: 2 2 2 2 2 2 2 2 2 2
Or bits*len^1.7 > 48500:
1 = classical is better, 2 = karatsuba is better
horizontal axis = length, vertical axis = bits
2 5 9 15
1 3 7 12
1: 1 1 1 1 1 1
2: 1 1 1 1 1 1
3: 1 1 1 1 1 1
5: 1 1 1 1 1 1
7: 1 1 1 1 1 1
9: 1 1 1 1 1 1 1
12: 1 1 1 1 1 1
15: 1 1 1 1 1 1
19: 1 1 1 1 1 1
24: 1 1 1 1 1 1 1
30: 1 1 1 1 1 1 2
37: 1 1 1 1 1 1
45: 1 1 1 1 1 1
55: 1 1 1 1 1 1
67: 1 1 1 1 1 1
81: 1 1 1 1 1 1 2
98: 1 1 1 1 1 1
119: 1 1 1 1 1 1
144: 1 1 1 1 1 2
174: 1 1 1 1 1
210: 1 1 1 1 1 1
253: 1 1 1 1 1
305: 1 1 1 1 1 1
367: 1 1 1 1 2
441: 1 1 1 1 1 1
530: 1 1 1 1 1 2
637: 1 1 1 1 1
765: 1 1 1 1 1
919: 1 1 1 1 2 1 2
1104: 1 1 1 1 2
1326: 1 1 1 1 1 1 2
1592: 1 1 1 1 2 2
1911: 1 1 1 1 2
2294: 1 1 1 1
2754: 1 2 2
3306: 1 1 2
3968: 1 1
4763: 1 2
5717: 1 1 2 2
6861: 1 2
8234: 1 2 2
9882: 1
11859: 2 2
14232: 2 2
17079: 1 2 2 2
20496: 2 2 2 2
24596: 2 2 1
29516: 2 2 2 2 2 2 2
35420: 2 2 2 2 2
For GF(p) a cutoff of length > 75 should work regardless of bits:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1: 1 1 1 1 1 1 1 1 1 1 1 1 1
2: 1 1 1 1 1 1 1 1 1 1 1 1 1
3: 1 1 1 1 1 1 1 1 1 1 1 1 1
5: 1 1 1 1 1 1 1 1 1 1 1 1 1
7: 1 1 1 1 1 1 1 1 1 1 1 1 1
9: 1 1 1 1 1 1 1 1 1 1 1 1 1
12: 1 1 1 1 1 1 1 1 1 1 1 1 1
15: 1 1 1 1 1 1 1 1 1 1 1 1 1
19: 1 1 1 1 1 1 1 1 1 1 1 1 1
24: 1 1 1 1 1 1 1 1 1 1 1 1
30: 1 1 1 1 1 1 1 1 1 1 1
37: 1 1 1 1 1 1 1 1 1 1 1
45: 1 1 1 1 1 1 1 1
55: 1
67:
81: 2
98: 2 1 2
119: 2 2 1
144: 2 2
174: 2 2 2 2 2
210: 2 2 2 2
253: 2 2 2 2 2 2 2 2 2 2 2 2
305: 2 2 2 2 2 2 2 2 2 2 2 2 2
367: 2 2 2 2 2 2 2 2 2 2 2 2 2
441: 2 2 2 2 2 2 2 2 2 2 2 2 2
530: 2 2 2 2 2 2 2 2 2 2 2 2 2
637: 2 2 2 2 2 2 2 2 2 2 2 2
765: 2 2 2 2 2 2 2 2 2 2 2 2 2
919: 2 2 2 2 2 2 2 2 2 2 2 2 2
1104: 2 2 2 2 2 2 2 2 2 2 2 2 2
1326: 2 2 2 2 2 2 2 2 2 2 2 2 2
1592: 2 2 2 2 2 2 2 2 2 2 2 2 2
1911: 2 2 2 2 2 2 2 2 2 2 2 2
Here is the code:
function polytime()
# warm up jit
for i = 2:5
n = rand(2^(i-1):2^i-1); while !AbstractAlgebra.isprobable_prime(n) n = rand(2^(i-1):2^i-1) end
R = PolyRing(GF(n))
f = AbstractAlgebra.rand(R, i:i)
g = AbstractAlgebra.rand(R, i:i)
h = mul_classical(f, g)
k = mul_karatsuba(f, g)
end
println("1 = classical is better, 2 = karatsuba is better")
println("horizontal axis = bits, vertical axis = length")
legend(64)
len = 1
while len < 2000
bits = 2
print(" "^(4-ndigits(len, base=10))); print(len, ": ")
while bits < 64
n = rand(2^(bits-1):2^bits-1); while !AbstractAlgebra.isprobable_prime(n) n = rand(2^(bits-1):2^bits-1) end
R = PolyRing(GF(n))
f = AbstractAlgebra.rand(R, len-1:len-1)
g = AbstractAlgebra.rand(R, len-1:len-1)
t1 = time_ns(); mul_classical(f, g); t1 = time_ns() - t1
t2 = time_ns(); mul_karatsuba(f, g); t2 = time_ns() - t2
if t1 > t2*1.2
print(" 2 ")
elseif t2 > t1*1.2
print(" 1 ")
else
print(" ")
end
bits = Int(round(bits*1.2) + 1)
end
println("")
len = Int(round(len*1.2) + 1)
end
end
For GF(ZZ(p)) we can probably take length^2*bits > 2000:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55 81 119 174 253 367 530 765 1104 1592
1 3 7 12 19 30 45 67 98 144 210 305 441 637 919 1326 1911
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1
2: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
7: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
9: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
12: 1 1 1 1 2 2 2 2
15: 1 1 1 1 1 1 2
19: 1 1 2 2 2
24: 1 2 2 2 2 2 2 2 2 2
30: 1 2 2 2 2 2 2 2 2
37: 1 2 2 2 2 2 2 2 2
45: 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1
55: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
67: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
81: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2
98: 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 1 2
119: 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 1 2 2 2
144: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 1 2 2 1
174: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2
210: 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 1 2 1 1 2 1 2
253: 2 2 1 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2
305: 2 2 1 2 1 2 1 2 1 2 1 2 1 2 2 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2
367: 2 2 2 2 1 2 2 2 2 1 2 2 2 2 2 1 2 2 2 1 2 2 1 2 2 2 2 2 2 2
441: 1 2 2 2 2 1 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2
530: 2 2 1 2 1 2 1 2 1 2 1 2 1 2 2 1 1 1 2 2 2 2 2 2 2 2 2 2 2
637: 2 2 1 1 2 2 2 1 1 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2
765: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
919: 1 1 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Code:
function polytime(cutoff::Int)
# warm up jit
for i = 2:5
n = rand(ZZ(2)^(i-1):ZZ(2)^i-1); while !AbstractAlgebra.isprobable_prime(n) n = rand(ZZ(2)^(i-1):ZZ(2)^i-1) end
R = PolyRing(GF(n))
f = AbstractAlgebra.rand(R, i:i)
g = AbstractAlgebra.rand(R, i:i)
h = mul_classical(f, g)
k = mul_karatsuba(f, g)
end
println("1 = classical is better, 2 = karatsuba is better")
println("horizontal axis = bits, vertical axis = length")
legend(cutoff)
len = 1
while len < 1000
bits = 2
print(" "^(4-ndigits(len, base=10))); print(len, ": ")
while bits < cutoff
n = rand(ZZ(2)^(bits-1):ZZ(2)^bits-1); while !AbstractAlgebra.isprobable_prime(n) n = rand(ZZ(2)^(bits-1):ZZ(2)^bits-1) end
R = PolyRing(GF(n))
f = AbstractAlgebra.rand(R, len-1:len-1)
g = AbstractAlgebra.rand(R, len-1:len-1)
t1 = time_ns(); mul_classical(f, g); t1 = time_ns() - t1
t2 = time_ns(); mul_karatsuba(f, g); t2 = time_ns() - t2
if t1 > t2*1.2
print(" 2 ")
elseif t2 > t1*1.2
print(" 1 ")
else
print(" ")
end
bits = Int(round(bits*1.2) + 1)
end
println("")
len = Int(round(len*1.2) + 1)
end
end
For a ResidueRing over a QQ polynomial of degree 2 (number field):
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1: 1
2: 2
3: 1 1 2 1 1 1 1 1 1
5:
7: 2
9: 2 2
12: 2 2 2 2 2 2
15: 2 2 2 1 2 2
19: 2 2 2 2 2 1 2 1
24: 2 2 2 2 2 2 1 2 2 2 1
30: 1 2 2 2 2 1 2 2 2
37: 2 2 1 2 2 2 2 1 2 1 2
45: 2 2 1 1 1 2 2 2 2 2 2
55: 1 2 2 1 2 2 1 2 1 2 2 1
67: 2
81: 2 2 2 2 2 2 2 1 2
98: 2 2 2 2 2 2
Degree 3:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1:
2: 2
3: 1 1 1 1 1 1
5:
7: 2 2
9: 2 2 2
12: 2 2 2 2 1 2 2 2
15: 2 1 2 2 2
19: 1 2 2 2 2 2 2 1
24: 2 2 2 2 2 2 2 2 1
30: 2 1 2 2 1 1 2 2 2 1 1 2
37: 2 1 1 1 2 2 2 2 1 2 2 1 2
45: 2 1 2 2 1 2 2 2 2
55: 2 2 2 2 2 1
67: 2 1 2 2 2 2 2
81: 2 2 2 2 2 2
98: 2 2 2 2 2
Degree 5:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1:
2: 2 2 2 2 2 2
3: 1 1 1 1 1
5: 1
7: 2 2 1 2
9: 2 1 2 1 2 1 2
12: 2 2 2 1 1 2 1
15: 2 2 1 2 1 2 1 1 2
19: 1 2 2 1 2 2 1 1 2 2 2 2
24: 2 2 2 2 1 1 2 2 2 2
30: 2 2 2 2 1
37: 2 2 2 2 2 1
45: 2 2 2 2
55: 2 2 2 2 2
67: 2 2 2
81: 2 2 2
98: 2 2 2 2 2
So, I propose we have a generic fallback crossover of length > 5.
Here is the code (where K is polynomial ring over Generic residue field over polynomial ring over Q, i.e. poly over number field):
function polytime(K, cutoff::Int)
# warm up jit
for i = 2:5
f = AbstractAlgebra.rand(K, i:i, -10:10)
g = AbstractAlgebra.rand(K, i:i, -10:10)
h = mul_classical(f, g)
k = mul_karatsuba(f, g)
end
println("1 = classical is better, 2 = karatsuba is better")
println("horizontal axis = bits, vertical axis = length")
legend(cutoff)
len = 1
while len < 100
bits = 2
print(" "^(4-ndigits(len, base=10))); print(len, ": ")
while bits < cutoff
f = AbstractAlgebra.rand(K, len-1:len-1, -2^bits:2^bits)
g = AbstractAlgebra.rand(K, len-1:len-1, -2^bits:2^bits)
t1 = time_ns(); mul_classical(f, g); t1 = time_ns() - t1
t2 = time_ns(); mul_karatsuba(f, g); t2 = time_ns() - t2
if t1 > t2*1.2
print(" 2 ")
elseif t2 > t1*1.2
print(" 1 ")
else
print(" ")
end
bits = Int(round(bits*1.2) + 1)
end
println("")
len = Int(round(len*1.2) + 1)
end
end
Now for some Nemo timings.
Firstly a degree 2 number field:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1: 1 1 1 1 2 2 2 2 2 2
2: 1 1 1 1 1 1 1 1 1 1 1 1
3: 1 1 1 1 1 1 1 1 1 1 1 1 1
5: 1 1 1 1 1 1 1 1 1 1 1 1 1
7: 1 1 1 1 1 1 1 1 1
9: 1 1 1 1 1 1
12: 2 2
15: 1 2
19: 2
24: 2 2 2
30: 2 2 2 2 2 2 2 2 2
37: 2 2 2 2 2 2 2 2 2
45: 2 2 2 2 2 2 1 2
55: 2 2 2 2 2 2 2 2 2
67: 2 2 2 2 2 2 2 2 2 2 2
81: 2 2 2 2 2 2 2 2 2 2 2 2 2
98: 2 2 2 2 2 2 2 2 2 2 2 2 2
Degree 3:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1: 1 1 1 2 2 2 2 2 2
2: 1 1 1 1 1 1 1 1 1 1
3: 1 1 1 1 1 1 1 1 1 1 1 1 1
5: 1 1 1 1 1 1 1 1 1 1 1 1
7: 1 1 1 1 1 1 1 1 1 1
9: 1 1 1 1 1
12:
15: 2
19: 2
24: 2 2 2 2 2
30: 1 2 2 2 2 2 2 2
37: 2 2 2 2 2 2 2 2
45: 2 2 2 2 2 2 2 2 2
55: 2 2 2 2 2 2 2 2 2
67: 2 2 2 2 2 2 2 2 2 2 2
81: 2 2 2 2 2 2 2 2 2 2 2 2 2
98: 2 2 2 2 2 2 2 2 2 2 2 2 2
Degree 5:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1: 1 1 2 2 2 2 2 2 2 2 2
2: 1 1 1 1 1 1
3: 1 1 1 1 1 1 1 1 1 1 1 1 1
5: 1 1 1 1 1 1 1 1 1 1 1
7: 1 1 1 1 1 1 1 1 1
9: 1 1 1
12: 2
15: 2 1 1
19: 1 2 2 2 2
24: 2 2 2 2 2 2 2
30: 1 2 2 2 2 2 1 2 2 2 2
37: 2 2 2 2 2 2 2
45: 2 2 2 2 2 2 2 2 2
55: 2 2 2 2 2 2 2 2 2 2
67: 1 2 2 2 2 2 2 2 2 2 2
81: 2 2 2 2 2 2 2 2 2 2 2 2
98: 2 2 2 2 2 2 2 2 2 2 2 2 2
Degree 10:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1: 1 2 2 2 2 2 2
2: 1 1 1 1
3: 1 1 1 1 1 1 1 1 1 1 1
5: 1 1 1 1 1 1 1 1
7: 1 1 1 1 1 1 1
9: 1 1
12: 1 1 2
15: 1 1 2
19: 2 1 2 2
24: 2 2 2 2
30: 2 2 2 2 2 2 2
37: 2 2 2 1 2 2 2 2 2
45: 2 2 2 2 2 2 2 2 2 2 2 2
55: 1 2 2 2 2 2 2 2 2
67: 2 2 1 2 2 2 2 2 2 2
81: 2 2 2 2 2 2 2 2 2 2 2 2 2
98: 2 2 2 2 2 2 2 2 2 2 2 2 2
Degree 20:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1: 2 2 2 2 2 2 2 2 2 2 2
2: 1 1 2
3: 1 1 1 1 2 1 1
5: 1 1 1
7: 1 1 1 1 1 2
9: 1 1 2
12: 2 1 2 2
15: 1 2 2 2 2
19: 2 1 2 2 2 2
24: 2 2 2 2 2 2 2
30: 1 1 2 2 2 2 2
37: 2 1 2 2 2 2 2 2 2
45: 2 2 1 2 2 2 2 2 2
55: 1 2 2 2 2 2 2 2 2 2 2
67: 2 2 2 2 2 2 2 2 2 2 2
81: 2 2 2 2 2 2 2 2 2
98: 2 2 2 2 2 2 2 2 2 2 2 2
Degree 30:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1: 2 2 2 2 2 2 2 2 2 2 2
2: 2 2 2 2 2 2 2 2 2 2 2
3: 1 1 1 1 1
5: 1 1 1 2 1 2 2 1
7: 1 2
9: 2 2
12: 2 2 2 2 2 2 2
15: 2 2 2 2
19: 1 2 2 2 2 2 2
24: 1 2 2 2 2 2
30: 1 2 2 2 2 2 2 2
37: 2 2 2 2 2 2 2 2
45: 2 2 2 2 2 2 2 2
55: 2 2 2 2 2 2 2 2 2 2
67: 2 2 2 2 2 2 2 2
Degree 50:
1 = classical is better, 2 = karatsuba is better
horizontal axis = bits, vertical axis = length
2 5 9 15 24 37 55
1 3 7 12 19 30 45
1: 2 2 2 2 2 2 2 2 2 2 2 2
2: 2 2 2 2 2 2 2 1
3: 1 1 1 2 1 1 1
5: 1 1 2 1 2 2
7: 1
9: 2
12: 2 2 2 2
15: 2 2 2 2
19: 1 2 2 2 2 2 2
24: 2 2 2 2 2 2 2 2 2 2
30: 1 2 2 2 2 2 2 2
37: 2 2 2 2 2 2 2 2 2
45: 1 2 1 2 2 2 2 2 2 2
It looks like length*bits > 100 || degree(number field) > 25 should work.
I think @fieker was playing with power series over padics? Something exotic if I remember correctly.
The generic crossover should be fine for a ring that big I think.
I will have to deal with power series themselves separately. They use mullow_karatsuba I think.
I've implemented * to use the old mul_karatsuba in the cases benchmarked above, but the new mul_karatsuba (in src/algorithms) is probably better for rings without coefficient explosion. It only takes a length cutoff as input. This should be used instead in all rings without coefficient explosion (where presumably length is the only parameter affecting cutoff).