大整数相乘.ppt
《大整数相乘.ppt》由会员分享,可在线阅读,更多相关《大整数相乘.ppt(4页珍藏版)》请在冰点文库上搜索。
南京理工大学,大整数相乘,通常,在分析算法的计算复杂度时,都将加法和乘法运算当作基本运算来处理,即将执行一次加法或乘法运算所需要的计算时间当作一个常数,该常数仅仅取决于计算机硬件处理速度。
然而,这个假定仅仅在参加运算的整数处于一定范围内时才是合理的。
这个整数范围取决于计算机硬件对整数的表示。
在某些情况下,要处理很大的整数,它无法在计算机硬件能直接表示的整数范围内进行处理。
这时候,就必须使用软件的方法来实现大整数的算术运算。
上次课堂上,我们介绍了二进制形式的大整数相乘的分治算法。
然而,在实际使用中,人们可能更习惯于以十进制的形式输入大整数。
南京理工大学,问题:
设有两个很大的十进制进制整数A和B,要计算AB的值.A=“123457667788888888”B=“92883938499303003278303884”,23,12,x,46,23,276,+,南京理工大学,使用分治策略来求解之,例,我们有:
例,下式成立:
w,x,y,z,w,x,n,n,南京理工大学,如何降低时间复杂性?
观察:
所以: