求的高精度算法

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

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