- **Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=8*)

- - **low-value comments cleared out of FFT thread**
(*https://www.mersenneforum.org/showthread.php?t=16214*)

low-value comments cleared out of FFT thread[QUOTE=LaurV;277395]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?[/QUOTE]
Polinomials: C(x)=A(x)*B(x). And it may be used for integer multiplication. FFT does the same. |

[QUOTE=Christenson;277396]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 off-topic, and it will draw fewest flames there.[/QUOTE]
In the homework? No. :) |

[QUOTE=Maximus;277399]Polinomials: C(x)=A(x)*B(x). And it may be used for integer multiplication. FFT does the same.[/QUOTE]
Ok. Now let's be a little more clear. Multiplying polynomials is always max quadratic in the number of terms. That is, if the polynomials have degree n, then you do maximum about n^2 multiplications. If one polynomial is degree n and one is degree m, then you do maximum (n+1)*(m+1) multiplications. Some algorithms as Karatsuba or else, will do less multiplications. So, multiplying polynomials requires a "polynomial" number of steps. But each step could be exponential inside, if the coefficients are huge numbers (multi-precision)... I would be very surprised if you found an algorithm to multiply polynomials that can be used to multiply integers in polynomial time. I really doubt. Please note that [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods"]FFT multiplication[/URL] is NOT polynomial. Its order is still (sub)exponential. Maybe you found something like [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Linear_time_multiplication"]this[/URL], that could require a polynomial time, but it would require an exponential space. The best algorithm should be the one that make a good compromise between the time and the space. |

[QUOTE=LaurV;277405]I would be very surprised if you found an algorithm to multiply polynomials that can be used to multiply integers in polynomial time. I really doubt. Please note that [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods"]FFT multiplication[/URL] is NOT polynomial. Its order is still (sub)exponential. [/quote]
:huh: FFT is nlogn which is decidedly polynomial. And, the basis of FFT multiplication is polynomial multipoint evaluation (followed by pointwise multiplication) [QUOTE=LaurV;277405]Maybe you found something like [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Linear_time_multiplication"]this[/URL], that could require a polynomial time, but it would require an exponential space. [/QUOTE] :huh: :huh: If you require exponential space, then you need to read/write all those exponential space, and therefore your algo is exponential time. |

"requires that any memory location can be accessed in constant time"
Now admittedly, that also requires a multiplication look up table of significant size, which, when counted with the actual multiplication, would create an exponential algorithm |

[QUOTE=LaurV;277405]Ok. Now let's be a little more clear. Multiplying polynomials is always max quadratic in the number of terms. That is, if the polynomials have degree n, then you do maximum about n^2 multiplications. If one polynomial is degree n and one is degree m, then you do maximum (n+1)*(m+1) multiplications. Some algorithms as Karatsuba or else, will do less multiplications. So, multiplying polynomials requires a "polynomial" number of steps. But each step could be exponential inside,
[/QUOTE] [b]False.[/b] [QUOTE] if the coefficients are huge numbers (multi-precision). [/QUOTE] [b]False.[/b] Integer multiplication also takes just polynomial time. [QUOTE] .. I would be very surprised if you found an algorithm to multiply polynomials that can be used to multiply integers in polynomial time. I really doubt. Please note that [URL="http://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods"]FFT multiplication[/URL] is NOT polynomial. Its order is still (sub)exponential. [/QUOTE] [b]False.[/b] FFT multiplication is definitely polynomial. Three strikes and you are out! Go back and do some reading. For example, Go read my joint paper with Peter: An FFT Extension to the P-1 Factoring Algorithm. Integer multiplication takes polynomial time. The 'paper/pencil' method is quadratic in the size of the inputs. Integer multiplication via FFT's takes O(n log n loglogn) where n is the size of the numbers. The only essential difference between integer and polynomial multiplication is that for the latter one does not need to handle CARRIES. |

RDS rulz... Well, you are right... Mea culpa. :smile:
I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P |

[QUOTE=LaurV;277422]RDS rulz... Well, you are right... Mea culpa. :smile:
I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P[/QUOTE] PROVABLY IMPOSSIBLE. The proof is trivial. |

[QUOTE=LaurV;277422]I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P[/QUOTE]
I am just wondering. What do you think 'n' means in this context? I get the feeling that you consider 'n' to be the number being multiplied rather than the number of bits/digits in the number being multiplied. |

[QUOTE=axn;277426]I am just wondering. What do you think 'n' means in this context? I get the feeling that you consider 'n' to be the number being multiplied rather than the number of bits/digits in the number being multiplied.[/QUOTE]
The input to a complexity function is the SIZE of the problem........ We measure time/space complexity as a function of the size of the inputs..... The size of a number is its length (in whatever radix you choose) (as axn knows) |

[QUOTE=axn;277426]I am just wondering. What do you think 'n' means in this context? I get the feeling that you consider 'n' to be the number being multiplied rather than the number of bits/digits in the number being multiplied.[/QUOTE]
Well, the thread says "explanation for non math guys".... |

All times are UTC. The time now is 10:48. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.