Talk:Karatsuba algorithm
 | Mathematics Start‑class Low‑priority | |||||||||
| ||||||||||
Divide and conquer
The Karatsuba multiplication algorithm, ... in 1960 ... The Karatsuba algorithm can be considered to be the earliest example of a binary splitting algorithm, or more generally, a divide and conquer algorithm.
I think this is wrong. According to Merge_sort, von Neumann invented Merge Sort in 1945. —Preceding unsigned comment added by 84.74.154.5 (talk) 14:11, 23 July 2008 (UTC)
I think, this is an absurd to compare von Neumann Merge Sort and the Karatsuba fast multiplication algorithm. Only after the Karatsuba algorithm the history of fast algorithms began. Such fast processes like AGM method of Gauss, Newton method etc. become FAST only with application of fast multiplication. Von Neumann or anybody else results can not help here. That is why the Karatsuba algorithm can be considered as the frist FAST algorithm in the history of computations.
Rule of thumb
None of the references really talked about any "rule of thumb" I moved those references. I doubt this rule of thumb is any close to truth I think there was a mistake, I think in this case n refers to the operands themselves and not to the number of digits (Cause if Karatsuba's algorithm only got faster after such an insane amount of digits it wouldn't have any practical use) Perhaps this claim should be removed or at least fixed to remove this ambiguity not to mention including an actual reference 200.87.23.227 (talk) 17:35, 8 January 2009 (UTC)
- In fact the references did. GMP uses 32-bit limbs on 32-bit processors, and 64-bit limbs on 64-bit processors. Thus the 10-limb crossover point mentioned in the GMP reference suggests 320 to 640 bit numbers, that is, numbers above 2^320 or 2^640, respectively. The other reference suggest an 800 to 2000-bit x86 crossover point (for numbers above 2^800 or 2^2000).
- CRGreathouse (t | c) 18:43, 8 January 2009 (UTC)
Well, either way the amguity about "n" remains, I will change n to "the operands" —Preceding unsigned comment added by 200.87.23.104 (talk) 17:52, 13 January 2009 (UTC)
Merge from Karatsuba multiplication
Consider merging material from The Karatsuba multiplication, which has some descriptions of variants and some more sources. JackSchmidt (talk) 12:57, 26 February 2009 (UTC)
Calculations in Example
With n=2^10=1024, the formula 3n^(log_2(3)) approx 3n^1.585 evaluates to 177193, not 59049 as claimed in the heading paragraph. Now, I do not know what's wrong, the formula or just the result. Someone might want to look into this issue. Gulliveig (talk) 05:46, 20 July 2009 (UTC)
- Good catch. Looks like the original writer forgot the 3 in front — evaluates to exactly , in fact. Shreevatsa (talk) 06:31, 20 July 2009 (UTC)
- Sorry, but the original number 59049 was correct. Note that the number of single-digit multiplies is at most 3n^(log_2(3)) for general n, but is less than that for many vaues of n. In particular, when n is exactly a power of two 2k, the count is exactly n^(log_2(3)) = 3k, not 3 × 3k. All the best, --Jorge Stolfi (talk) 22:12, 24 July 2009 (UTC)
- Ok, I edited the text to mention this explicitly, to avoid future confusion. Thanks, Shreevatsa (talk) 22:24, 24 July 2009 (UTC)
- Sorry, but the original number 59049 was correct. Note that the number of single-digit multiplies is at most 3n^(log_2(3)) for general n, but is less than that for many vaues of n. In particular, when n is exactly a power of two 2k, the count is exactly n^(log_2(3)) = 3k, not 3 × 3k. All the best, --Jorge Stolfi (talk) 22:12, 24 July 2009 (UTC)
Using B = 10^9
Someone objected to the suggestion of using B = 109 because "multiplication by 109 is not realizable by bit-shifts, so choosing B this way doesn't make sense". Actually multiplication by 109 corresponds to shifting the array of "digits" (each stored in one 32-bit word) by one full word.
This choice of basis for bignum arithmetic may be advantageous when one expects a lot of input/output in decimal. Other similar choices are B = 10000 (each "digit" stored in a 16-bit short word) and B = 100 (each "digit" stored in one byte). The last two choices allow decimal output and input by table look-up, without divisions or multiplications.
All the best, --Jorge Stolfi (talk) 03:02, 12 December 2009 (UTC)
- Sounds interesting, you should add that to the article. Adrianwn (talk) 08:15, 12 December 2009 (UTC)