Toom – Cook çarpımı - Toom–Cook multiplication

Toom-Cook , adını düşük karmaşıklığıyla yeni algoritmayı tanıtan Andrei Toom'dan ve açıklamasını temizleyen Stephen Cook'tan alan Toom-3 olarak da bilinen Toom-Cook , büyük tam sayılar için bir çarpma algoritmasıdır .

İki büyük tamsayılar, Verilen bir ve b , Toom-Cook böler bir ve b içine k küçük parçaların uzunluğu her l kısımlarında ve gerçekleştirir işlemleri. Gibi k büyüdükçe, tek böylece algoritmanın genel karmaşıklığını azaltarak, çarpma alt operasyonların birçok birleştirebiliriz. Çarpma alt işlemleri daha sonra Toom – Cook çarpımı kullanılarak yinelemeli olarak hesaplanabilir ve bu böyle devam eder. "Toom-3" ve "Toom-Cook" terimleri bazen yanlış bir şekilde birbirinin yerine kullanılsa da, Toom-3 Toom-Cook algoritmasının yalnızca tek bir örneğidir, burada k = 3'tür.

Toom-3, 9 çarpımı 5'e indirir ve Θ ( n ^{log (5) / log (3)} ) ≈ Θ ( n ^1,46 ) şeklinde çalışır. Genel olarak Toom- k , Θ ( c ( k ) n ^e ) 'de çalışır , burada e = log (2 k - 1) / log ( k ) , n ^e alt çarpmalara harcanan zamandır ve c , zamandır. küçük sabitlerle toplama ve çarpma için harcandı. Karatsuba algoritması iki numaralı küçük olanları ayrılmıştır Toom-Cook, özel bir durumdur. 4 çarpımı 3'e düşürür ve böylece Θ ( n ^{log (3) / log (2)} ) ≈ Θ ( n ^1,58 ) 'de çalışır. Sıradan uzun çarpma karmaşıklığı Θ ( n ² ) olan Toom-1'e eşdeğerdir .

E üssü , k artırılarak 1'e keyfi olarak yakın olarak ayarlanabilse de , c fonksiyonu maalesef çok hızlı büyüyor. Karma seviyeli Toom – Cook şemalarının büyüme oranı, 2005'te hala açık bir araştırma problemiydi. Donald Knuth tarafından açıklanan bir uygulama zaman karmaşıklığına ulaşır Θ ( n 2 ^{√ 2 log n} log n ) .

Ek yükü nedeniyle Toom – Cook, küçük sayılarla uzun çarpmadan daha yavaştır ve bu nedenle, asimptotik olarak daha hızlı olan Schönhage – Strassen algoritmasından önce (karmaşıklık Θ ( n log n log log n ) ) genellikle orta boyutlu çarpımlar için kullanılır. pratik hale gelir.

Toom bu algoritmayı ilk olarak 1963'te tanımladı ve Cook, 1966'da doktora tezinde geliştirilmiş (asimptotik olarak eşdeğer) bir algoritma yayınladı.

Detaylar

Bu bölümde adı geçen tam olarak nasıl Toom- gerçekleştirmek için k herhangi bir belirli değeri için k ve Marco Bodrato tarafından tarif Toom-Cook polinom çoğalması için bir açıklama oluşturulabileceğinin basitleştirilmiş bir şeklidir. Algoritmanın beş ana adımı vardır:

1. Bölme
2. Değerlendirme
3. Noktasal çarpma
4. İnterpolasyon
5. Yeniden düzenleme

Tipik bir büyük tamsayı uygulamasında, her bir tamsayı, baz veya taban bazı (tipik olarak büyük) bir b değerine ayarlanmış şekilde konumsal gösterimde bir rakam dizisi olarak temsil edilir ; bu örnek için b  = 10000 kullanırız, böylece her rakam dört ondalık basamak grubuna karşılık gelir (bir bilgisayar uygulamasında, b bunun yerine tipik olarak 2'nin kuvveti olur). Çarpılan iki tam sayının şöyle olduğunu varsayalım:

m	=	12	3456	7890	1234	5678	9012
n	=	9	8765	4321	9876	5432	1098.

Bunlar, normalde Toom – Cook ile işlenecek olandan çok daha küçüktür (ilkokul çarpımı daha hızlı olacaktır) ancak algoritmayı göstermeye hizmet edeceklerdir.

Bölme

İlk adım, baz seçmektir B  =  b ⁱ hem de basamak sayısı bu şekilde, m ve n, bir baz ile B en fazla olduğu , k (Toom-3, örneğin, 3). İ için tipik bir seçim şudur:

${\ displaystyle i = \ max \ sol \ {\ sol \ lfloor {\ frac {\ sol \ lfloor \ log _ {b} m \ sağ \ rfloor} {k}} \ sağ \ rfloor, \ sol \ lfloor {\ frac {\ sol \ lfloor \ log _ {b} n \ sağ \ rfloor} {k}} \ sağ \ rfloor \ sağ \} + 1.}$

Örneğimizde Toom-3 yapacağız, bu yüzden B = b ² = 10 ⁸ seçiyoruz . Daha sonra m ve n'yi temel B rakamlarına ayırırız m _i , n _i :

${\ displaystyle {\ begin {align} m_ {2} & {} = 123456 \\ m_ {1} & {} = 78901234 \\ m_ {0} & {} = 56789012 \\ n_ {2} & {} = 98765 \\ n_ {1} & {} = 43219876 \\ n_ {0} & {} = 54321098 \ end {hizalı}}}$

Daha sonra bu rakamları p ( B ) =  m ve q ( B ) =  n özelliği ile derece- ( k - 1) polinomları p ve q cinsinden katsayılar olarak kullanırız :

${\ displaystyle p (x) = m_ {2} x ^ {2} + m_ {1} x + m_ {0} = 123456x ^ {2} + 78901234x + 56789012 \,}$

${\ displaystyle q (x) = n_ {2} x ^ {2} + n_ {1} x + n_ {0} = 98765x ^ {2} + 43219876x + 54321098 \,}$

Bu polinomları tanımlamanın amacı, eğer onların ürününü r ( x ) = p ( x ) q ( x ) hesaplayabilirsek, cevabımız r ( B ) = m × n olacaktır .

Çarpılan sayıların farklı boyutlarda olduğu durumda, m ve n için k _m ve k _{n olarak} adlandıracağımız farklı k değerleri kullanmak yararlıdır . Örneğin, algoritma "Toom-2.5" ile Toom-Cook değinmektedir k _m  = 3 ve k _{, n}  Bu durumda = 2. i içinde B  =  b ⁱ tipik haliyle seçilir:

${\ displaystyle i = \ max \ sol \ {\ sol \ lfloor {\ frac {\ sol \ lceil \ log _ {b} m \ sağ \ rceil} {k_ {m}}} \ sağ \ rfloor, \ sol \ Zemin {\ frac {\ sol \ lceil \ log _ {b} n \ sağ \ rceil} {k_ {n}}} \ sağ \ rfloor \ sağ \}.}$

Değerlendirme

Polinom çarpımını hesaplamak için Toom – Cook yaklaşımı p ( x ) q ( x ) yaygın olarak kullanılan bir yaklaşımdır. D derece polinomunun benzersiz olarak d  + 1 noktaları ile belirlendiğine dikkat edin (örneğin, birinci derece bir çizgi polinomu iki nokta ile belirtilir). Fikir, p (·) ve q (·) ' yu çeşitli noktalarda değerlendirmektir. Ardından, çarpım polinomunda puan elde etmek için değerlerini bu noktalarda çarpın. Sonunda katsayılarını bulmak için enterpolasyon yapın.

Yana ° ( pq ) = C ( P ) + ° ( q ) , biz gerekir ° ( s ) + ° ( q ) + 1 = k _m + k _{, n} 1 - nihai sonucu tespit işaret eder. Bu Çağrı d . Toom-3 durumunda, d  = 5. Algoritma hangi noktalar seçilirse seçilsin çalışacaktır (birkaç küçük istisna dışında, Enterpolasyonda matris tersinirlik gerekliliğine bakın ), ancak algoritmayı basitleştirmek adına küçük seçmek daha iyidir 0, 1, −1 ve −2 gibi tamsayı değerleri.

Sık kullanılan alışılmadık bir puan değeri sonsuzdur, ∞ veya 1/0 olarak yazılır. "Değerlendirmek" için bir polinom s sonsuzda aslında limitini almak anlamına p ( x /) X ^{° p} olarak x sonsuza gider. Sonuç olarak, p (∞) her zaman en yüksek derece katsayısının değeridir (yukarıdaki m ₂ katsayısı örneğinde ).

Toom-3 örneğimizde 0, 1, −1, −2 ve ∞ noktalarını kullanacağız. Bu seçenekler, aşağıdaki formülleri üreterek değerlendirmeyi basitleştirir:

${\ displaystyle {\ begin {dizi} {lrlrl} p (0) & = & m_ {0} + m_ {1} (0) + m_ {2} (0) ^ {2} & = & m_ {0} \\ p (1) & = & m_ {0} + m_ {1} (1) + m_ {2} (1) ^ {2} & = & m_ {0} + m_ {1} + m_ {2} \\ p ( -1) & = & m_ {0} + m_ {1} (- 1) + m_ {2} (- 1) ^ {2} & = & m_ {0} -m_ {1} + m_ {2} \\ p (-2) & = & m_ {0} + m_ {1} (- 2) + m_ {2} (- 2) ^ {2} & = & m_ {0} -2m_ {1} + 4m_ {2} \\ p (\ infty) & = & m_ {2} && \ end {dizi}}}$

ve benzer şekilde q için . Örneğimizde, aldığımız değerler şunlardır:

p (0)	=	m 0	=	56789012	=	56789012
p (1)	=	m 0 + m 1 + m 2	=	56789012 + 78901234 + 123456	=	135813702
p (−1)	=	m 0 - m 1 + m 2	=	56789012 - 78901234 + 123456	=	−21988766
p (−2)	=	m, 0 - 2 m 1 + 4 m 2	=	56789012 - 2 × 78901234 + 4 × 123456	=	−100519632
p (∞)	=	m 2	=	123456	=	123456
q (0)	=	n 0	=	54321098	=	54321098
q (1)	=	n 0 + n 1 + n 2	=	54321098 + 43219876 + 98765	=	97639739
q (−1)	=	n 0 - n 1 + n 2	=	54321098 - 43219876 + 98765	=	11199987
q (−2)	=	n, 0 - 2 , n 1 + 4 , n 2	=	54321098 - 2 × 43219876 + 4 × 98765	=	−31723594
q (∞)	=	n 2	=	98765	=	98765.

Gösterildiği gibi, bu değerler negatif olabilir.

Daha sonra açıklama amacıyla, bu değerlendirme sürecini, matrisin her satırının değerlendirme noktalarından birinin güçlerini içerdiği ve vektörün polinomun katsayılarını içerdiği bir matris-vektör çarpımı olarak görmek faydalı olacaktır:

${\ displaystyle \ sol ({\ başlar {matris} p (0) \\ p (1) \\ p (-1) \\ p (-2) \\ p (\ infty) \ uç {matris}} \ sağ) = \ left ({\ begin {matrix} 0 ^ {0} & 0 ^ {1} & 0 ^ {2} \\ 1 ^ {0} & 1 ^ {1} & 1 ^ {2} \\ (- 1) ^ {0} & (- 1) ^ {1} & (- 1) ^ {2} \\ (- 2) ^ {0} & (- 2) ^ {1} & (- 2) ^ {2} \\ 0 & 0 & 1 \ end {matris}} \ sağ) \ left ({\ begin {matrix} m_ {0} \\ m_ {1} \\ m_ {2} \ end {matrix}} \ right) = \ left ( {\ begin {matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & -2 & 4 \\ 0 & 0 & 1 \ end {matrix}} \ right) \ left ({\ begin {matrix} m_ {0} \\ m_ {1 } \\ m_ {2} \ end {matris}} \ sağ).}$

Matrisin boyutları, p için d x k _m ve q için d ve k _{n şeklindedir} . Son sütundaki 1 dışında sonsuzluk satırı her zaman sıfırdır.

Daha hızlı değerlendirme

Çok noktalı değerlendirme yukarıdaki formüllerden daha hızlı elde edilebilir. Temel işlemlerin sayısı (toplama / çıkarma) azaltılabilir. Bodrato tarafından Toom-3 için verilen, burada çalışan örneğin ilk işlenen (polinom p ) üzerinde yürütülen dizi aşağıdaki gibidir:

p 0	←	m 0 + m 2	=	56789012 + 123456	=	56912468
p (0)	=	m 0	=	56789012	=	56789012
p (1)	=	p 0 + m 1	=	56912468 + 78901234	=	135813702
p (−1)	=	p 0 - m 1	=	56912468 - 78901234	=	−21988766
p (−2)	=	( p (−1) + m 2 ) × 2 - m 0	=	(- 21988766 + 123456) × 2-56789012	=	- 100519632
p (∞)	=	m 2	=	123456	=	123456.

Bu sıra, biri doğrudan değerlendirmeden az olmak üzere beş toplama / çıkarma işlemi gerektirir. Ayrıca p (−2) hesaplamasında 4 ile çarpma kaydedildi.

Noktasal çarpma

P (·) ve q (·) polinomlarını çarpmanın aksine , değerlendirilen p ( a ) ve q ( a ) değerlerini çarpmak tam sayıları çarpmayı içerir - orijinal sorunun daha küçük bir örneği. Her bir değerlendirilen nokta çiftini çarpmak için çarpma yordamımızı yinelemeli olarak çağırırız. Pratik uygulamalarda, işlenenler küçüldükçe algoritma ders kitabı uzun çarpmaya geçecektir . Letting r ürün polinomun be, bizim örneğimizde Elimizdeki:

r (0)	=	p (0) q (0)	=	56789012 × 54321098	=	3084841486175176
r (1)	=	p (1) q (1)	=	135813702 × 97639739	=	13260814415903778
r (−1)	=	p (−1) q (−1)	=	−21988766 × 11199987	=	−246273893346042
r (−2)	=	p (−2) q (−2)	=	−100519632 × −31723594	=	3188843994597408
r (∞)	=	p (∞) q (∞)	=	123456 × 98765	=	12193131840.

Gösterildiği gibi, bunlar da olumsuz olabilir. Yeterince büyük sayılar için, bu en pahalı adımdır, m ve n boyutlarında doğrusal olmayan tek adımdır .

İnterpolasyon

Bu en karmaşık adımdır, değerlendirme adımının tersidir: r (·) çarpım polinomu üzerindeki d noktalarımız göz önüne alındığında , katsayılarını belirlememiz gerekir. Başka bir deyişle, sağ taraftaki vektör için bu matris denklemini çözmek istiyoruz:

${\ displaystyle {\ başlar {hizalı} \ sol ({\ başlar {matris} r (0) \\ r (1) \\ r (-1) \\ r (-2) \\ r (\ infty) \ end {matrix}} \ right) & {} = \ left ({\ begin {matrix} 0 ^ {0} & 0 ^ {1} & 0 ^ {2} & 0 ^ {3} & 0 ^ {4} \\ 1 ^ {0} & 1 ^ {1} & 1 ^ {2} & 1 ^ {3} & 1 ^ {4} \\ (- 1) ^ {0} & (- 1) ^ {1} & (- 1) ^ {2 } & (- 1) ^ {3} & (- 1) ^ {4} \\ (- 2) ^ {0} & (- 2) ^ {1} & (- 2) ^ {2} & (- 2) ^ {3} & (- 2) ^ {4} \\ 0 & 0 & 0 & 0 & 1 \ end {matrix}} \ right) \ left ({\ begin {matrix} r_ {0} \\ r_ {1} \\ r_ { 2} \\ r_ {3} \\ r_ {4} \ end {matrix}} \ right) \\ & {} = \ left ({\ begin {matrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 \ \ 1 & -2 & 4 & -8 & 16 \\ 0 & 0 & 0 & 0 & 1 \ end {matrix}} \ right) \ left ({\ begin {matrix} r_ {0} \\ r_ {1} \\ r_ {2} \\ r_ {3} \ \ r_ {4} \ end {matris}} \ sağ). \ end {hizalı}}}$

Bu matris, d × d olması dışında değerlendirme adımındakiyle aynı şekilde oluşturulmuştur . Bu denklemi Gauss eliminasyonu gibi bir teknikle çözebilirdik , ama bu çok pahalı. Bunun yerine, değerlendirme noktalarının uygun şekilde seçilmesi koşuluyla, bu matrisin tersine çevrilebilir olduğu gerçeğini kullanırız (ayrıca bkz. Vandermonde matrisi ) ve böylece:

${\ displaystyle {\ begin {align {align}}} \ left ({\ begin {matrix} r_ {0} \\ r_ {1} \\ r_ {2} \\ r_ {3} \\ r_ {4} \ end {matris }} \ right) & {} = \ left ({\ begin {matrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & -2 & 4 & -8 & 16 \\ 0 & 0 & 0 & 0 & 1 \ end {matrix}} \ right) ^ { -1} \ left ({\ begin {matris} r (0) \\ r (1) \\ r (-1) \\ r (-2) \\ r (\ infty) \ end {matris}} \ sağ) \\ & {} = \ left ({\ begin {matrix} 1 & 0 & 0 & 0 & 0 \\ {\ tfrac {1} {2}} & {\ tfrac {1} {3}} & - 1 & {\ tfrac {1} {6}} & - 2 \\ - 1 & {\ tfrac {1} {2}} & {\ tfrac {1} {2}} & 0 & -1 \\ - {\ tfrac {1} {2}} & { \ tfrac {1} {6}} & {\ tfrac {1} {2}} & - {\ tfrac {1} {6}} & 2 \\ 0 & 0 & 0 & 0 & 1 \ end {matrix}} \ sağ) \ left ({\ başlangıç ​​{matris} r (0) \\ r (1) \\ r (-1) \\ r (-2) \\ r (\ infty) \ end {matris}} \ sağ). \ end {hizalı} }}$

Geriye kalan tek şey bu matris vektör çarpımını hesaplamaktır. Matris kesirler içerse de, ortaya çıkan katsayılar tamsayılar olacaktır - bu nedenle bunların tümü tamsayı aritmetiği, sadece eklemeler, çıkarmalar ve küçük sabitlerle çarpma / bölme ile yapılabilir. Toom-Cook'taki zor bir tasarım zorluğu, bu ürünü hesaplamak için verimli bir işlem dizisi bulmaktır; Bodrato tarafından Toom-3 için verilen bir sekans, burada devam eden örnek üzerinden yürütülür:

r 0	←	r (0)	=	3084841486175176
r 4	←	r (∞)	=	12193131840
r 3	←	( r (−2) - r (1)) / 3	=	(3188843994597408 - 13260814415903778) / 3
			=	−3357323473768790
r 1	←	( r (1) - r (−1)) / 2	=	(13260814415903778 - (−246273893346042)) / 2
			=	6753544154624910
r 2	←	r (−1) - r (0)	=	−246273893346042 - 3084841486175176
			=	−3331115379521218
r 3	←	( r 2 - r 3 ) / 2 + 2 r (∞)	=	(−3331115379521218 - (−3357323473768790)) / 2 + 2 × 12193131840
			=	13128433387466
r 2	←	r 2 + r 1 - r 4	=	−3331115379521218 + 6753544154624910 - 12193131840
			=	3422416581971852
r 1	←	r 1 - r 3	=	6753544154624910 - 13128433387466
			=	6740415721237444.

Artık polinom r ürünümüzü biliyoruz :

${\ displaystyle {\ begin {array} {rrr} r (x) = & {} & 3084841486175176 \\ & + & 6740415721237444x \\ & + & 3422416581971852x ^ {2} \\ & + & 13128433387466x ^ {3} \\ & + & 12193131840x ^ {4} \ end {dizi}}}$

Farklı k _m , k _n veya değerlendirme noktaları kullansaydık, matris ve dolayısıyla enterpolasyon stratejimiz değişirdi; ancak girişlere bağlı değildir ve bu nedenle verilen herhangi bir parametre seti için sabit kodlanabilir.

Yeniden düzenleme

Son olarak, nihai cevabımızı elde etmek için r (B) 'yi değerlendiririz. Bu basittir, çünkü B, b'nin bir kuvveti ve dolayısıyla B'nin üsleriyle çarpımların tümü, b tabanındaki bir tam sayı basamaklı kaymalardır . Çalışan örnekte b = 10 ⁴ ve B = b ² = 10 ⁸ .

								3084	8414	8617	5176
						6740	4157	2123	7444
				3422	4165	8197	1852
		13	1284	3338	7466
+	121	9313	1840
	121	9326	3124	6761	1632	4937	6009	5208	5858	8617	5176

Ve bu aslında 1234567890123456789012 ve 987654321987654321098'in ürünüdür.

Çeşitli k için enterpolasyon matrisleri

Burada, k _m ve k _n'nin birkaç farklı ortak küçük değeri için ortak enterpolasyon matrisleri veriyoruz .

Toom-1

Toom-1 ( k _m = k _n = 1) 1 değerlendirme noktası gerektirir, burada 0 olarak seçilir: Özdeşlik matrisinin bir interpolasyon matrisiyle uzun çarpmaya dejenere olur:

${\ displaystyle \ left ({\ begin {matrix} 1 \ end {matrix}} \ right) ^ {- 1} = \ left ({\ begin {matrix} 1 \ end {matrix}} \ sağ).}$

Toom-1.5

Toom-1.5 ( k _m = 2, k _n = 1) 2 değerlendirme puanı gerektirir, burada 0 ve ∞ seçilmiştir. Enterpolasyon matrisi daha sonra kimlik matrisidir:

${\ displaystyle \ sol ({\ başlar {matris} 1 ve 0 \\ 0 ve 1 \ uç {matris}} \ sağ) ^ {- 1} = \ sol ({\ başlar {matris} 1 ve 0 \\ 0 ve 1 \ uç {matris}} \sağ).}$

Bu aynı zamanda uzun çarpmaya doğru dejenere olur: bir faktörün her iki katsayısı diğer faktörün tek katsayısı ile çarpılır.

Toom-2

Toom-2 ( k _m = 2, k _n = 2) burada 0, 1 ve ∞ olarak seçilen 3 değerlendirme puanı gerektirir. Karatsuba çarpımı ile aynıdır ve enterpolasyon matrisi:

${\ displaystyle \ sol ({\ başlar {matris} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \ end {matris}} \ sağ) ^ {- 1} = \ sol ({\ başlar {matris} 1 & 0 & 0 \\ - 1 & 1 & -1 \\ 0 & 0 & 1 \ end {matris}} \ sağ).}$

Toom-2.5

Toom-2.5 ( k _m = 3, k _n = 2) 4 değerlendirme puanı gerektirir, burada 0, 1, be1 ve ∞ olarak seçilir. Daha sonra aşağıdaki enterpolasyon matrisine sahiptir:

${\ displaystyle \ sol ({\ başlar {matris} 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 0 & 0 & 0 & 1 \ end {matris}} \ sağ) ^ {- 1} = \ sol ({\ başla {matris} 1 & 0 & 0 & 0 \\ 0 & {\ tfrac {1} {2}} & - {\ tfrac {1} {2}} & - 1 \\ - 1 & {\ tfrac {1} {2}} & {\ tfrac {1} {2}} & 0 \\ 0 & 0 & 0 & 1 \ end {matris}} \ sağ).}$

Notlar

Referanslar

• D. Knuth. Bilgisayar Programlama Sanatı , Cilt 2. Üçüncü Baskı, Addison-Wesley, 1997. Bölüm 4.3.3.A: Dijital yöntemler, s. 294.
• R. Crandall ve C. Pomerance. Asal Sayılar - Hesaplamalı Bir Perspektif . İkinci Baskı, Springer, 2005. Bölüm 9.5.1: Karatsuba ve Toom – Cook yöntemleri, s. 473.
• M. Bodrato. Optimal Toom-Cook Çarpma doğru ... . WAIFI'07, Springer, 2007'de.

Dış bağlantılar

• GMP belgelerinden Toom – Cook 3 yollu çarpma