改善高精度运算的效率.pptVIP

第1页，共12页，星期日，2025年，2月5日2、整数数组的建立和输出

当输入数串st后，我们从左而右扫描数串st，以四个数码为一组，将之对应的10000进制数存入n数组中。具体方法如下：

readln(st)；{输入数串st}

k←length(st)；{取得数串st的长度}

fori←0tok-1dobegin{把st对应的整数保存到数组n中}

j←(k-i+3)div4-1；

n[j]←n[j]*10+ord(st[i+1])-48；

end；{for}

ln←(k+3)div4；

当得出最后结果a后，必须按照由次高位（a[la-2]）到最低位（a[0]）的顺序，将每一位元素由10000进制数转换成10进制数，即必须保证每个元素对应四位10进制数。例如a[i]=0015(0≤i≤la-2)，对应的10进制数不能为15，否则会导致错误结果。我们按照如下方法输出a对应的10进制数：

write(a[la-1])；{输出结果}

fori←la-2downto0do

write(a[i]div1000，(a[i]div100)mod10，(a[i]div10)mod10，a[i]mod10)；

第2页，共12页，星期日，2025年，2月5日3、介绍几个基本运算⑴整数数组-1（n←n-1，n为整数数组）我们从n[0]出发往左扫描，寻找第一个非零的元素（n[j]≠0，n[j-1]=n[j-2]=…=n[0]=0）。由于该位接受了底位的借位，因此减1，其后缀全为9999（n[j]=n[j]-1，n[j-1]=n[j-2]=…=n[0]=9999）。如果最高位为0（n[ln]=0），则n的长度减1。j←0；{从n[0]出发往左扫描，寻找第一个非零的元素}while(n[j]=0)doinc(j)；dec(n[j])；{由于该位接受了底位的借位，因此减1}fork←=0toj-1don[k]←9999；{其后缀全为9999}if((j=ln-1)and(n[j]=0))thendec(ln)；{如果最高位为0，则n的长度减1}第3页，共12页，星期日，2025年，2月5日⑵整数数组除以整数（a←a/i，a为整数数组，i为整数）我们按照由高位到底位的顺序，逐位相除。在除到第j位时，该位在接受了来自j+1位的余数（a[j]←a[j]+(j+1位相除的余数)*10000）后与i相除。如果最高位为0（n[ln]=0），则n的长度减1。l←0；{余数初始化}forj←la-1downto0dobegin{按照由高位到底位的顺序，逐位相除}inc(a[j]，l*10000)；{接受了来自第j+1位的余数}l←a[j]modi；{计算第j位的余数}a[j]←a[j]divi；{计算商的第j位}end；{for}while(a[la-1]=0)dodec(la)；{计算商的有效位数}第4页，共12页，星期日，2025年，2月5日⑶两个整数数组相乘（a←a*n，a和n为为整数数组）我们按照由高位到底位的顺序，将a数组的每一个元素与n相乘。当计算到a[j]*n时，根据乘法规则，a[j-1]，…，a[0]不变，a[j]为a[j]为a[j]与n[0]的乘积，a[j+k]加上a[j]*n[k]的乘积（k=ln-1，ln-2，…，1），然后按照由底位到高位的顺序处理进位。最后，如果a[la-1]*n有进位，则乘积a的有效位数为la+ln；否则a的有效位数为la+ln-1。forj←la-1downto0do{a1←a*n}fork←ln-1downto0doinc(a1[j+k-1]，a[j]*n[k])；a←a1；l←0；{进位初始化}forj←0tola+ln-1dobegin{按照由底位到高位的顺序处理进位}inc(l，a[j])；{计算经过进位后的第j位}a[j]←lmod10000；{将第j位规整为10000进制数}l←ldiv10000；{计算进位}end；{for}if(a[la+ln-1]0)theninc(la，ln){修改有效位数}elseinc(la，ln-1)；第5页，共1