Talk:Multiplication algorithm

From Wikipedia, the free encyclopedia

Contents

[edit] Example in Objective Caml

The example given is I'm sure great, but I have no idea what caml is, and it's kinda confusing to read. A C or pseudocode example would convey the meaning of the code far more clearly to the majority of the reader base. Could someone translate the example to C/Pseudocode for us? AdamSebWolf 09:09, 30 May 2006 (UTC)

[edit] Article needs attention tag

I've excerpted the following comment made at Wikipedia:Pages needing attention/Mathematics concerning this article:

The article … contains a false statement: "The fastest known method based on this idea was described in 1971 by Schönhage and Strassen (Schönhage-Strassen algorithm) and has a time complexity of Θ(n ln(n) ln(ln(n)))". (About multiplying long integers - Θ(nln(n)) is evidently enough). The part "A simple improvement to the basic recursive multiplication algorithm..." contains warmup example and shouldn't be in the end. Discussion about complexity is mixed with the discussion about rounding errors and the GIMPS project. (Unsigned entry at 08:06, May 10, 2005 (UTC) by 212.193.10.2. Paul August ☎ 18:54, Jun 5, 2005 (UTC))

Some of the above user's comments may no longer apply because of subsequent edits, but I thought I would copy this here for the editors of this page to consider. Paul August ☎ 19:28, Jun 5, 2005 (UTC)

To be more clear, the commentor above was the same person who added the "article needs attention" msg. So if we think all of that persons issues have been adequately addressed then, we can remove the tag, and it's entry on Wikipedia:Pages needing attention/Mathematics. What concerns me most is the alleged factual error. I don't know enough to confirm or fix this. Paul August ☎ 19:48, Jun 5, 2005 (UTC)

In fact the article is correct, the complexity of S-S multiplication is O(n log n log log n), and is the best known. Often FFT multiplication is quoted as having complexity O(n log n), because it is assumed the "double" data type on a computer is sufficiently accurate to perform the convolution (which is almost always true in practice). In fact, when you take into account the number of bits needed of the base data type to guarantee sufficiently small error, FFT multiplication has complexity O(n log^2 n).--Luke Gustafson 07:24, 1 January 2006 (UTC)

After reviewing the article thoroughly I removed the attention tag and removed it from articles needing attention. (I'm a little new to these sorts of procedures so hopefully this was done appropriately.)--Luke Gustafson 07:37, 1 January 2006 (UTC)

[edit] Number theoretic transform

Is it correct to say the finite field should have at least characteristic m ? -- Nic Roets 12:24, 21 July 2005 (UTC)

I believe (although I haven't actually seen the NTT algorithm) that the characteristic needs to be larger than possible values of the convolutions-- 2^w+1 I think.--Luke Gustafson 07:31, 1 January 2006 (UTC)

[edit] Hardware

Note that it's possible to implement any of these in Combinatorial logic hardware. Is there a reference to show that long multiplication is the dominant implementation in silicon ? -- Nic Roets 12:22, 21 July 2005 (UTC)

[edit] Long Multiplication

Seems like a more thorough walkthrough of long multiplication should be given, to parallel the long division article. The example doesn't explain the process at all.

Is there a corresponding "short multiplication"? — Omegatron 03:36, 29 November 2005 (UTC)
I think the name 'long multiplication' was given to distinguish it from multiplication that uses tricks such as lookup tables -- Nic Roets 11:12, 12 August 2006 (UTC)
Should the algorithm be labeled as "fairly accurate"? The algorithm is accurate and will produce a correct answer if used correctly. Any algorithm is subject to operator error -- EconProf86 19:09, 1 July 2007 (UTC)

[edit] lattice multiplication

the lattice isn't explained very well. it should also be converted into an image, like this: http://online.edfac.unimelb.edu.au/485129/wnproj/multiply/images/lattice4.gif

I started to convert it to table markup, but then saw that the examples on other sites draw diagonal lines. it might be possible to draw it in tex, too? but an image is probably the best method. — Omegatron 03:32, 29 November 2005 (UTC)

[edit] Karatsuba

I thought this section could use more references and more in the way of practical application -- what ranges it's efficient in and so forth. Since the section was already too long, I spun this out into its own article: Karatsuba multiplication. As a result, I've shortened the explanation here by making the example less explicit and technical and removing the Objective Caml example (both of which were moved over). CRGreathouse (talk • contribs) 00:13, 12 August 2006 (UTC)

[edit] Lower bounds?

Are there proven lower bounds on how long any general multiplication algorithm of n-bit numbrs must take? It's trivially Ω(n), and S-S shows it's O(n log n log log n), but are any better bounds known? CRGreathouse (t | c) 03:42, 22 September 2006 (UTC)

[edit] FFT

Can someone explain why this is true (in the section regarding FFTs): "We choose the largest integer w that will not cause overflow during the process outlined below. Then we split the two numbers into groups of w bits"?

I haven't messed around with my own examples (and I'm only in high school, so I probably am just missing a point somewhere), but why does it make sense to have the integer w be the size of the groups? Shouldn't the size of w be the size of the groups?

The most watered down example I could come up with to prove this (to myself) is this: Say we want to do FFT multiplication to multiply 6 by 9 (I know this is pointless in actuality, stick with me), the largest integer w that will not cause overflow is 3. The size of 3 in bits is 2, but we are going to group the numbers into 3 bit pieces, with a maximum value for each of 7. Would 7 not cause errors due to overflow?

I just think there's one or two words amiss in the quoted text; but, again, I don't really have a clue what I'm talking about (dd you notice? :D) — KyleP 07:33, 24 February 2007 (UTC)