Content deleted Content added
collapsed the sections containing original research not related to the article |
|||
Line 68:
:And what exactly do you want to tell us by that? Furthermore, could you please explain [http://en.wikipedia.org/w/index.php?title=Karatsuba_algorithm&curid=6395589&diff=368458594&oldid=368191659 this edit]? I reverted a previous, similar edit of yours, because it was unclear and seemed redundant. – [[User:Adrianwn|Adrianwn]] ([[User talk:Adrianwn|talk]]) 05:37, 17 June 2010 (UTC)
==Original research by 93.118.212.93 (Florin Matei) I (collapsed)==
{{cot|Subdivision 1:4 that is not Toom-Cook}}
▲== Further subdivision 1:4 ==
if the operands are 1:4 length they might be a particular form of 4:4 n then we might find better orders for Karatsuba algo (1960) <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 20:54, 25 May 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
Line 79 ⟶ 81:
i think it could b a chance to b a problem oriented on programmer analysts problematic :-) [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 12:52, 13 February 2013 (UTC)
i think that could be possible keeping a O(1) *n loop to count , in O(1) the number
Line 90 ⟶ 92:
sssswell, its not the egiptian algo, maybe bit oriented processing n dynamic programming might achieve O(N) or similary processing time... who knows cz im such poor encoder when it comes to write programmes :( <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 15:15, 2 February 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
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 [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 19:16, 6 December 2012 (UTC)
Line 104 ⟶ 107:
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 [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 09:29, 9 February 2013 (UTC)
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 :) <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 11:53, 2 February 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
Line 110 ⟶ 113:
ok, once n last 4 everybody that wanna challenge this idea: my challenge 2 u is that using bit
Line 124 ⟶ 127:
:This is the general Toom-Cook idea. Please read and understand the paper by Bernstein, as I told You before.--[[User:LutzL|LutzL]] ([[User talk:LutzL|talk]]) 19:09, 9 February 2013 (UTC)
swell, r u sure that Toom-Cook is linear 4 splitting variant k=2, if i rmb well, bcz of those coetients from the system Toom-Cook is not O(N) complexity in any case. my ideas r meant as an iq test also [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 10:07, 10 February 2013 (UTC)
{{cob}}
== How it has been computed? ==
Line 133 ⟶ 138:
However, it doesn't explains the algorithm for compute that. Is there the time for applying long multiplication, or just apply Karatsuba algorithm again to that expression? [[Special:Contributions/31.42.239.14|31.42.239.14]] ([[User talk:31.42.239.14|talk]]) 21:54, 25 February 2013 (UTC)
==Original research by 93.118.212.93 (Florin Matei) II (collapsed)==
== ok, abt some a bit different K idea possible able 4 generalization ==▼
{{cot|Subdivision 1:4 that is not Toom-Cook}}
multiplying A=(a1;a2) with B=(b1;b2) might be planned like this (a1+b1)*(a2+b2), (a1-b1)*(a2-b2), and a1*b1... i think this could challenge Toom-Cook algo, by some K. generalization that use mostly algebraic sums n possibly finding more simplier systems of equation... the algebraic sums to b multiplied that ofer decent agebraig sums of desired coetients might b search evn automatically, by the computer...good luck! (i posted similary tries on Toom - Cook talk page.) [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 10:51, 27 March 2013 (UTC)
Line 141 ⟶ 148:
wedd want the value of the product for some xo=2^k value... we plan to do 3 small multiplications h1(1)*h2(1), l1(1)*l2(1) n (h1+l1)(1)*(h2+l2)(1) but, after obtaining the values (using K. classic algo) we multiply properly with 2^t two of the resulted polynoms action that sooner or later, is expected to ofer the desired results of the multiplication of the two polynoms n aplied to the x0 =2^k value meaning the multiplication is over... time looks pretty appealing, IF its working :) [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 07:06, 28 March 2013 (UTC)
if we have to multiply 2 polinoms but in fact looking 4 their value resulted number obtained for x0= 2^k for the polinom product, we might use as xi, the values that create the system of equations, xi= roots_complex_order_j(1)... j somewhere 1...n, n the numbers of plan partitions: it could help geting a decent system of linear equations thats solves more fast... :) [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 08:21, 28 March 2013 (UTC)
Line 156 ⟶ 164:
this idea could make the difference between O(N^1.59) n O(N*log(N)) by simply redisn the plan of recursive calls of this good idea: basically instead of planning 3 muls of T(n/2) we plan (and that is reffering to the muls of sums) the T(n/2) sum n then the two remaining two T(n/4) sums. i agree there is some terms let 4 autosolve but this doesent yet charge the data stack (hypotetical data stack of some implementention of the algo) n those remaining unconsidered ("yet") terms are expected to become smaller n smaller. practically if the tack grows with N/2+N/4+N/4=N then this small idea could lead us to an O(n*log(n)) time complexity algo. i agree my "demonstration" here is far to b complete, take it as a Russian style problem , if u wish :) Florin Matei, Romania [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 13:12, 14 April 2013 (UTC)
:No, russian style is to leave the solution of a problem to the reader. What you want is to leave the formulation of a problem to the reader. This is crank style. Come back when you have an implementation with demonstrable runtimes.--[[User:LutzL|LutzL]] ([[User talk:LutzL|talk]]) 12:13, 15 April 2013 (UTC)
Line 162 ⟶ 171:
well, another pure creative idea is that observing/remarking first that if we manage to write the master method equivalent for finding O() of Karatsuba algo idea in such way that being possible the following kinda write T(N)=3*(1-p)*T(N/2), p a small percentage of 1 meaning the problem solved first from each of those 3 planned, we might find better O() for K. algo idea... basically insted of planning a mul of T(N/2) we solve a small percentage of that n planning only the remaining (1-p)*T(N/2) claiming we already talk abt a better O()... as a rule of thumb the lil mul n the remaining mul should b equalize in time wasting in order to find a most representative O() [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 05:15, 20 April 2013 (UTC)
if we have to multiply 2 long integers of N bits each, first we might do the multiplyings of first 3*N/4 with first 3*N/4 bits, obtaining recursively a result, then we might do the same for the last 3*N/4 bits multiplied with others operand 3*N/4 bits .we might b remarking that we already got (3/8)*N (first)+ (3/8)*N (last) required bits of the result now we might b focusing on the middle of the operands (pretending that at the middle of operands there is some aiding hypotethic floating point)... at a summary view in order to get a clue abt master method equation, i got 8^alfa=2*6^alfa ... [[Special:Contributions/93.118.212.93|93.118.212.93]] ([[User talk:93.118.212.93|talk]]) 13:42, 26 May 2013 (UTC) Florin Matei, Romania
{{cob}}
== "Invented by Karatsuba" ==
| |||