Talk:Multiplication algorithm

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)

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)

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)

Details can/could be found in Nussbaumer's Fast Fourier Transform and Convolution Algorithms, if anyone has the time to spare. I might double back an add something on NTTs at a later date. Polynomial transforms probably also deserve a mention, I've used them to avoid the rounding error problems mentioned alongside the NTT reference. 118.208.79.170 (talk) 10:47, 6 April 2009 (UTC)

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)

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)

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)

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)

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)

I think the article summary should list the lower possible/known bounds. ~ Booya ^Bazooka 14:46, 17 November 2010 (UTC)

Furer's algorithm is asymptotically better than S-S. I'm not aware of any nontrivial lower bounds on serial multiplication - however multiplication is known to lie outside of AC⁰, meaning it can't be solved with bounded fan-in constant-depth logical circuits, because there is a constant-depth reduction from parity to multiplication, and parity is not in AC⁰ (see e.g. [1]). This is the best lower bound I know of, and I will add it. Dcoetzee 23:21, 19 November 2010 (UTC)

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)

Hi Kyle - the short answer is, w is already a size in bits, not the number of values possible for each group, which would be 2^w. I don't quite follow your example but this may be your source of confusion. Dcoetzee 08:37, 7 April 2009 (UTC)

I think there might be a slight mistake in the convolution equations: in the double sum after the 2nd '=' sign k goes from 0 to 2m and i from 0 to k which means we multiply for example a_0 and b_2m while b only have m values. Or am I wrong somewhere? —Preceding unsigned comment added by 46.116.195.141 (talk) 17:16, 14 February 2011 (UTC)

Oops, just realized it's defined as 0 later on. sorry. —Preceding unsigned comment added by 46.116.195.141 (talk) 17:18, 14 February 2011 (UTC)

Leonardo

There is reference to a Leonardo but there is no acute way of knowing who Leonardo really is. 129.32.94.123 (talk) 17:43, 19 February 2010 (UTC)

Leonardo was the author Fibonacci's first name. Dmcq (talk) 18:19, 19 February 2010 (UTC)

Quarter square multiplication and recurrence relations

I have in mind putting in something about this, but first I thought I should put it up for comment, both to get it debugged and to allay any objections about original research (it isn't original, but I can't remember where I came across it, so I had to redo it - and it does seem obvious once you see it). Read on...PMLawrence (talk) 14:11, 11 March 2011 (UTC)

With qs the quarter square function on integers (rounded down), then because we have $qs(x+y)-qs(x-y)=xy$, putting $x=n-r$ and $y=r$, we get a family of recurrence relations $qs(n)=qs(n-2r)+nr-r^{2}$ for each r. In general this would involve more multiplications, but we can choose r to make those convenient, say powers of 2 so that the multiplications can be done by repeated doubling. Then it is convenient to work out values of qs(n) using a suitable subfamily of the recurrence relations, e.g.:-

$qs(n)={\begin{cases}qs(-n)&{\text{if }}n<0\\0&{\text{if }}n=0\\0&{\text{if }}n=1\\qs(n-2)+n-1&{\text{if }}2\leqslant n<4{\text{ (matching }}r=1{\text{)}}\\qs(n-4)+2n-4&{\text{if }}4\leqslant n<8{\text{ (matching }}r=2{\text{)}}\\qs(n-8)+4n-16&{\text{if }}8\leqslant n<16{\text{ (matching }}r=4{\text{)}}\\qs(n-16)+8n-64&{\text{if }}16\leqslant n<32{\text{ (matching }}r=8{\text{)}}\\qs(n-32)+16n-256&{\text{if }}n\geqslant 32{\text{ (matching }}r=16{\text{)}}\end{cases}}$

... or using more or fewer members of the family, or using tabulated values of qs for more than just n = 0 and n = 1. (Clearly, if only the recurrence relation for r = 1 is used, there is no multiplication needed to evaluate qs at all, but then multiplying using qs resembles multiplying using repeated addition. In particular, it is slow for most multiplications.)

I really can't see how anyone could ever have got any gain from using this, so I would need to see a citation which also mentioned it helping with multiplication. Dmcq (talk) 14:38, 11 March 2011 (UTC)

The gain comes from not needing such a large table as the straight look up method, while still being reasonably fast. Code would typically be a function using a (much smaller) table of number of times to double (doubling by adding) and the amounts to subtract ($r^{2}$), read off against the values of r, highest first, and would drop through looking for the first recurrence relation to use. It would then use n, those values, and a recursive call to get the result. The base case would be a small, direct look up table it would hit if no number were found (just two entries in the example above). Alternatively, even those values could be calculated rather than looked up, which is slightly slower but more flexible. But what does the gain have to do with it, anyway? PMLawrence (talk) 00:04, 12 March 2011 (UTC)

The gain has to do with citation in an article about multiplication. I didn't see it gained anything useful so I asked for a citation because it seemed unlikely to me that anyone actually even contemplated using this recurrence in the context of multiplication. It still seems extremely unlikely so yes you definitely need a citation and your assurance you saw it somewhere is not enough. Dmcq (talk) 00:25, 12 March 2011 (UTC)

And there I was thinking you were asking what using quarter square multiplication, you know, gained from being evaluated this way - since you did write "I really can't see how anyone could ever have got any gain from using [emphasis added] this". Are you sure you aren't simply shifting your position? But clearly citation isn't necessary for certain levels of discussion, as that section already contains "A simple algebraic proof shows that the discarded remainder would have canceled [sic] when the final difference is taken, so no accuracy is lost by discarding the remainders". So how about "A simple algebraic proof shows that quarter squares can also be evaluated conveniently using recurrence relations", at least to be going on with? If I don't give readers any more useful - i.e. more detailed - information, that will be both true and easily verified, by the standards of the section. Or would you regard that as a challenge to delete that necessary part of the table method, since the cited reference doesn't actually cover that, even though it is necessary for completeness? In any case, it strikes me that providing the level of detail I suggested is obvious once you notice the recurrence relations, and is really only for illustration. I don't see why it should be contentious, since it is so easy to confirm its behaviour (though I put it up here partly so as not to have to debug it myself while I was still so close to it). PMLawrence (talk) 03:00, 12 March 2011 (UTC)

The relevance to multiplication hasn't been shown. It is missing a citation. And it is big. There is no good reason to include it and good reasons not to. Dmcq (talk) 08:44, 12 March 2011 (UTC)

Huh? The section itself shows the relevance of quarter squares to multiplication, and this is clearly relevant to quarter squares (by the way, when I first heard of quarter square multiplication, it was described as a method the Romans used, with look up tables; with their notation, I wouldn't be surprised if they used the r = 1 recurrence relation to build up their tables rather than actually calculating the entries individually - and that, I freely admit, is the sort of speculation about historical fact that would need a citation to justify going in the section, but I mention it here simply to show that there is nothing prima facie unlikely that people would ever have used recurrence relations to evaluate quarter squares, or prima facie absurd and unhelpful about referring to recurrence relations in this section). You have not addressed my interim suggestion of a brief mention with the same level of citation as a comparable sentence already in there, and you have not addressed the reasons I gave for thinking that a free standing source is not so necessary in this case (i.e., that the level of detail is only for completeness/purposes of illustration and can easily be verified without needing outside references, since the principle is covered by my interim suggestion above - it's not as though verification would need readers to conduct a laboratory experiment or anything like that). While the particular illustration I canvassed above is "big", that's only how it appears on screen with images enabled - it's actually only an ordinary paragraph of notation between two shorter ones that are mostly text; and this current exercise is about seeking constructive criticism, so would you be happy if I suggested a briefer illustration or if you tried your hand at one yourself? And I thought I gave good reasons for including something along these lines, if not precisely the draft above (at any rate, so far you have not addressed the reasons I gave, showing whether they were good or bad and why but only that you did not agree with them - which is no proper test of "good", in this sense), while I have yet to see your reasons, good or otherwise, for not doing so. That is, I have seen your stated conclusions, but no reasons over and above being "big" and a lack of citation, but you can't mean those in your paragraph just there as that would be double counting (that you don't see a gain is not a reason in itself but a statement of your position, a conclusion you have come to). PMLawrence (talk) 11:19, 12 March 2011 (UTC)

Just because quarter squares are relevant doesn't mean this recurrence is. Please just follow the WP:5P. We're supposed to find things which are halfway notable written about in reliable sources and summarize what's written about them. You really need a reliable source if you want to take this any further. Dmcq (talk) 23:46, 12 March 2011 (UTC)

Again, huh? By that standard, much of what is in this section shouldn't be in there. You have failed to address any of my specific points bringing this out. In particular, you have failed to state any reasons not to go with this, in the sense of specific reasons of the sort I asked for. So, I'll start again. Unless I soon receive specific reasons not to, or constructive criticism suggesting alternatives, in the near future I shall put in an interim entry roughly like this: "A simple algebraic argument shows that quarter squares can also be evaluated using recurrence relations, $qs(n)=qs(n-2r)+nr-r^{2}$. This is fast for large r, and easy when r is a power of 2 as the multiplications of n reduce to doubling by repeated addition and drop out completely in the simplest, slowest case.". I believe only the first sentence is strictly necessary for this matter, and it meets the standards already followed in this section, but the second sentence is necessary to clarify its usefulness. Even so, a fuller illustration would be better, and I would welcome any constructive criticism offering that. PMLawrence (talk) 03:04, 15 March 2011 (UTC)

And I'd remove it citing WP:Original research. I do not believe this is a basis for a good algorithm, and I don't believe it has ever been used or written about in this context. Dmcq (talk) 10:04, 15 March 2011 (UTC)

You have given a strong indication that you are not acting in good faith. Now that I have provided references - you are claiming that the particular use proves that the material does not belong here. You are inventing objections on the fly rather than carrying out constructive criticism to provide helpful suggestions, you are failing and refusing to provide specific objections so I can see how to address them, and when I meet your general and generic objections you claim - irrelevantly as well as incorrectly - that those links make that material more specific to something else and thus irrelevant here. But not only is that wrong - about it being irrelevant - it misses the point about how encyclopaedias work. If that material were carefully confined in a different article, the article on multiplication would be missing stuff on how that is achieved. I believe I have given plenty of leeway, asked for constructive criticism in advance, met and more than met your stated objections insofar as you have condescended to reveal them, and now been confronted with an objection invented after the fact that was not among any objection given before and is anyway both unfounded and irrelevant. In all the circumstances I feel justified in asking for arbitration, since I have gone out of my way to avoid the necessity without success. Feel free to offer constructive criticism while we wait, if you can bring yourself to it (but note that putting this "how" stuff elsewhere does not help this article). PMLawrence (talk) 03:35, 20 March 2011 (UTC)

I would say this is a perfectly adequate section, as long as the references are appropriately set up. I haven't seen this analysis before and wouldn't know where to go to look for it, and until I get the latter I wouldn't be happy about this section going in - but the work itself looks fine. --Matt Westwood 23:07, 20 March 2011 (UTC)

The article is about multiplication algorithms. The 'recurrence relations themselves are no more than a dressed up version of (a+b)²=a²+2ab+b² and hopefully you would have seen an 'analysis' of that somewhere or be able to figure out where to go for it. They are not used in quarter square multiplication. As I have said to the person the references could be used in the mathematical table or human computer article as these are about table construction. However particular methods of table construction do not belong here and the recurrence relations as given here were not used in table construction anyway and have never appeared in the literature as far as I'm aware for any purpose. Dmcq (talk) 08:32, 21 March 2011 (UTC)

Construction of tables

The justification for a section about recursive generation of the quarter suares was that it was used in the table generation.

That is absolutely false. The fact is, you asked for a reference showing that recurrence relations were in fact used. I provided more than one relevant citation. However, that is not the justification for mentioning it, that is, the thing that makes it relevant. It is relevant because it shows how to obtain conveniently the things quarter square multiplication uses - the values of the quarter squares. Bluntly, this is not about table construction, it is about quarter square multiplication, and the reference to using this approach to construct tables was solely and simply to satisfy you in your asking for a reference to a real situation in which this approach was used. That does not turn it into something that only matters to table construction, it meets your demand for a demonstration of usefulness. That does not make it useless for anything else; by that Morton's Forkish reasoning, if I don't give you a citation I can't make the edit, and if I do I must not make the edit. PMLawrence (talk) 03:35, 20 March 2011 (UTC)

The method was a standard one in the pre-computer era. It doesn't have anything to do with multiplication as such so I removed it.

By that logic, most of that section should be removed. However, as I have just pointed out, it is indeed relevant to multiplication because it shows how to obtain conveniently the things quarter square multiplication uses - the values of the quarter squares. If you don't believe me, read Samuel Laundy's own words in a report to the Institute of Actuaries, in their magazine I cited: "THE paper which I have the honour to submit is so elementary in its details that I have to claim the indulgence of the meeting; but, as the practical application of the simple formulæ to which I shall have occasion to refer may be interesting, I trust I may not unworthily occupy a short portion of your time. A few months ago it occurred to me that tables to facilitate the process of multiplication, based upon the identity would be of extensive use in actuarial and other calculations, and would effect a considerable saving of labour—to an extent even greater than that acquired by the use of logarithms... Before proceeding to explain the use of the tables, I may be allowed to refer to the process by which they have been computed. To form each value separately by multiplication would require an amount of labour that few would voluntarily undergo : but considering the fact that the squares of numbers beginning from unity may be found by the successive addition of a constantly and uniformly increasing difference, it is evident that every tabular number may be found from that preceding it by the process of addition... But the computation from No. (2000) and onward can be more conveniently continued by a modification of the above method..." Mr. Laundy, himself, pointed out the relevance of the method of construction, and the Institute of Actuaries was willing to accept that in the report. PMLawrence (talk) 03:35, 20 March 2011 (UTC)

A bit more in the article human computer about how they were used to compute tables would be useful I think.

While that would help that article, it fails to help this one, which would - as I have shown - benefit from the presence of material in this area. PMLawrence (talk) 03:35, 20 March 2011 (UTC)

It should be based on what's written about how to divide up the work between multiple computers. The method here is a slight variation on what a difference engine normally does and could be done by one by having two extra digits which are ignored and of course they worked in decimal. Dmcq (talk) 14:22, 19 March 2011 (UTC)

Please do not split up peoples contributions this way. You are not replying to an email. You can quote a bit of what a person says if it is not obvious from your reply.

If you can point to other parts of this article which are not directly pertinent to multiplication algorithms please do so.

Computing the quarter squares is no problem. You just square, divide by four and discard te remainder as explained in the article. What was being described by Samuel Laundy was the standard technique to generate tables and is relevant to human computer or mathematical table. It isn't relevant here. And sticking in your own formula and saying Laundy used a variant of it isn't exactly following WP:Reliable sources either is it?

I guess from what you are saying you don't feel like trying to improve human computer or mathematical table and want to continue here instead. I have said my piece a couple of times and doubt saying it again is a terribly useful occupation so I shall raise this at Wikipedia talk:WikiProject Mathematics#Quarter squares. Dmcq (talk) 13:07, 20 March 2011 (UTC)

Linear time multiplication

I think there is an error in the section "Linear time multiplication". In the reference, Knuth discusses that in the model described in this article, multiplication can be done in O(n log n), not O(n). After that he leaves as an exercise to prove that in the pointer machine model it can be done in O(n). — Preceding unsigned comment added by 181.28.64.87 (talk) 04:15, 28 August 2012 (UTC)

Cheprasov Algorithm

There seems to be some edit warring about this. Please discuss on this talk page first if still insistent on including it.

Personally I see no reason to include it at present. There does not seem to be any general interest that I can see. Also if there was some interest I believe mental calculation would eb more appropriate.

As to the actual system as described personally I think it is silly. I can make up better myself in a couple of minutes, for instance using the symbolism there

$A=(t_{1}-u_{1})\times (u_{2}-t_{2})$

$B=t_{1}\times t_{2}$

$C=(u_{1}\times u_{2})+t_{u_{1}\times u_{2}}$

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle D= (A+B+C) @ u_{u_1 \times u_2}}

Failed to parse (syntax error): {\displaystyle \operatorname{Answer} = (B+\operatorname{hundreds of} D)@\operatorname{tens and units of} D}

Which also possibly has negative numbers and adds up to something positive. I don't specially feel inclined to write a book about that though. Dmcq (talk) 12:02, 4 January 2013 (UTC)

I agree with Dmcq. One can remark that the algorithm presented by Dmcq is well known (up some changes of signs) as Karatsuba algorithm, and has the great advantage to use only 3 multiplications of digits instead of 4 in the classical algorithm and in the so called "Cheprasov Algorithm". D.Lazard (talk) 12:53, 4 January 2013 (UTC)

Yes, the proposed algorithm has no particular advantages in time complexity or for mental calculation, which is precisely why it hasn't gotten published in any peer-reviewed venue. Dcoetzee 05:56, 5 January 2013 (UTC)

justification for taking remainders in quarter squaring

IMO the explanation

If x+y is odd then x-y will also be odd, this means any fraction will cancel out so no accuracy is lost by discarding the remainders.

is not valid as it stands. It is not immediately obvious (without "writing out" (2n-1)²=4n²-4n+1) that the remainders could not add up their effects rather than cancel out; at least the argumentation much be changed. I'd rather suggest

We know that the result is an integer, so any possible fractional part of +/- 1/4 in either (x+y)²/4 or (x-y)²/4 (in case the squares are of the form (2n+1)²=4n²+4n+1) must necessarily cancel.

This argumentation leads (IMO) more obviously to the correct result. — MFH:Talk 14:40, 19 March 2013 (UTC)

The statement is true. You never get a -1/4 remainder when squaring. It isn't a textbook and checking is fairly easy for a reader if they want to do so. Dmcq (talk) 18:01, 19 March 2013 (UTC)

A possible memory trade for time gaining 4 the common O(N*N) multiplications

i think there is a chance that purely creative paradigm approaching way of 1->K data length extrapolation could lead us to an algo that is derived from common algo O(N*N) n that is kinda trading memory O(N) complexity 4 an Sqrt(N) time factor demultiplied from N*N time complexity. Take this as a challange... it looks to me that idea can not b (at least not easily) extrapolated for recursivity so better algo using this only suggested idea seems harder to b obtained. Good Luck, Yankees !! Florin Matei, Romania. 93.118.212.93 (talk) 14:15, 5 May 2013 (UTC)

ok, purely creative part 4 finding similarities with quicksort paradigm

qsort might use small sorting in order to partitionate the datas practically forcing some D&C solution, i wonder if there is a similary idea 4 multiplyings: heres the pure creative aproach: we got a rectangle we know the lengths of the edges but we dont know its surface (probably surface area) we might use some both sides splitting in such a way that we might b forming a square or...(a more "docile" rectangle) ... the formed square might help as using algebra taking advantages of its equals borders... its not quite easy to get this to an end but, again, it might worth a try. Florin Matei, Romania... 93.118.212.93 (talk) 17:16, 13 June 2013 (UTC)

I don't understand what you are saying. I think you are proposing some of your own ideas. We only put things into articles which have been written about in books and magazines and suchlike and not editors own ideas. See WP:Verifiability. Dmcq (talk) 18:36, 13 June 2013 (UTC)

wow: thats a cold war specialist talking, but i agree u got some of ur own policy: we got ours, too bad my ideas r working ha?93.118.212.93 (talk) 20:36, 13 June 2013 (UTC)

take these a a homework, please, y not some credits 4 me anyway?

n*log(n) muls or even better

wow, im sorry lets say we want to multiply a1 n b1, to avoid confusion a1*b1=m*m-n*n; m*m =(m1;m2)*(m1;m2) , m1 the most significant part m1=3*a+b, m2=3*b+a, computing m1*m1, m2*m2 n m1*m2 from "autosolve". good luck n dont forget credits, ok?? Florin Matei, Romania 93.118.212.93 (talk) 19:16, 6 December 2012 (UTC)

   What exactly are you trying to say? What is "autosolve"? The idea to reduce multiplication to two squarings is old. How is 3a+b the most significant part of m? What is m? Usually one would take m=(a+b)/2 and n=(a-b)/2. m=3a+b would require n=3a-b to cancel the squares, then m*m-n*n=12*a*b. How do you propose to achieve the squarings? Using Karatsuba? Do you resolve the mixed scale multiplication again to a difference of two squares? What is the complexity relation, that is, how is T(2n) expressed in terms of n and T(n)? n*log(n)-Multiplication is Schönhage-Strassen, an algebraic variant of the FFT. Did you check that?--LutzL (talk) 12:35, 7 December 2012 (UTC)

   Please study Daniel J. Bernstein: Multidigit multiplication for mathematicians. for an overview of fast multiplication algorithms and ways to communicate them. If the formalism is right, the language doesn't matter that much.--LutzL (talk) 20:16, 19 December 2012 (UTC)

autosolve in a nonexpansive way to compute m1*m2 using the notations m1=3a+b n m2=3b+a, m1, m2 the 2 parts of spilting m (whos m? dont make me laught, u is the one to say idea is old), n the computed values m1*m1 n m2*m2 that works recursively, dont need extra ideas... once we got m1*m1, m2*m2 n M1*m2 we've completed the curent recursivity level by computing m*m... idea is to use a decent sum m1*m1+r*m2*m2 with the notation suggested in order to find m1*m2 (algo main idea) i know its a bit crazy but might evn work n if so then Order is n*log(n)... n dont bother me with master method formulas i practically reinvented it once n way to verify it also :P 93.118.212.93 (talk) 14:47, 2 February 2013 (UTC)

   Please publish a paper, preferably refereed, where you give a detailed description of what happens when in your algorithm, some example and also a detailed account of your reinvention of the "master theorem". But even then this discussion page is not the right place to talk about this fundamentally different "idea".--LutzL (talk) 20:32, 5 February 2013 (UTC)

idk abt the rite place 4 this, apparently is all i can afford it here, not to mention the brain treat... they r doing this 2 me 4 their fun, i guess 93.118.212.93 (talk) 09:29, 9 February 2013 (UTC) Karatsuba idea n estimating MSb mantissa for factorials

i think due to the arithmetic progression of operands n using binary codifyings 4 numbers we could use ideas similary to Karatsuba to multiply in polynomial time a great deal of numbers such as factorials, only for the significant mantissa (n exponent) the details r let to u :) — Preceding unsigned comment added by 93.118.212.93 (talk) 11:53, 2 February 2013 (UTC)

estimating modulus of such product could b possible , anyway, in order for primality tests, but i think i m not able to do that one, not in polynomial time, anyway 93.118.212.93 (talk) 12:00, 2 February 2013 (UTC)

Please stop copying stuff into different talk pages. You have been told what is needed. What you are doing is wasting your time and anybody's who reads this. Please stop. Also if you cannot be bothered to try and write understandably and correctly others will not bother trying to make out what you say. Your time is not worth more than mine. Dmcq (talk) 21:20, 13 June 2013 (UTC)

Who was it above who wrote: "wow, im sorry lets say we want to multiply a1 n b1, to avoid confusion a1*b1=m*m-n*n;" ??? You write "a1 n b1" which actually CREATES confusion, because: 1) That includes the letter n so it looks as if you're multiplying a1 * n * b1 2) You go on to use the letter n in the very next equation

Do you think you could write in NON-CONFUSING English, please? "Let's say we want to multiply a1 and b1 ..." or "Let's say we want to multiply a1 by b1..." 46.64.255.189 (talk) 19:58, 10 January 2014 (UTC)

Ancient Indian algorithm for multiplying numbers close to a round number

What is the complexity of this algorithm? 31.42.233.14 (talk) 15:08, 10 January 2014 (UTC) Like, really unbelievably complex, man! 46.64.255.189 (talk) 19:59, 10 January 2014 (UTC)