1、求N!的高精度算法,本文中的算法主要針對Pascal語言,這篇文章的內(nèi)容,你了解高精度嗎？ 你曾經(jīng)使用過哪些數(shù)據(jù)結(jié)構(gòu)？ 你仔細(xì)思考過如何優(yōu)化算法嗎？,在這里，你將看到怎樣成倍提速求N!的高精度算法,關(guān)于高精度,Pascal中的標(biāo)準(zhǔn)整數(shù)類型 高精度算法的基本思想,Pascal中的標(biāo)準(zhǔn)整數(shù)類型,Comp雖然屬于實型，實際上是一個64位的整數(shù),高精度算法的基本思想,Pascal中的標(biāo)準(zhǔn)整數(shù)類型最多只能處理在-263263之間的整數(shù)。如果要支持更大的整數(shù)運(yùn)算，就需要使用高精度 高精度算法的基本思想，就是將無法直接處理的大整數(shù)，分割成若干可以直接處理的小整數(shù)段，把對大整數(shù)的處理轉(zhuǎn)化為對這些小整數(shù)段的處理

2、,Back,數(shù)據(jù)結(jié)構(gòu)的選擇,每個小整數(shù)段保留盡量多的位 使用Comp類型 采用二進(jìn)制表示法,每個小整數(shù)段保留盡量多的位,一個例子：計算兩個15位數(shù)的和 方法一 分為15個小整數(shù)段，每段都是1位數(shù)，需要15次1位數(shù)加法 方法二 分為5個小整數(shù)段，每段都是3位數(shù)，需要5次3位數(shù)加法 方法三 Comp類型可以直接處理15位的整數(shù)，故1次加法就可以了 比較 用Integer計算1位數(shù)的加法和3位數(shù)的加法是一樣快的 故方法二比方法一效率高 雖然對Comp的操作要比Integer慢，但加法次數(shù)卻大大減少 實踐證明，方法三比方法二更快,使用Comp類型,高精度運(yùn)算中，每個小整數(shù)段可以用Comp類型表示 Co

3、mp有效數(shù)位為1920位 求兩個高精度數(shù)的和，每個整數(shù)段可以保留17位 求高精度數(shù)與不超過m位整數(shù)的積，每個整數(shù)段可以保留18m位 求兩個高精度數(shù)的積，每個整數(shù)段可以保留9位 如果每個小整數(shù)段保留k位十進(jìn)制數(shù)，實際上可以認(rèn)為其只保存了1位10k進(jìn)制數(shù)，簡稱為高進(jìn)制數(shù) ，稱1位高進(jìn)制數(shù)為單精度數(shù),采用二進(jìn)制表示法,采用二進(jìn)制表示，運(yùn)算過程中時空效率都會有所提高，但題目一般需要以十進(jìn)制輸出結(jié)果，所以還要一個很耗時的進(jìn)制轉(zhuǎn)換過程。因此這種方法競賽中一般不采用，也不在本文討論之列,Back,算法的優(yōu)化,高精度乘法的復(fù)雜度分析 連乘的復(fù)雜度分析 設(shè)置緩存 分解質(zhì)因數(shù)求階乘 二分法求乘冪 分解質(zhì)因數(shù)后的調(diào)

4、整,高精度乘法的復(fù)雜度分析,計算n位高進(jìn)制數(shù)與m位高進(jìn)制數(shù)的積 需要n*m次乘法 積可能是n+m1或n+m位高進(jìn)制數(shù),Back,連乘的復(fù)雜度分析（1）,一個例子：計算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ù),連乘的復(fù)雜度分析（2）,若“n位數(shù)*m位數(shù)=n+m位數(shù)”，則n個單精度數(shù)，無論以何種順序相乘，乘法次數(shù)一定為

5、n(n-1)/2次 證明： 設(shè)F(n)表示乘法次數(shù)，則F(1)=0，滿足題設(shè) 設(shè)kn時，F(xiàn)(k)=k(k-1)/2，現(xiàn)在計算F(n) 設(shè)最后一次乘法計算為“k位數(shù)*(n-k)位數(shù)”，則 F(n)=F(k)+F(n-k)+k (n-k)=n(n-1)/2（與k的選擇無關(guān)）,Back,設(shè)置緩存（1）,一個例子：計算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+

6、m-1位數(shù),共6次乘法,共4次乘法,設(shè)置緩存（2）,考慮k+t個單精度數(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次乘法 可以先計算ak+1*ak+t，再一起乘，只需要m+t次乘法,在設(shè)置了緩存的前提下，計算m個單精度數(shù)的積，如果結(jié)果為n位數(shù)，則乘法次數(shù)約為n(n1)/2次，與m關(guān)系不大,設(shè)S=a1a2 am，S是n位高進(jìn)制數(shù) 可以把乘法的過程近似看做，先將這m個數(shù)分為n組，每組的積仍然是一個單精度數(shù)，最后計算后面這n個數(shù)的積。時間主要集中在求最后n個數(shù)的

7、積上，這時基本上滿足“n位數(shù)*m位數(shù)=n+m位數(shù)”，故乘法次數(shù)可近似的看做n(n-1)/2次,設(shè)置緩存（3）,緩存的大小 設(shè)所選標(biāo)準(zhǔn)數(shù)據(jù)類型最大可以直接處理t位十進(jìn)制數(shù) 設(shè)緩存為k位十進(jìn)制數(shù)，每個小整數(shù)段保存tk位十進(jìn)制數(shù) 設(shè)最后結(jié)果為n位十進(jìn)制數(shù)，則乘法次數(shù)約為 k/(nk) (i=1.n/k)i=(n+k)n/(2k(tk)，其中k遠(yuǎn)小于n 要乘法次數(shù)最少，只需k (tk)最大，這時k=t/2 因此，緩存的大小與每個小整數(shù)段大小一樣時，效率最高 故在一般的連乘運(yùn)算中，可以用Comp作為基本整數(shù)類型，每個小整數(shù)段為9位十進(jìn)制數(shù)，緩存也是9位十進(jìn)制數(shù),Back,分解質(zhì)因數(shù)求階乘,例：10!=2

8、8*34*52*7 n!分解質(zhì)因數(shù)的復(fù)雜度遠(yuǎn)小于nlogn，可以忽略不計 與普通算法相比，分解質(zhì)因數(shù)后，雖然因子個數(shù)m變多了，但結(jié)果的位數(shù)n沒有變，只要使用了緩存，乘法次數(shù)還是約為n(n-1)/2次 因此，分解質(zhì)因數(shù)不會變慢（這也可以通過實踐來說明） 分解質(zhì)因數(shù)之后，出現(xiàn)了大量求乘冪的運(yùn)算，我們可以優(yōu)化求乘冪的算法。這樣，分解質(zhì)因數(shù)的好處就體現(xiàn)出來了,Back,二分法求乘冪,二分法求乘冪，即： a2n+1=a2n*a a2n=(an)2 其中，a是單精度數(shù) 復(fù)雜度分析 假定n位數(shù)與m位數(shù)的積是n+m位數(shù) 設(shè)用二分法計算an需要F(n)次乘法 F(2n)=F(n)+n2，F(xiàn)(1)=0 設(shè)n=2k

9、，則有F(n)=F(2k)=(i=0.k1)4i=(4k1)/3=(n21)/3 與連乘的比較 用連乘需要n(n-1)/2次乘法，二分法需要(n21)/3 連乘比二分法耗時僅多50% 采用二分法，復(fù)雜度沒有從n2降到nlogn,二分法求乘冪之優(yōu)化平方算法,怎樣優(yōu)化 (a+b)2=a2+2ab+b2 例：123452=1232*10000+452+2*123*45*100 把一個n位數(shù)分為一個t位數(shù)和一個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 所以，無論怎樣

10、分，效率都是一樣 將n位數(shù)分為一個1位數(shù)和n1位數(shù)，這樣處理比較方便,二分法求乘冪之復(fù)雜度分析,復(fù)雜度分析 前面已經(jīng)求出F(n)=n(n+1)/2，下面換一個角度來處理 S2=(0in)ai10i)2=(0in)ai2102i+2(0ijn)aiaj10i+j 一共做了n+C(n,2)=n(n+1)/2次乘法運(yùn)算 普通算法需要n2次乘法，比改進(jìn)后的慢1倍 改進(jìn)求乘冪的算法 如果在用改進(jìn)后的方法求平方，則用二分法求乘冪，需要(n+4)(n1)/6次乘法，約是連乘算法n(n1)/2的三分之一,Back,分解質(zhì)因數(shù)后的調(diào)整（1）,為什么要調(diào)整 計算S=211310，可以先算211，再算310，最后求

11、它們的積 也可以根據(jù)S=211310=610*2，先算610，再乘以 2即可 兩種算法的效率是不同的,分解質(zhì)因數(shù)后的調(diào)整（2）,什么時候調(diào)整 計算S=ax+kbx=(ab)xak 當(dāng)kax+kbx時，選用(ab)xak，反之，則采用ax+kbx。 axbxakax+kbx (bxak)(ax+1)0 bxak 這時kxlogab,Back,總結(jié),內(nèi)容小結(jié) 用Comp作為每個小整數(shù)段的基本整數(shù)類型 采用二進(jìn)制優(yōu)化算法 高精度連乘時緩存和緩存的設(shè)置 改進(jìn)的求平方算法 二分法求乘冪 分解質(zhì)因數(shù)法求階乘以及分解質(zhì)因數(shù)后的調(diào)整 應(yīng)用 高精度求乘冪（平方） 高精度求連乘（階乘） 高精度求排列組合,結(jié)束語,求N!的高精度