mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-06-21, 12:44   #34
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

355510 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
He wrote:

"The trouble is not representing Fn, it is performing arithmetic modulo Fn"

This is pretty clear. He said nothing about squaring a random bitstring.

You are referring to the difficulty of doing a multiplication, A*B. Once
one has the product doing the reduction is easy. The difficulty is getting the
product.
This is of course what I meant. I read the original question to be wondering if computations that are currently impossible would become possible because of a different representation of the underlying data, and those computations must involve squaring at least.

One of the early papers on number-theoretic transforms claimed that you could get some computational savings when computing these transforms because multiplication by many of the constants involved in the transform could be performed with only a few modular shifts, adds and subtracts. This is something the dedicated hardware the reader is designing should take advantage of :)
jasonp is offline   Reply With Quote
Old 2007-06-21, 12:55   #35
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Default

Quote:
Originally Posted by jasonp View Post
This is of course what I meant. I read the original question to be wondering if computations that are currently impossible would become possible because of a different representation of the underlying data, and those computations must involve squaring at least.

One of the early papers on number-theoretic transforms claimed that you could get some computational savings when computing these transforms because multiplication by many of the constants involved in the transform could be performed with only a few modular shifts, adds and subtracts. This is something the dedicated hardware the reader is designing should take advantage of :)
Yep. Dedicated custom hardware can speed things.

However, it does not change the underlying complexity. All it does
is improve the implied multiplicative CONSTANT in the O() estimates.

The true asymptotic complexity of multiplication on a Turing machine is
unknown. (see Knuth Vol 2 section on multiplication). We know that we
can achieve linear time complexity on a *pointer* machine, and that this
is the best possible, but we do not know the true lower bound on a
Turing (e.g. finite state real computer) machine. We can achieve
O(n log n loglog n) to multiply n-bit numbers, but do not know if this
is the best possible. I strongly suspect that it is, but there is no proof.

The modular reduction just slows things down by a fixed constant (the
constant being machine and implementation dependent) since we can
also do division by FFT's in time O(n log n loglog n) time. (See Aho, Hopcroft,
and Ullman's book on Algorithms for a clear exposition).
R.D. Silverman is offline   Reply With Quote
Old 2007-06-22, 17:42   #36
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

The recent paper by Martin Fürer has lowered the complexity of integer multiplication to O(n log(n) 2^(log*(n))) where log*(n) is the minimum number of logarithms you need to stack to get <= 1. Bernstein did a quick estimate that suggested that it might be competitive with Schönhage-Strassen for interesting operand sizes, i.e. a few million words or so.

Alex

Last fiddled with by akruppa on 2007-07-19 at 13:37 Reason: Corrected spelling of Fürer
akruppa is offline   Reply With Quote
Old 2007-06-22, 18:35   #37
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

101101111010112 Posts
Default

Quote:
Originally Posted by akruppa View Post
The recent paper by Martin Führer has lowered the complexity of integer multiplication to O(n log(n) 2^(log*(n))) where log*(n) is the minimum number of logarithms you need to stack to get <= 1. Bernstein did a quick estimate that suggested that it might be competitive with Schönhage-Strassen for interesting operand sizes, i.e. a few million words or so.
That sounds like a classic "strictly of theoretical interest" scenario, unless these asympotically-just-a-teensy-bit-faster algorithms are simpler to implement and lend themselves just as well to algorithmic/numeric optimization as a standard transform-based multiply, which I strongly doubt.

As anyone who has implemented a halfway decent transform-based multiply algorithm knows, real-world memory management and processor-optimization effects tend to dwarf anything beyond the n*log(n) terms, and for large vector lengths, one is typically elated to even approach the n*log(n) in practice, especially once the datasets in question significantly exceed the cache sizes on the target hardware.

Thanks for the references, though. ;)
ewmayer is offline   Reply With Quote
Old 2007-10-23, 18:39   #38
sghodeif
 
Sep 2005

2×32 Posts
Default yes, we prove this and find it as big as we want.

Quote:
Originally Posted by jasong View Post
First, let me say, that while I know little about number theory, I'm confident in my ability to notice seemingly odd facts, and therefore be able to ask good questions.

I've been reading in a number theory book I have(made for high school students) about Fermat numbers. In it, it states a method where, for any number 2^2^n+1, it's possible to determine, with n squarings, whether or not it's definitely composite. If anyone wishes I could attempt to post it here(I might make an error, since I don't totally understand the method), but what I was wondering is if anyone has made a program to go through the numbers to check for absolutely certain compositeness. And if so, how far have they gotten?
i prove the infinity of Fermat's prime numbers and find it as big as we want,but i did not publish this until now.
Just waiting or continue to find another proof for this

I wish all the best for u and all mathematicians .

Sghodeif ,
sghodeif is offline   Reply With Quote
Old 2007-10-23, 19:55   #39
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

5·2,351 Posts
Default

For those not familiar with Mr. Ghodeif's alleged "proofs", some background reading to prevent another thread from getting polluted with the discussion:

http://www.mersenneforum.org/showthread.php?t=4604

http://www.mersenneforum.org/showthread.php?t=4618

http://www.mersenneforum.org/showthread.php?t=5211

http://www.mersenneforum.org/showthread.php?t=6018

http://www.mersenneforum.org/showthread.php?t=9507

Mr. Ghodeif, any future posts you make with claims of this sort which [as has been the case with all your claims to date] lack any supporting documentation will be subject to deletion.

Last fiddled with by ewmayer on 2007-10-23 at 20:20
ewmayer is offline   Reply With Quote
Old 2007-10-27, 23:11   #40
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

32·179 Posts
Default

Quote:
Originally Posted by akruppa View Post
The recent paper by Martin Fürer has lowered the complexity of integer multiplication to O(n log(n) 2^(log*(n))) where log*(n) is the minimum number of logarithms you need to stack to get <= 1. Bernstein did a quick estimate that suggested that it might be competitive with Schönhage-Strassen for interesting operand sizes, i.e. a few million words or so.

Alex
Here it is his book:http://www.cse.psu.edu/~furer/Papers/mult.pdf
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ecm with Fermat numbers ET_ FermatSearch 1 2016-08-02 19:40
P-1/P+1 on Fermat numbers ATH Operazione Doppi Mersennes 2 2015-01-25 06:27
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25
Fermat Numbers devarajkandadai Math 8 2004-07-27 12:27
Factoring Fermat Numbers Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 18:20.


Sat Feb 4 18:20:32 UTC 2023 up 170 days, 15:49, 1 user, load averages: 0.89, 1.00, 0.94

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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