Karatsuba Algorithm
Büyük tamsayı çarpımını dört yarım-boy çarpım yerine üç çarpıma indirerek yaklaşık O(n^1.585) karmaşıklığa ulaşan böl-ve-yönet algoritması.
Karatsuba'nın asimptotik üstünlüğü küçük tamsayılarda otomatik hız kazancı değildir. Üç recursive çarpım karşılığında ek toplama, çıkarma, carry yönetimi ve geçici buffer maliyeti gelir.
Crossover Threshold
BigInteger/BigNum implementasyonlarında klasik schoolbook çarpımdan Karatsuba'ya belirli operand boyutundan sonra geçilir. Bu eşik CPU mikro-mimarisi, limb genişliği, allocator ve daha üst seviyede Toom-Cook/FFT tabanlı algoritmaların bulunmasına göre değişir.
Bu nedenle benchmark'ta yalnız operand bit uzunluğu değil, allocation ve temporary-copy davranışı da ölçülmelidir. In-place'e yakın implementasyonlar teorik algoritma aynı olsa bile ciddi fark yaratabilir.
Kaynak
- https://www.mathnet.ru/eng/dan26729