求的高精度算法

求的高精度算法第1頁(yè)，共24頁(yè)，2023年，2月20日，星期六這篇文章的內(nèi)容你了解高精度嗎？你曾經(jīng)使用過哪些數(shù)據(jù)結(jié)構(gòu)？你仔細(xì)思考過如何優(yōu)化算法嗎？在這里，你將看到怎樣成倍提速求N!的高精度算法第2頁(yè)，共24頁(yè)，2023年，2月20日，星期六關(guān)于高精度Pascal中的標(biāo)準(zhǔn)整數(shù)類型高精度算法的基本思想第3頁(yè)，共24頁(yè)，2023年，2月20日，星期六Pascal中的標(biāo)準(zhǔn)整數(shù)類型數(shù)據(jù)類型值域Shortint-128～127Byte0～255Integer-32768～32767Word0～65535Longint-2147483648～2147483647Comp-9.2e18～9.2e18Comp雖然屬于實(shí)型，實(shí)際上是一個(gè)64位的整數(shù)第4頁(yè)，共24頁(yè)，2023年，2月20日，星期六高精度算法的基本思想Pascal中的標(biāo)準(zhǔn)整數(shù)類型最多只能處理在-263～263之間的整數(shù)。如果要支持更大的整數(shù)運(yùn)算，就需要使用高精度高精度算法的基本思想，就是將無法直接處理的大整數(shù)，分割成若干可以直接處理的小整數(shù)段，把對(duì)大整數(shù)的處理轉(zhuǎn)化為對(duì)這些小整數(shù)段的處理Back第5頁(yè)，共24頁(yè)，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)的選擇每個(gè)小整數(shù)段保留盡量多的位使用Comp類型采用二進(jìn)制表示法第6頁(yè)，共24頁(yè)，2023年，2月20日，星期六每個(gè)小整數(shù)段保留盡量多的位一個(gè)例子：計(jì)算兩個(gè)15位數(shù)的和方法一分為15個(gè)小整數(shù)段，每段都是1位數(shù)，需要15次1位數(shù)加法方法二分為5個(gè)小整數(shù)段，每段都是3位數(shù)，需要5次3位數(shù)加法方法三Comp類型可以直接處理15位的整數(shù)，故1次加法就可以了比較用Integer計(jì)算1位數(shù)的加法和3位數(shù)的加法是一樣快的故方法二比方法一效率高雖然對(duì)Comp的操作要比Integer慢，但加法次數(shù)卻大大減少實(shí)踐證明，方法三比方法二更快第7頁(yè)，共24頁(yè)，2023年，2月20日，星期六使用Comp類型高精度運(yùn)算中，每個(gè)小整數(shù)段可以用Comp類型表示Comp有效數(shù)位為19～20位求兩個(gè)高精度數(shù)的和，每個(gè)整數(shù)段可以保留17位求高精度數(shù)與不超過m位整數(shù)的積，每個(gè)整數(shù)段可以保留18–m位求兩個(gè)高精度數(shù)的積，每個(gè)整數(shù)段可以保留9位如果每個(gè)小整數(shù)段保留k位十進(jìn)制數(shù)，實(shí)際上可以認(rèn)為其只保存了1位10k進(jìn)制數(shù)，簡(jiǎn)稱為高進(jìn)制數(shù)，稱1位高進(jìn)制數(shù)為單精度數(shù)第8頁(yè)，共24頁(yè)，2023年，2月20日，星期六采用二進(jìn)制表示法采用二進(jìn)制表示，運(yùn)算過程中時(shí)空效率都會(huì)有所提高，但題目一般需要以十進(jìn)制輸出結(jié)果，所以還要一個(gè)很耗時(shí)的進(jìn)制轉(zhuǎn)換過程。因此這種方法競(jìng)賽中一般不采用，也不在本文討論之列Back第9頁(yè)，共24頁(yè)，2023年，2月20日，星期六算法的優(yōu)化高精度乘法的復(fù)雜度分析連乘的復(fù)雜度分析設(shè)置緩存分解質(zhì)因數(shù)求階乘二分法求乘冪分解質(zhì)因數(shù)后的調(diào)整第10頁(yè)，共24頁(yè)，2023年，2月20日，星期六高精度乘法的復(fù)雜度分析計(jì)算n位高進(jìn)制數(shù)與m位高進(jìn)制數(shù)的積需要n*m次乘法積可能是n+m–1或n+m位高進(jìn)制數(shù)

Back第11頁(yè)，共24頁(yè)，2023年，2月20日，星期六連乘的復(fù)雜度分析（1）一個(gè)例子：計(jì)算5*6*7*8方法一：順序連乘5*6=30，1*1=1次乘法30*7=210，2*1=2次乘法210*8=1680，3*1=3次乘法方法二：非順序連乘5*6=30，1*1=1次乘法7*8=56，1*1=1次乘法30*56=1680，2*2=4次乘法共6次乘法共6次乘法特點(diǎn)：n位數(shù)*m位數(shù)=n+m位數(shù)第12頁(yè)，共24頁(yè)，2023年，2月20日，星期六連乘的復(fù)雜度分析（2）若“n位數(shù)*m位數(shù)=n+m位數(shù)”，則n個(gè)單精度數(shù)，無論以何種順序相乘，乘法次數(shù)一定為n(n-1)/2次證明：設(shè)F(n)表示乘法次數(shù)，則F(1)=0，滿足題設(shè)設(shè)k<n時(shí)，F(xiàn)(k)=k(k-1)/2，現(xiàn)在計(jì)算F(n)設(shè)最后一次乘法計(jì)算為“k位數(shù)*(n-k)位數(shù)”，則F(n)=F(k)+F(n-k)+k(n-k)=n(n-1)/2（與k的選擇無關(guān)）Back第13頁(yè)，共24頁(yè)，2023年，2月20日，星期六設(shè)置緩存（1）一個(gè)例子：計(jì)算9*8*3*2方法一：順序連乘9*8=72，1*1=1次乘法72*3=216，2*1=2次乘法216*2=432，3*1=3次乘法方法二：非順序連乘9*8=72，1*1=1次乘法3*2=6，1*1=1次乘法72*6=432，2*1=2次乘法特點(diǎn)：n位數(shù)*m位數(shù)可能是n+m-1位數(shù)共6次乘法共4次乘法第14頁(yè)，共24頁(yè)，2023年，2月20日，星期六設(shè)置緩存（2）考慮k+t個(gè)單精度數(shù)相乘a1*a2*…*ak*ak+1*…*ak+t設(shè)a1*a2*…*ak結(jié)果為m位高進(jìn)制數(shù)（假設(shè)已經(jīng)算出）ak+1*…*ak+t結(jié)果為1位高進(jìn)制數(shù)若順序相乘，需要t次“m位數(shù)*1位數(shù)”，共mt次乘法可以先計(jì)算ak+1*…*ak+t，再一起乘，只需要m+t次乘法在設(shè)置了緩存的前提下，計(jì)算m個(gè)單精度數(shù)的積，如果結(jié)果為n位數(shù)，則乘法次數(shù)約為n(n–1)/2次，與m關(guān)系不大設(shè)S=a1a2…am，S是n位高進(jìn)制數(shù)可以把乘法的過程近似看做，先將這m個(gè)數(shù)分為n組，每組的積仍然是一個(gè)單精度數(shù)，最后計(jì)算后面這n個(gè)數(shù)的積。時(shí)間主要集中在求最后n個(gè)數(shù)的積上，這時(shí)基本上滿足“n位數(shù)*m位數(shù)=n+m位數(shù)”，故乘法次數(shù)可近似的看做n(n-1)/2次第15頁(yè)，共24頁(yè)，2023年，2月20日，星期六設(shè)置緩存（3）緩存的大小設(shè)所選標(biāo)準(zhǔn)數(shù)據(jù)類型最大可以直接處理t位十進(jìn)制數(shù)設(shè)緩存為k位十進(jìn)制數(shù)，每個(gè)小整數(shù)段保存t–k位十進(jìn)制數(shù)設(shè)最后結(jié)果為n位十進(jìn)制數(shù)，則乘法次數(shù)約為k/(n–k)∑(i=1..n/k)i=(n+k)n/(2k(t–k))，其中k遠(yuǎn)小于n要乘法次數(shù)最少，只需k(t–k)最大，這時(shí)k=t/2因此，緩存的大小與每個(gè)小整數(shù)段大小一樣時(shí)，效率最高故在一般的連乘運(yùn)算中，可以用Comp作為基本整數(shù)類型，每個(gè)小整數(shù)段為9位十進(jìn)制數(shù)，緩存也是9位十進(jìn)制數(shù)Back第16頁(yè)，共24頁(yè)，2023年，2月20日，星期六分解質(zhì)因數(shù)求階乘例：10!=28*34*52*7n!分解質(zhì)因數(shù)的復(fù)雜度遠(yuǎn)小于nlogn，可以忽略不計(jì)與普通算法相比，分解質(zhì)因數(shù)后，雖然因子個(gè)數(shù)m變多了，但結(jié)果的位數(shù)n沒有變，只要使用了緩存，乘法次數(shù)還是約為n(n-1)/2次因此，分解質(zhì)因數(shù)不會(huì)變慢（這也可以通過實(shí)踐來說明）分解質(zhì)因數(shù)之后，出現(xiàn)了大量求乘冪的運(yùn)算，我們可以優(yōu)化求乘冪的算法。這樣，分解質(zhì)因數(shù)的好處就體現(xiàn)出來了Back第17頁(yè)，共24頁(yè)，2023年，2月20日，星期六二分法求乘冪二分法求乘冪，即：a2n+1=a2n*aa2n=(an)2其中，a是單精度數(shù)復(fù)雜度分析假定n位數(shù)與m位數(shù)的積是n+m位數(shù)設(shè)用二分法計(jì)算an需要F(n)次乘法F(2n)=F(n)+n2，F(xiàn)(1)=0設(shè)n=2k，則有F(n)=F(2k)=∑(i=0..k–1)4i=(4k–1)/3=(n2–1)/3與連乘的比較用連乘需要n(n-1)/2次乘法，二分法需要(n2–1)/3連乘比二分法耗時(shí)僅多50%采用二分法，復(fù)雜度沒有從n2降到nlogn第18頁(yè)，共24頁(yè)，2023年，2月20日，星期六二分法求乘冪之優(yōu)化平方算法怎樣優(yōu)化(a+b)2=a2+2ab+b2例：123452=1232*10000+452+2*123*45*100把一個(gè)n位數(shù)分為一個(gè)t位數(shù)和一個(gè)n-t位數(shù)，再求平方怎樣分設(shè)求n位數(shù)的平方需要F(n)次乘法F(n)=F(t)+F(n-t)+t(n-t)，F(xiàn)(1)=1用數(shù)學(xué)歸納法，可證明F(n)恒等于n(n+1)/2所以，無論怎樣分，效率都是一樣將n位數(shù)分為一個(gè)1位數(shù)和n–1位數(shù)，這樣處理比較方便第19頁(yè)，共24頁(yè)，2023年，2月20日，星期六二分法求乘冪之復(fù)雜度分析復(fù)雜度分析前面已經(jīng)求出F(n)=n(n+1)/2，下面換一個(gè)角度來處理S2=(∑(0≤i<n)ai10i)2=∑(0≤i<n)ai2102i+2∑(0≤i<j<n)aiaj10i+j一共做了n+C(n,2)=n(n+1)/2次乘法運(yùn)算普通算法需要n2次乘法，比改進(jìn)后的慢1倍改進(jìn)求乘冪的算法如果在用改進(jìn)后的方法求平方，則用二分法求乘冪，需要(n+4)(n–1)/6次乘法，約是連乘算法n(n–1)/2的三分之一Back第20頁(yè)，共24頁(yè)，2023年，2月20日，星期六分解質(zhì)因數(shù)后的調(diào)整（1）為什么要調(diào)整計(jì)算S=211310，可以先算211，再算310，最后求它們的積也可以根據(jù)S=211310=610*2，先算610，再乘以2即可兩種算法的效率是不同的第21頁(yè)，共24頁(yè)，2023年，2月20日，星期六分解質(zhì)因數(shù)后的調(diào)整（2）什么時(shí)候調(diào)整計(jì)算S=ax+kbx=(ab)xak當(dāng)k<xlogab時(shí)，采用(ab)xak比較好，否則采用ax+kbx更快證明：可以先計(jì)算兩種算法的乘法次數(shù)，再解不等式，就可以得到結(jié)論也可以換一個(gè)角度來分析。其實(shí)，兩種算法主要差別在最后一步求積上。由于兩種方法，積的位數(shù)都是一樣的，所以兩個(gè)因數(shù)的差越大，乘法次數(shù)就越小∴當(dāng)axbx–ak>ax+k–bx時(shí)，選用(ab)xak，反之，則采用ax+kbx?！郺xbx–ak>ax+k–bx∴(bx–ak)(ax+1)>0∴bx>ak這時(shí)k<xlogabBack第22頁(yè)，共24頁(yè)，2023年，2月20日，星期六總結(jié)內(nèi)容小結(jié)用Comp作為每個(gè)小整數(shù)段的基本整數(shù)類型采用二進(jìn)制優(yōu)化算法高精度連乘時(shí)緩存和緩存的設(shè)置改進(jìn)的求平方算法二分法求乘冪分解質(zhì)因數(shù)法求階乘以及分解質(zhì)因數(shù)后的調(diào)整應(yīng)用高精度求乘冪（平方）高精度求連乘（階乘）高精度求