资源描述：
《彭雨翔-多项式导论.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、IntroductiontoPolynomialsPicksTsinghuaUniversityDepartmentofComputerScienceandTechnologyJanuary20,20161/54PicksIntroductiontoPolynomials1/54ContentsPolynomialMultiplicationFormalPowerSeriesPolynomialAlgebraPolynomialFactorizationReference2/54PicksIntroductiontoPolynomials2/54Polyno
2、mialMultiplicationFormalPowerSeriesPolynomialAlgebraPolynomialFactorizationReference3/54PicksIntroductiontoPolynomials3/54DefinitionsandNotations∙Forpolynomial?(?)=?01?∑︀??0?+?1?+...+???=?=0???∙Vector:F=(?0,?1,...,??)?∙Degree:deg?=?∙Domain:??∈?,?∈?[?]∙Monicpolynomial:??=1.3/54Picks
3、IntroductiontoPolynomials3/54DefinitionsandNotations∑︀??∙AdditionandSubtraction:(?±?)(?)=?=0(??±??)?∑︀2?∑︀?∙Multiplication:(?×?)(?)=?=0(?+?=?????)??∏︀?∙Power:?(?)=?(?)?=14/54PicksIntroductiontoPolynomials4/54NaiveAlgorithm∙Bydefinition:∑︀∙(?×?)[?]=?+?=?????5/54PicksIntroductiontoPo
4、lynomials5/54Karatsuba’sAlgorithm∙Assumedeg?=?−1.??∙Let?(?)=?0(?)+?2?1(?),?(?)=?0(?)+?2?1(?),wheredeg?=deg?=deg?=deg?=?01012∙NaiveAlgorithm:??(?×?)(?)=(?0×?0)(?)+?2(?0×?1+?1×?0)(?)+?(?1×?1)(?)∙Let?(?)=((?0+?1)×(?0+?1))(?)∙Amazingly:(?0×?1+?1×?0)(?)=?(?)−(?0×?0)(?)−(?1×?1)(?)∙3subta
5、skswithdegree?!2∙?(?)=3?(?)+?(?).2∙?(?)=?log23t?1.585.6/54PicksIntroductiontoPolynomials6/54FastFourierTransform∙Anothermethodtorepresentapolynomial:∙F=(?(?1),?(?2),...,?(??))?∙∀?̸=?,??̸=??∙It’ssameasthecoefficientrepresentation:∑︀∏︀∙?(?)=?∏︀?̸=?(?−??)?=1(??−??)?(??)?̸=?∙Advantage:
6、F×G=(?(?1)?(?1),?(?2)?(?2),...,?(??)?(??))7/54PicksIntroductiontoPolynomials7/54FastFourierTransformRootofunity∙Therootsof??=1?2?????∙??=??=cos(2?)+?sin(2?)???∙??=??2?2∙??=????????8/54PicksIntroductiontoPolynomials8/54FastFourierTransformDFT∙ConsidercalculatingF=(?(?0),?(?1),...,?(
7、??−1))???∑︀?∑︀?∙Let?0(?)=2?2???,?1(?)=2?2?+1???=0?=0∙?(?)=?0(?2)+??1(?2)∙?(??)=?0(?2?)+???1(?2?)=?0(???)+???1(???)?????22?+?∙?(??2)=?(−??)=?0(???)−???1(???)??22∙Notice:deg?0=deg?1=?2∙Userecursionagain.∙?(?)=2?(?)+?(?)29/54PicksIntroductiontoPolynomials9/54FastFourierTransformIDFT∙N
8、otice?[?]=1∑︀?−1?−????=0?(
