Content deleted Content added
No edit summary |
|||
Line 40:
:''Z'' = (12 + 34)(56 + 78) - ''X'' - ''Y'' = 46 ⋅ 134 - 672 - 2652 = 2840
:''X'' 10<sup>2⋅2</sup> + ''Y'' + ''Z'' 10<sup>2</sup> = 672 0000 + 2652 + 2840 00 = '''7006652''' = 1234 ⋅ 5678
==Code Implementation Notes==
4 steps in Our implementation<br>
1- Determine Base (B)<br/>
2- for n-length Integer get (m) here we will assign
m = Int(n/2)
3- here we can get x<sub>1</sub> & x<sub>2</sub> from x so y<sub>1</sub> & y<sub>2</sub> from y
x<sub>1</sub> = x/B<sup>m</sup>
x<sub>2</sub> = x%B<sup>m</sup>
y<sub>1</sub> = y/B<sup>m</sup>
y<sub>2</sub> = y%B<sup>m</sup>
At this point we can calculate
X = x<sub>1</sub>y<sub>1</sub>
Y = x<sub>2</sub>y<sub>2</sub>
Z = x<sub>1</sub>y<sub>2</sub>+x<sub>2</sub>y<sub>1</sub>
and we can from this point evaluate the result:
xy = X.B<sup>2m</sup> + Y + Z B<sup>m</sup>
we can see X, Y or Z as result of two large numbers multiplication
so that we can Use Recursion Here.
<br><br>--[[User:Aigdonia|Aigdonia]] 21:29, 3 November 2007 (UTC)
==Complexity==
If ''T''(''n'') denotes the time it takes to multiply two ''n''-digit numbers with Karatsuba's method, then we can write
| |||