在 .NET 开发中,有时会因为处理一些边缘学科的知识内容,如统计,金融,天文等计算,是加密解密算法都会涉及到大数的运算,就是.net中最大数值类型储存了都会溢出的数,我的一个想法是计算时用数值类型,储存( 暂时 )和输出时是字符串 那么储存时就需要BOX[n] n个数组来暂时储存一个计算中的小步骤结果,
'如一下例子====================算法理解图=======================
'97*97*97*97*97 = 8587340257
box( 1 ) = 587340257
box( 2 )=8
'97*97*97*97*97*97 = 832972004929
box( 1 ) = 972004929
box( 2 )=832
'97*97*97*97*97*97*97 = 80798284478113
box( 1 ) = 284478113
box( 2 )=80798 '97*97*97*97*97*97*97*97 = 7837433594376961
box( 1 ) = 594376961
box( 2 )=7837433
'97^ 9 = 760231058654565217
box( 1 ) = 654565217
box( 2 )=760231058
'97^ 10 = 73742412689492826049
box( 1 ) = 492826049 box( 2 )=742412689 box( 3 )=73 …… …… …… ……
注意box 下表越大对应的数越高位在,在运用上面的算法时要记住
①先定义一个BOX的标志为几位,如上面是9位( 根据需要和实际情况 ),
②由于计算习惯,很多人会从底位算起时
{
box( 0 -> n )
}
要先算box( n+1 )位的数,在把box( n ) 产生的进位数( 如第一条计算box( 1 )向box( 2 )=0产生进位数8 box( 2 )+进位数 = 8)进行处理,如以上时加法处理
③ 最好从高位算起,你将省去很多麻烦,box个数未知,没关系,用动态数组,满了时( 最高下标box产生的进位数 )再添一个还有取模运算时,如果模数不大,也可以采用以上思想分段求模,再链接box得暂时结果,重新分配box( 一定要从高位起重新截断 )如被模数123456789123456789 设八位一个box box( 1 )=89 box( 2 )=91234567 box( 3 )=12345678各box分别取模再联合( 传统是123456789123456789 ÷ 333=370741108478849 模是72 ) 那么重新分配的盒子应该是box( 1 ) =478849 box( 2 ) =370741180 而不能是box( 1 ) =370741180 box( 2 ) = 478849 为什么? ∵从高位开始取模,box( n ) 在被取模一次后如果不变,再次取模结果没变是box( n ) = box( n ) 程序将进入死循环
另外一种涉及大数运算的情况式是 对A的n 次方后取模 ( A ^n mod V) 如果mod数不大可以( 是n个A后结束 )( ( A mod V )* A mod V ) * A mod V …… 此算法不一定要用递归实现,简单的循环即可,最多两层嵌套循环
最后忠告 :对一个大数进行加减乘除时千万别轻易的进行对被( 加/减/乘/除 )数因式分解,这种算法效率会很底
( 文章编写匆忙,可能存在错字,敬请原谅 )
