mersenneforum.org > Math low-value comments cleared out of FFT thread
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2011-11-07, 03:30   #1
Maximus

Nov 2011

22×3 Posts
low-value comments cleared out of FFT thread

Quote:
 Originally Posted by LaurV 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?
Polinomials: C(x)=A(x)*B(x). And it may be used for integer multiplication. FFT does the same.

2011-11-07, 03:33   #2
Maximus

Nov 2011

C16 Posts

Quote:
 Originally Posted by Christenson 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.
In the homework? No. :)

2011-11-07, 04:58   #3
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

100110111101012 Posts

Quote:
 Originally Posted by Maximus Polinomials: C(x)=A(x)*B(x). And it may be used for integer multiplication. FFT does the same.
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 FFT multiplication is NOT polynomial. Its order is still (sub)exponential.

Maybe you found something like this, 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.

2011-11-07, 05:17   #4
axn

Jun 2003

10101000000012 Posts

Quote:
 Originally Posted by LaurV 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 FFT multiplication is NOT polynomial. Its order is still (sub)exponential.
FFT is nlogn which is decidedly polynomial. And, the basis of FFT multiplication is polynomial multipoint evaluation (followed by pointwise multiplication)

Quote:
 Originally Posted by LaurV Maybe you found something like this, that could require a polynomial time, but it would require an exponential space.
If you require exponential space, then you need to read/write all those exponential space, and therefore your algo is exponential time.

 2011-11-07, 06:08 #5 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2011-11-07, 12:20   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·5·373 Posts

Quote:
 Originally Posted by LaurV 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,
False.

Quote:
 if the coefficients are huge numbers (multi-precision).

False. 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 FFT multiplication is NOT polynomial. Its order is still (sub)exponential.
False. 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.

 2011-11-07, 13:15 #7 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 100110111101012 Posts RDS rulz... Well, you are right... Mea culpa. I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P Last fiddled with by LaurV on 2011-11-07 at 13:21
2011-11-07, 13:29   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×5×373 Posts

Quote:
 Originally Posted by LaurV RDS rulz... Well, you are right... Mea culpa. I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P
PROVABLY IMPOSSIBLE.

The proof is trivial.

2011-11-07, 13:59   #9
axn

Jun 2003

10101000000012 Posts

Quote:
 Originally Posted by LaurV I am still waiting for an algorithm with complexity O((log n)^a)), with "a" as big as you want, but fixed... >:P
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.

Last fiddled with by axn on 2011-11-07 at 14:01 Reason: thing -> think

2011-11-07, 15:46   #10
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101001001002 Posts

Quote:
 Originally Posted by axn 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.
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)

2011-11-07, 15:50   #11
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

9,973 Posts

Quote:
 Originally Posted by axn 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.
Well, the thread says "explanation for non math guys"....

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Lounge 46 2017-05-09 12:32 ET_ FermatSearch 5 2016-07-03 10:58 R.D. Silverman GMP-ECM 11 2013-06-29 20:34 jasong jasong 0 2012-08-19 20:02 opyrt Prime Sierpinski Project 7 2008-12-15 00:49

All times are UTC. The time now is 08:06.

Wed Jul 6 08:06:38 UTC 2022 up 83 days, 6:07, 0 users, load averages: 2.33, 1.57, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔