ضرب اعداد صحیح بزرگ
مسئله: ضرب دو عدد صحیح بزرگ u و v


  







 
 large _ integer prod ( large_integer u, large_integer v)
 
 {
 
 large_inreger x , y , w , z ;
 
 int n , m ;
 
 n = maximum(number of digits in u,number of digits in v)
 
 if (u = = 0 || v = = 0)
 
 return 0 ;
  

 
 else if (n < = threshold)
 
 return u × v obtained in the usual way;
 
 else {
 
 m = Į n / 2 ⌡;
 
 x = u divide 10 ^ m ; y = rem 10 ^ m;
 
 w = v divide 10 ^ m ; z = rem 10 ^ m;
 
  return prod (x ,w) × 10 ^2m + ( prod ( x, z) + prod (w, y )) × 10 ^ m + prod ( y, z);
 
 }
 
 }
تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم( ضرب اعداد صحیح)
عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در
هنگام جمع کردن ، تفریق کردن، یا انجام اعمالdivide 10 ^ m ،
rem 10 ^m یا ×10 ^ m. هر یک از این اعمال را m بار انجام می دهد.
اندازه ورودی: n ، تعداد ارقام هر یک از دو عدد صحیح.

به ازای n > s که n توانی از 2استW ( n ) = 4 W (n / 2) + cn
W ( s ) = 0

W ( n ) Є θ ( n² )

ضرب اعداد صحیح بزرگ 2











 
  large_integer prod2 (large_integer u , large_ integer v)
 
 {
 
 large_integer x , y , w , z , r , p , q;
 
 int n , m;
 
 n = maximum (number of digits in u,number of digits in v);
 
 if (u = = 0 || v = = 0)
 
 return 0 ;
 
 else if (n < = threshold)
 
 return u × v obtained in the usual way; 
 
 else {
 
 m = Į n / 2 ⌡;
 
  x = u divide 10 ^ m ; y = rem 10 ^ m; 
 
 w = v divide 10 ^ m ; z = rem 10 ^ m;
 
 r = prod2 (x + y, w + z );
 
 p = prod2 ( x , w )
 
 q = prod2 ( y , z );
 
 return p ×10 ^ 2m + ( r – p – q ) × 10 ^ m +q ; }
 
 }

تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم( ضرب اعداد صحیح2)
عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در
هنگام جمع کردن ، تفریق کردن، یا انجام اعمالdivide 10 ^ m ،
rem 10 ^m یا ×10 ^ m. هر یک از این اعمال را m بار انجام می دهد.
اندازه ورودی: n ، تعداد ارقام هر یک از دو عدد صحیح.

به ازای n > s که n توانی از 2است
3W(n/2)+ c n <=W (n) <= 3W (n / 2 +1) + c n
W (s) = 0
W (n) = θ (n ^ 1.58