20110828, 17:11  #45  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
Quote:


20110909, 14:17  #46 
May 2011
FR Germany  Berlin
1110_{2} Posts 
Thank you!
I found the fitting keyword for me: "Set Theory". Will go w/ "Goldrei, Derek (1996), Classic Set Theory, London: Chapman and Hall, p. 3, ISBN 0412606100" ... Cheers, ciic.  P.S.: "Them ain't Bagels, they doughnuts": See http://en.wikipedia.org/wiki/Bagels , please. "PS Can't fool me: there ain't no sanity clause." : 't me either! 
20110909, 16:00  #47  
Nov 2003
1D24_{16} Posts 
Quote:


20111106, 20:46  #48 
Nov 2011
2^{2}·3 Posts 
I found an algorithm for polynomial multiplying. The algorithm is relative to FFT and has a simple explanation. Is anybody interesting?

20111107, 02:20  #49 
Romulan Interpreter
Jun 2011
Thailand
17·19·29 Posts 
I am confused here. Did you find an algorithm to multiply polynomials (in whatever complexity time) or did you find an algorithm to multiply integers in polynomial time?

20111107, 02:43  #50 
Dec 2010
Monticello
5×359 Posts 
Let's have it, with a small example. Be mathematically precise in the sense you mean it...and post in the homework thread, since your post (and my reply) is offtopic, and it will draw fewest flames there.

20120129, 18:36  #51 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3·1,951 Posts 
I have been fiddling around trying to make small FFTs optimal. Here is my psuedo code for 4x4 multiplication using FFT.
Input: (a,b,c,d,0,0,0,0)*(e,f,g,h,0,0,0,0) FFT: Code:
brt=b*1/sqrt(2) drt=d*1/sqrt(2) mtmp1=a+c mtmp2=b+d mtmp3=brtdrt mtmp4=brt+drt m1=mtmp1+ntmp2 m2=a+mtmp3 m3=c+mtmp4 m4=ac m5=bd m6=amtmp3 m7=cmtmp4 m8=mtmp1mtmp2 frt=f*1/sqrt(2) hrt=h*1/sqrt(2) ntmp1=e+g ntmp2=f+h ntmp3=frthrt ntmp4=frt+hrt n1=ntmp1+ntmp2 n2=e+ntmp3 n3=g+ntmp4 n4=eg n5=fh n6=entmp3 n7=gntmp4 n8=ntmp1ntmp2 The multiplication can be done by: Code:
r1=m1*n1 r2=m2*n2m3*n3 r3=m4*n4m5*n5 r4=m6*n6m7*n7 r5=m8*n8 r6=m2*n3+m3*n2 r7=m4*n5+m5*n4 r8=m6*n7+m7*n6 Inverse FFT: Code:
tmp1=(r1+r5)/8 tmp2=r3/4 tmp3=tmp1+tmp2 tmp4=tmp1tmp2 tmp5=(r2+r4)/4 tmp6=(r6+r8)/4 tmp7=(r1r5)/8 tmp8=r7/4 tmp9=tmp7+tmp8 tmp10=tmp7tmp8 tmp11=(r2r4)*sqrt(2)/8 tmp12=(r6r8)*sqrt(2)/8 output1: tmp3 + tmp5 output2: tmp9 + tmp11 + tmp12 output3: tmp4 + tmp6 output4: tmp10  tmp11 + tmp12 output5: tmp3  tmp5 output6: tmp9  tmp11  tmp12 output7: tmp4  tmp6 output8: tmp10 + tmp11  tmp12 Total for 4x4 multiplication by FFT is 26 adds, 26 subs, 20 muls and 6 shifts. This is 78 operations which is slightly less than the 10*N*log2(N) estimate of 80. Can anyone see any mistakes or any improvements? I am going to move onto 8x8 multiplication next. 
20120129, 20:58  #52 
∂^{2}ω=0
Sep 2002
República de California
3·5^{3}·31 Posts 
Without delving into your code in much detail, several general notes:
1. You need to be clear what type of transform you are working on  realvector, complex, modular, what? (It seems from your examples you intend a realsignal covolutionbased multiply, is that right? 2. You should never use 1/sqrt(N) normalizations  just apply 1/N during the final normalizeandcarry step on the convolution outputs. 3. "Shifts" are not an option on most floatingpoint hardware. What you call shifts should instead be mulsbyinversepowersof2, should never appear explicitly. These should be absorbable into the other multiplicative constants appearing in the algorithm. 4. You need to think about whether this kind of smalltransformoptimization approach will generalize well to larger signal lengths. It appears to be useful for the smallDFTs surrounding the dyadicmul step, but large FFTs will need moregenericradix passes (mostly small powers of 2, perhaps one oddradix pass per fFFT and iFFT) preceding and following the dyadicmul step. Those will have variable strides, and need to accommodate array accesses with varying strides, as well as complex "twiddle" muls. 
20120130, 00:39  #53  
Nov 2003
2^{2}×5×373 Posts 
Quote:
for various domains. 

20120130, 00:58  #54  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3×1,951 Posts 
Quote:
Quote:
Quote:
Quote:
I realize that the optimisations will get more complex. With a length 8 FFT E was 1/sqrt(2)+1/sqrt(2)*i and real(E)=im(E). With higher powers real(E)!=im(E). The code above worked once I had changed m1=mtmp1+ntmp2 to m1=mtmp1+mtmp2. I have gleaned most of my information on ffts from this thread. I have studied basic linear transformations at uni but nothing like this. I am currently half way through my first year studying maths at Leicester University. I will look at this again tomorrow. Need to get to sleep 

20120130, 20:40  #55  
∂^{2}ω=0
Sep 2002
República de California
3·5^{3}·31 Posts 
Quote:
Quote:
Quote:
Once one needs to get seriously efficient one alno needs to support nonpowrof2 intermediate runlengths, e.g. n=80, which one could do via radix [5,16] or [8,10] combos. That gets nontrivial because one needs to consider how to generalize the concept of "bit reversal reordering" to auch runlengths. But you seem like you're on the right track, so let us know how things go. Last fiddled with by ewmayer on 20120130 at 20:42 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Any technology you guys are excited about?  jasong  Lounge  31  20151009 20:55 
These dell guys can't possibly be serious...  Unregistered  Hardware  12  20061103 03:53 
You guys are famous  jasong  Sierpinski/Riesel Base 5  1  20060322 01:06 
Hi guys !  Crystallize  Lounge  6  20030927 13:08 
How do you guys do this?  ThomRuley  Lone Mersenne Hunters  1  20030529 18:17 