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

 Maximus 2011-11-07 03:30

[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.

 Maximus 2011-11-07 03:33

[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. :)

 LaurV 2011-11-07 04:58

[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.

 axn 2011-11-07 05:17

[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.

 Dubslow 2011-11-07 06:08

"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

 R.D. Silverman 2011-11-07 12:20

[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.

 LaurV 2011-11-07 13:15

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

 R.D. Silverman 2011-11-07 13:29

[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.

 axn 2011-11-07 13:59

[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.

 R.D. Silverman 2011-11-07 15:46

[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)

 LaurV 2011-11-07 15:50

[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:15.