Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**Stangerzv****Member**- Registered: 2012-01-30
- Posts: 179

Hi Bobbym

It would take some times and I would let you know when it is done.

Offline

**phrontister****Real Member**- From: The Land of Tomorrow
- Registered: 2009-07-12
- Posts: 3,847

Hi Bobby,

bobbym wrote:

Oh boy, if only some of that were true. My cousin is being kind.

I'm sure I asked you a question once...I think...possibly...

I can't find it, though. Tried inputting a question mark in Search for posts of mine that had one of those things, but that didn't do it. Hmmm...maybe I was wrong.

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,478

About the question mark or the question?

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

**Online**

**phrontister****Real Member**- From: The Land of Tomorrow
- Registered: 2009-07-12
- Posts: 3,847

About ever asking you a question (just going along with the doubt you expressed).

I thought that doing a search for my posts containing a question mark would bring up all posts where I had asked a question, and I was planning to then look through them to see if I'd ever asked you one.

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,478

Try *?*

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

**Online**

**phrontister****Real Member**- From: The Land of Tomorrow
- Registered: 2009-07-12
- Posts: 3,847

I already did, and it only returned 129 pages of my posts in descending date order. The first few I checked didn't have a question mark.

Maybe I've never asked a question.

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,478

For some reason "?" is considered something else in the search.

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

**Online**

**phrontister****Real Member**- From: The Land of Tomorrow
- Registered: 2009-07-12
- Posts: 3,847

I'm pretty sure the search is limited, as we discussed recently in another thread. Only whole words work, I think, and some words are excluded.

I need to get some beauty sleepzzz......

*Last edited by phrontister (2013-10-21 03:03:42)*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,478

Hi;

Okay, see you later. It looks like I will be doing the same thing.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**Stangerzv****Member**- Registered: 2012-01-30
- Posts: 179

Anybody knows how to run the primality test using AKS? Here the AKS article http://en.wikipedia.org/wiki/AKS_primality_test#History_and_running_time (I need for dummies instruction). I have ran ProvablePrimeQ[n] on the mathematica and even after more than a month still couldn't get the answer and it crashed my computer after sometimes. I need to make sure the primes here are true (especially for the large numbers).

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,478

It has been pointed out to me that it is very, very, slow.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**Stangerzv****Member**- Registered: 2012-01-30
- Posts: 179

Dear bobbym

Thanks for the info. I think I need to upgrade my computing power to do the job.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,478

I do not think so. It is very, very, very slow. Too slow to be useful except for small numbers.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**danaj****Member**- Registered: 2014-03-03
- Posts: 16

Here is an example graph showing some times for primality proving. Single threaded on a 4.3GHz machine (more details available if you'd like). I have not seen a faster AKS implementation than the B+V version here, but they could be out there. Pari/GP's APR-CL (the isprime command) runs a bit slower than WraithX's APRCL 1.1. I have no idea how fast Mathematica is (timings from this thread make me think its BPSW is quite a bit slower than the graph here, but that is independent from its proof times). Primo is the most common program used for proving large general primes.

100 digit primes can be proved extremely fast (a few milliseconds). 1000 digits will take ~2-8 minutes. For ECPP and APR-CL the time increases at about the 4th power of the number of digits (for AKS it's the 6th power). By 20k digits, expect 3 months using all cores of a 4- or 6-core machine.

I'm not sure about the various DR-restricted numbers, but the first set of unrestricted (post 109) are fairly small. E.g. p=29 => n=932651 is 213 digits, p=31 => n=2547137 is 242 digits. They grow of course, as p=59 => n=4183583 is 469 digits.

Offline

**Stangerzv****Member**- Registered: 2012-01-30
- Posts: 179

Thanks danaj

I think having a computer with GPU processing units (NVIDIA Tesla) would make it faster due to the fact it has thousand cores per GPU. I am still working on building one with multiple GPUs, got to wait until the GPU price going down after sometimes.

*Last edited by Stangerzv (2014-10-20 12:07:18)*

Offline

**danaj****Member**- Registered: 2014-03-03
- Posts: 16

Having 1024 nodes with 4 2880-core GPUs each doesn't solve anything if there isn't an application to run on it. Do you have something in mind?

Trial division would be trivial to parallelize, but is basically worthless. I see a paper by Asaduzzaman et al. from 2014 saying they have sped it up on GPUs, but (1) that's not hard, and (2) their comparison CPU code is 100x slower than the single-core CPU code I use, making their 90x speedup claim dubious. One thing that bothered me at GTC was the uncertainty around speedup numbers -- it's easy to get 100x speedup if you write cruddy CPU code in a weekend and then compare to GPU code you had four people working 6 months on.

AKS should be pretty easy to run in parallel (each of the *s* tests are independent), and the code that takes 99% of the time is pretty simple. You need to do lots and lots and lots of *s += (a * b) % n* type operations. Some problems:

The growth rate difference means ECPP or APRCL on a single host will beat the hundreds of thousands of GPU cores running AKS. If the serial algorithm takes many trillions of years, how many cores will we need to make it run in an hour? Do you have that many GPUs?

There is no certificate, so realistically your saying you ran this is no better than just saying you used well-known software to run BPSW + a Frobenius test + some number of random-base M-R tests. Less for me because I've seen too many broken AKS implementations. It doesn't matter how fast it is if it isn't correct.

There may be other tricks for AKS that can help, but you have to make major changes to it to get it to the same growth rate as APR-CL or ECPP. There are definitely some research opportunities here.

The BLS75 methods involve factoring, so won't scale to usefully large numbers.

I don't know how well APRCL would parallelize. I think there was a thesis about the subject, but it didn't give much detail.

ECPP certainly could benefit if you could write it. If you do, please make it open source and publicize it. That would be a major accomplishment of use to many people. There are quite a few places where things could run in parallel (the fanout is extremely large if you run speculatively).

*Last edited by danaj (2014-10-20 17:13:18)*

Offline