大不等式在計(jì)算機(jī)中的轉(zhuǎn)換

大不等式在計(jì)算機(jī)中的轉(zhuǎn)換

科學(xué)計(jì)算和密碼學(xué)應(yīng)用通常包括將大平均值轉(zhuǎn)換為10進(jìn)制和16進(jìn)制的過(guò)程。這不是用普通語(yǔ)言中的編碼方法進(jìn)行的。因此，我們使用cc編碼執(zhí)行了這樣的轉(zhuǎn)換工具。下面介紹一下我們的實(shí)現(xiàn)思想。1個(gè)長(zhǎng)度和前導(dǎo)位的長(zhǎng)度因?yàn)樵诳茖W(xué)計(jì)算和密碼學(xué)應(yīng)用中涉及到的大整數(shù)往往多達(dá)1024比特位,甚至更多。因此必須設(shè)計(jì)這種數(shù)在計(jì)算機(jī)中的存儲(chǔ)方式。在我們的實(shí)現(xiàn)中,我們用下面的結(jié)構(gòu)表示16進(jìn)制的大整數(shù):結(jié)構(gòu)中的字節(jié)數(shù)組digits存儲(chǔ)大整數(shù)的數(shù)據(jù)內(nèi)容,每個(gè)字節(jié)存儲(chǔ)的數(shù)據(jù)的范圍是0到255之間,并且為了編碼方便,采用小端的方式表示,即在數(shù)組中大整數(shù)的低位字節(jié)在前,高位字節(jié)在后。于是這個(gè)字節(jié)數(shù)組最多可以表示512個(gè)字節(jié),即4096比特位的大整數(shù)。結(jié)構(gòu)中的len參數(shù)表示大整數(shù)的實(shí)際字節(jié)長(zhǎng)度,即這個(gè)長(zhǎng)度是去掉前導(dǎo)位為零的字節(jié)后的長(zhǎng)度。于是每一個(gè)這樣的結(jié)構(gòu)變量對(duì)應(yīng)的大整數(shù)為:digits+digits×256+digits×2562+…+digits[len-1]×256len-1.(1)關(guān)于十進(jìn)制的大整數(shù),我們定義了下面的結(jié)構(gòu):結(jié)構(gòu)中的字節(jié)數(shù)組digits存儲(chǔ)大整數(shù)的數(shù)據(jù)內(nèi)容,每個(gè)字節(jié)存儲(chǔ)的數(shù)據(jù)的范圍是0到99之間,也采用小端的方式表示,即在數(shù)組中大整數(shù)的低位字節(jié)在前,高位字節(jié)在后。于是這個(gè)字節(jié)數(shù)組最多可以表示1234位十進(jìn)制數(shù)。結(jié)構(gòu)中的len參數(shù)表示大整數(shù)的實(shí)際長(zhǎng)度,即這個(gè)長(zhǎng)度是去掉前導(dǎo)位為零的字節(jié)后的長(zhǎng)度。于是每一個(gè)這樣的結(jié)構(gòu)變量對(duì)應(yīng)的大整數(shù)為:digits+digits×100+digits×1002+…+digits[len-1]×100len-1.(2)因?yàn)?096比特的二進(jìn)制數(shù)對(duì)應(yīng)的最大整數(shù)為24096-1,其對(duì)應(yīng)的十進(jìn)制數(shù)為:1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190335恰好有1234位。因此我們定義的結(jié)構(gòu)可以保證所有不多于512字節(jié)的十六進(jìn)制數(shù)正確地轉(zhuǎn)換成十進(jìn)制,也能保證不大于24096-1的十進(jìn)制數(shù)正確地轉(zhuǎn)換成十六進(jìn)制。2把大個(gè)數(shù)作為編碼轉(zhuǎn)換的條件大整數(shù)從十六進(jìn)制轉(zhuǎn)換到十進(jìn)制的基本思想是利用(1)。由于(1)涉及到了十進(jìn)制的加法、乘法、乘方,因此我們?cè)O(shè)計(jì)了一個(gè)十進(jìn)制的大整數(shù)加法算法、一個(gè)個(gè)十進(jìn)制的大整數(shù)乘法算法。我們?cè)O(shè)計(jì)的十進(jìn)制大整數(shù)的加法算法如下:設(shè)a=(ak-1…a0)100和b=(b?-1…b0)100是兩個(gè)十進(jìn)制大整數(shù)。假設(shè)k≥?≥1(如果k<?,那么我們可以僅交換a和b).它們的和c:=a+b的形式為c=(ckck-1…c0)100.我們可以在O(k)時(shí)間內(nèi)計(jì)算a+b的以100為基的表示,如下:注意到在每輪迭代中,carry的值為0或1,而值tmp位于0和199之間。我們?cè)O(shè)計(jì)的十進(jìn)制大整數(shù)的一般乘法算法如下:設(shè)a=(ak-1…a0)100和b=(b?-1…b0)100是兩個(gè)十進(jìn)制大整數(shù),其中k≥1及?≥1.乘積c:=a·b的形式為c=(ck+?-1…c0)100,可以在O(k?)時(shí)間內(nèi)計(jì)算,如下:注意在上面的算法中“%”表示模100取余數(shù),而“/”表示整數(shù)商。在上面算法中的每一步,carry的值位于0和99之間,而tmp的值位于0和9999之間。我們分析一下這個(gè)轉(zhuǎn)換的運(yùn)行時(shí)間。設(shè)要轉(zhuǎn)換的大整數(shù)存儲(chǔ)在LargeInt結(jié)夠變量A中。首先考慮乘方,即計(jì)算256i,i=1,2,…,A.len-1,在具體實(shí)現(xiàn)時(shí),每次計(jì)算的乘方都存起來(lái),以備下次使用,即用公式256i=256i-1×256來(lái)完成乘方的計(jì)算,其中的被乘數(shù)256i-1用100為基表示的位長(zhǎng)度t1≤1+(i-1)log100256,乘數(shù)256用100為基表示的位長(zhǎng)度t2=2,因此計(jì)算乘方256i用的時(shí)間為O(t1t2)=O(2+2(i-1)log100256);接下來(lái)考慮計(jì)算A.digits[i]×256i用的時(shí)間,其中i=1,2,…,A.len-1.由前面所述這個(gè)乘積的被乘數(shù)用100為基表示的位長(zhǎng)度t1=2,乘數(shù)用100為基表示的位長(zhǎng)度t2≤1+ilog100256,因此計(jì)算乘積A.digits[i]×256i用的時(shí)間為O(t1t2)=O(2+2ilog100256);關(guān)于加法,我們按照公式(1)中從左到右的順序依次進(jìn)行,共需進(jìn)行A.len-1次加法,第i次加法用的時(shí)間為O(1+(i+1)log100256).因此這個(gè)轉(zhuǎn)換總的運(yùn)行時(shí)間為O(T),其中T=(A.len-1)+(2+3+…+A.len)log100256//加法+2(A.len-1)+2(1+2+…+(A.len-2))log100256//乘方+2(A.len-1)+2(1+2+…+(A.len-1))log100256//乘法≤5A.len+5log100256(1+2+…+A.len)=5A.len+5log100256(A.len+1)A.len=O((A.len)2),因此總的運(yùn)行時(shí)間為O((A.len)2).3結(jié)構(gòu)變量a的存儲(chǔ)十進(jìn)制轉(zhuǎn)換到十六進(jìn)制的基本思想是首先將十進(jìn)制的大整數(shù)轉(zhuǎn)換成十六進(jìn)制位,然后再將大整數(shù)的十六進(jìn)制位表示轉(zhuǎn)換成十六進(jìn)字節(jié)表示。假設(shè)最終轉(zhuǎn)換的結(jié)果存儲(chǔ)到LargeInt結(jié)夠變量B中,十進(jìn)制到十六進(jìn)制的轉(zhuǎn)換算法如下:設(shè)a=(ak-1…a0)100是一個(gè)要轉(zhuǎn)換的十進(jìn)制大整數(shù),其中k≥1及ak-1≠0.我們定義了一個(gè)LargeDecimalInt結(jié)構(gòu)變量A來(lái)存儲(chǔ)這個(gè)大整數(shù)。具體算法為:注意在上面的算法中每輪while循環(huán)結(jié)束時(shí),都必須對(duì)結(jié)構(gòu)變量A的len參數(shù)進(jìn)行處理,以確保得到的大整數(shù)長(zhǎng)度為其去掉前導(dǎo)位零后的實(shí)際長(zhǎng)度。由于上面算法的for循環(huán)的實(shí)質(zhì)是對(duì)大整數(shù)A右移4位得到新的A,因此上面算法中總的while循環(huán)的次數(shù)等于a的十六進(jìn)制位數(shù)t0,而顯然a<100k,于是t0≤log16a+1<log16100k+1=klog16100+1.設(shè)第i次while循環(huán)執(zhí)行的for循環(huán)次數(shù)為si,那么si等于a/16i的整數(shù)部分以100為基時(shí)的位數(shù),于是有si≤log100a-ilog10016+1<k-ilog10016+1,i=1,2,…,t0.由于t0=O(k),si=O(k),i=1,2,…,t0,從而總的運(yùn)行時(shí)間為O(k2).又由于a以256為基時(shí)的位數(shù),即B.len滿足B.len≤log256a+1<log