Hizli Polinom Carpimi - 1

Question

Hepimiz birinci dereceden 2 polinomu nasil carpmamiz gerektigini biliyoruz. Ornegin $p(x) = a + bx$ ve $q(x) = c + dx$ olsun. $p(x)q(x) = A + Bx + Cx^2$ diyelim. O zaman, teker teker terim terim carparak $A = ac, B=ad + bc$ ve $C=bd$ oldugunu buluyoruz. Ama bu arada 4 adet carpma islemi, 1 adet toplama islemi yapiyoruz. Bu sonucu 4'ten az carpma islemi yaparak bulabilir misiniz? (Toplama islemi sayisi artabilir.)

Bu sorunun amaci ne? Carpma genel olarak toplamadan cok daha pahali bir islemdir. Ben size 123456 ile 789123 sayilarini carpin desem, kac dakikanizi alir? Bu sayilari toplayin desem ne kadar vaktinizi alir? Bilgisayar bilimi calisan matematikcilerin bazilari, bunun gibi sorulara cevap ariyorlar. Cep telefonlarimizin, tabletlerimizin biz farkinda bile olmadan yaptigi onlarca matris carpimini, polinom carpimini daha da hizlandiracak bir algoritma bulmaya calisiyorlar.

Not: Sorunun daha genel halini lisans seviyesinde soracagim daha sonra.

Comments

ben de akademigini sorayim madem en sonra :)

---

Sen sor o zaman benim yerime :) Benim bildigim algoritmayi sorunun icinde ipucu olarak verdim aslinda, koyu renklerle. Ne diyorsun?

---

Bence o kadar acik degil yine de. Ben okumayi seviyorum bu tarz sorularda. Buralar da olacam, seriye 1 takipci mevcut en az :)

---

abi hanginiz soracaksaniz sorun hadi, bekliyoruz biriniz soracak diye :)

---

Ozgur abi soracak :)

---

Geldi taze taze, citir citir.

---

bunlarin cevaplari yok mu :)

Answer 1

$a,b,c,d \in \mathbb{R}$ olmak üzere, $p(x)=a+bx$ ve $q(x)=c+dx$ olsun.

Bu iki polinomun çarpımını aşağıdaki gibi yazabiliriz:

$p(x).q(x)=ac+(ab+cd)x+bdx^2$

$A=ac \\ B=bd$

olmak üzere,

$C=(a+b)(c+d)$ olarak tanımlarsak, yukarıdaki ifadeyi

$p(x).q(x)=A+(C-A-B)x+Bx^2$ olarak yazabiliriz.

Şu hâliyle, ilk ifadede $ab$, $ab$, $cd$ ve $bd$ olarak $4$ adet çarpma işlemi gerekirken,

ikinci ifadede, $ac$, $bd$ ve $(a+b)(c+d)$ çarpaımlarının bulunmasıyla $3$ adet çarpma işlemiyle, polinom çarpımı bulunabilir.

Comments

Bunun 2.si de var, hazir hizini almisken, onu da cozersin bence. link.

---

Teşekkürler, Sercan hocam.

Bugünlük bu kadar yeter. :)

Bu arada $n*n$'lik iki polinom çarpımını hiç ama hiç sanmıyorum ki $n$ çarpma işleminde yapalım. :)

---

@funky2000 guzel tespit. Peki ne kadar carpma islemi gerekir? (n log(n)'den kisa surede, ya da nlog(n) carpma isleminden az islemle, yapabilir misin?)