大不等式在计算机中的转换

大不等式在计算机中的转换

科学计算和密码学应用通常包括将大平均值转换为10进制和16进制的过程。这不是用普通语言中的编码方法进行的。因此，我们使用cc编码执行了这样的转换工具。下面介绍一下我们的实现思想。1个长度和前导位的长度因为在科学计算和密码学应用中涉及到的大整数往往多达1024比特位,甚至更多。因此必须设计这种数在计算机中的存储方式。在我们的实现中,我们用下面的结构表示16进制的大整数:结构中的字节数组digits存储大整数的数据内容,每个字节存储的数据的范围是0到255之间,并且为了编码方便,采用小端的方式表示,即在数组中大整数的低位字节在前,高位字节在后。于是这个字节数组最多可以表示512个字节,即4096比特位的大整数。结构中的len参数表示大整数的实际字节长度,即这个长度是去掉前导位为零的字节后的长度。于是每一个这样的结构变量对应的大整数为:digits+digits×256+digits×2562+…+digits[len-1]×256len-1.(1)关于十进制的大整数,我们定义了下面的结构:结构中的字节数组digits存储大整数的数据内容,每个字节存储的数据的范围是0到99之间,也采用小端的方式表示,即在数组中大整数的低位字节在前,高位字节在后。于是这个字节数组最多可以表示1234位十进制数。结构中的len参数表示大整数的实际长度,即这个长度是去掉前导位为零的字节后的长度。于是每一个这样的结构变量对应的大整数为:digits+digits×100+digits×1002+…+digits[len-1]×100len-1.(2)因为4096比特的二进制数对应的最大整数为24096-1,其对应的十进制数为:1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190335恰好有1234位。因此我们定义的结构可以保证所有不多于512字节的十六进制数正确地转换成十进制,也能保证不大于24096-1的十进制数正确地转换成十六进制。2把大个数作为编码转换的条件大整数从十六进制转换到十进制的基本思想是利用(1)。由于(1)涉及到了十进制的加法、乘法、乘方,因此我们设计了一个十进制的大整数加法算法、一个个十进制的大整数乘法算法。我们设计的十进制大整数的加法算法如下:设a=(ak-1…a0)100和b=(bℓ-1…b0)100是两个十进制大整数。假设k≥ℓ≥1(如果k<ℓ,那么我们可以仅交换a和b).它们的和c:=a+b的形式为c=(ckck-1…c0)100.我们可以在O(k)时间内计算a+b的以100为基的表示,如下:注意到在每轮迭代中,carry的值为0或1,而值tmp位于0和199之间。我们设计的十进制大整数的一般乘法算法如下:设a=(ak-1…a0)100和b=(bℓ-1…b0)100是两个十进制大整数,其中k≥1及ℓ≥1.乘积c:=a·b的形式为c=(ck+ℓ-1…c0)100,可以在O(kℓ)时间内计算,如下:注意在上面的算法中“%”表示模100取余数,而“/”表示整数商。在上面算法中的每一步,carry的值位于0和99之间,而tmp的值位于0和9999之间。我们分析一下这个转换的运行时间。设要转换的大整数存储在LargeInt结够变量A中。首先考虑乘方,即计算256i,i=1,2,…,A.len-1,在具体实现时,每次计算的乘方都存起来,以备下次使用,即用公式256i=256i-1×256来完成乘方的计算,其中的被乘数256i-1用100为基表示的位长度t1≤1+(i-1)log100256,乘数256用100为基表示的位长度t2=2,因此计算乘方256i用的时间为O(t1t2)=O(2+2(i-1)log100256);接下来考虑计算A.digits[i]×256i用的时间,其中i=1,2,…,A.len-1.由前面所述这个乘积的被乘数用100为基表示的位长度t1=2,乘数用100为基表示的位长度t2≤1+ilog100256,因此计算乘积A.digits[i]×256i用的时间为O(t1t2)=O(2+2ilog100256);关于加法,我们按照公式(1)中从左到右的顺序依次进行,共需进行A.len-1次加法,第i次加法用的时间为O(1+(i+1)log100256).因此这个转换总的运行时间为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),因此总的运行时间为O((A.len)2).3结构变量a的存储十进制转换到十六进制的基本思想是首先将十进制的大整数转换成十六进制位,然后再将大整数的十六进制位表示转换成十六进字节表示。假设最终转换的结果存储到LargeInt结够变量B中,十进制到十六进制的转换算法如下:设a=(ak-1…a0)100是一个要转换的十进制大整数,其中k≥1及ak-1≠0.我们定义了一个LargeDecimalInt结构变量A来存储这个大整数。具体算法为:注意在上面的算法中每轮while循环结束时,都必须对结构变量A的len参数进行处理,以确保得到的大整数长度为其去掉前导位零后的实际长度。由于上面算法的for循环的实质是对大整数A右移4位得到新的A,因此上面算法中总的while循环的次数等于a的十六进制位数t0,而显然a<100k,于是t0≤log16a+1<log16100k+1=klog16100+1.设第i次while循环执行的for循环次数为si,那么si等于a/16i的整数部分以100为基时的位数,于是有si≤log100a-ilog10016+1<k-ilog10016+1,i=1,2,…,t0.由于t0=O(k),si=O(k),i=1,2,…,t0,从而总的运行时间为O(k2).又由于a以256为基时的位数,即B.len满足B.len≤log256a+1<log