Method for generating prime numbers

Page 3 of 8 [ 113 posts ] Go to page Previous 1, 2, 3, 4, 5, 6 ... 8 Next

Previous topic | Next topic

Ancalagon
Veteran
Veteran

Joined: 25 Dec 2007
Age: 45
Gender: Male
Posts: 2,302

14 Feb 2012, 12:52 am

NeantHumain wrote:

I don't think saving the printing to STDOUT until after all the primes have been calculated buys much.

In my experience, if you have a lot of calculations that are relatively fast, printing each one out to a terminal slows things down massively. If you get to the point where there's a significant, visible pause between numbers, then maybe it isn't a problem, but otherwise it will probably speed things up to avoid putting things on the terminal screen as they're calculated.

You can get the same effect by redirecting output to a file, so you shouldn't have to change the code to check if it's a speedup.

_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton

lau
Veteran
Veteran

Joined: 17 Jun 2006
Age: 75
Gender: Male
Posts: 9,788
Location: Somerset UK

14 Feb 2012, 1:43 am

Ancalagon wrote:

@lau: If your number isn't prime, it's got a really big prime factor. I messed around with factorizing in Haskell, since it has builtin support for arbitrary precision integers. After a couple of (not too tricky) optimizations, I got it to factor 433 factorial almost instantly, but that heavily depends on there being factors it can find fast. I also did 989582272970660878433, which has
919 and 27767 as factors. This is your number with a 9 instead of a 2 in the most significant place. It took about 15 seconds.

When I tried the number you gave, it ran for over 15 minutes before I killed it. If my guesses are right about how much time I save when I can find a relatively small factor (I then divide the number by the factor as many times as it will go, and recalculate the square root of this new number), then it would take at least 250 hours to finish running the program.

When you think about it...half of all numbers have a very small prime factor...that would be 2. Then, of the rest, a third of those (i.e. the odd numbers) have a slightly larger prime as a factor, and that would be 3.

Choose a large number at random, and the chance that it has a prime factor less than 1000 would be 2*3/2*5/4*7/6*11/10*... to one on. I.e. pretty close to guaranteed.

So, does my number (289582272970660878433) have two 11-digit prime factors - or is it prime?

_________________
"Striking up conversations with strangers is an autistic person's version of extreme sports." Kamran Nazeer

NakaCristo
Tufted Titmouse

Joined: 23 Jan 2012
Age: 37
Gender: Male
Posts: 49
Location: Santander, Spain

14 Feb 2012, 3:41 am

lau wrote:

So, does my number (289582272970660878433) have two 11-digit prime factors - or is it prime?

Wolfram Alpha (http://www.wolframalpha.com/input/?i=28 ... 0660878433) gives quickly its two factors.

There are asymptotically much better algorithms to check if a number is prime. In the way you are doing, if you want to check a n-digit number, you are checking about 10^(n/2) divisors. While the last version of the AKS test seems to run in n^6 operations.

Which we don't know is a better way to find the next prime to an integer k than go checking primality of k+1, k+2, ... I think that an improvement in this would be a very good thing. Related, is the work on finding arithmetic successions of primes, as stated in the Green-Tao theorem.

Shorttail
Blue Jay

Joined: 3 Feb 2012
Age: 38
Gender: Male
Posts: 95
Location: Aarhus, Denmark

14 Feb 2012, 7:45 am

NeantHumain wrote:

So you are suggesting something like this?

Yes. I can't tell if it correctly tests it, but it does look like it. It changes the runtime from O(n^2) to O(n*sqrt(n)).

Also, figured out how to allocate more RAM to the application. According to this site, there are 5.8 million primes below 100 million, and 98 million below 2 billion. I managed to test, with 6 GB RAM, 1 billion numbers, and it returned 50,847,534. I haven't found any other sites that claim to know the number (too lazy), but it does seem accurate. 37 second runtime. Pretty awesome compared to past examples.

Edit: I need more RAM.

NeantHumain wrote:

to store them, I'm using an array. Unlike Java, C does not have a built-in library of data structures/collections, so what I'm doing instead is allocating memory from the heap, and since I don't know how many primes there will be in advance, I'm just allocating an array of size maximum (corresponding to the maximum possible prime to generate to); obviously, when calculating up to larger primes, this could become prohibitive, so more complex memory management (e.g., using a smaller array size, reallocating when its limit has been reached, and copying the values over to the new array) would be needed.

I'm actually doing the same, for consistency. ArrayList scales poorly compared to array, because it needs to jump to random places in the RAM, so for all the methods I allocate for worst case. The sieve obviously needs it, but I find that the more naive methods benefit from it as well. The dynamic method does use an ArrayList though.

NeantHumain
Veteran
Veteran

Joined: 24 Jun 2004
Age: 44
Gender: Male
Posts: 4,837
Location: St. Louis, Missouri

14 Feb 2012, 11:03 pm

Shorttail wrote:

It feels so retro programming in C and actually worrying about allocating blocks of memory. C is obviously a pain for a lot of programming tasks, but it was originally intended as a sort of "portable assembler" for writing operating systems (UNIX): kernels, device drivers, and basic utilities.

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 69
Gender: Male
Posts: 116
Location: Missoula, MT

15 Feb 2012, 1:59 am

lau wrote:

jackmt wrote:

...
I looked up the Eratosthenes sieve, the Atkin(?) sieve, and the wheel sieve. They do not generate primes; they eliminate non-primes. I generate primes.

As you went on to say... you do not generate primes, but "prime candidates". I guess any odd number not ending in a digit 5 could be considered a prime candidate. You could then throw in stuff that avoided various other smallish prime factors.

OK. So could you give us a largish "prime candidate" and then show what you would do to establish whether it is really prime?

Here's a 21-digit prime candidate that I have come up with:

289582272970660878433

So... is it prime?

(and - it is too large for the *nix "factor" command to handle.)

My method produces only primes and some predictable products of primes. That is my limited meaning of 'prime candidates'. I have not yet found my work, but I was satisfied that I had created a unique method. It will take me awhile to reproduce it if I can't find it. It is based on a set of facts about all primes. All primes are members of this set, but not all members of this set are primes. I will be back to submit a prime candidate.

Shorttail
Blue Jay

Joined: 3 Feb 2012
Age: 38
Gender: Male
Posts: 95
Location: Aarhus, Denmark

15 Feb 2012, 7:01 am

jackmt wrote:

My method produces only primes and some predictable products of primes. That is my limited meaning of 'prime candidates'.

In what asymptotic time does it spit out prime candidates?

jackmt wrote:

It is based on a set of facts about all primes. All primes are members of this set, but not all members of this set are primes.

Number theory... relevant to my interests. :333

NeantHumain wrote:

Did you program in C before it was cool?

StuartN
Veteran
Veteran

Joined: 20 Jan 2010
Age: 60
Gender: Male
Posts: 1,569

15 Feb 2012, 8:05 am

jackmt wrote:

My method is better and more efficient. It does involve a two step filter after generating "prime candidates." It sounds like it may be valuable. Who should I see?

Any technique that generates or predicts primes faster than current algorithms is worth (big) money. Have a look at something like the RSA algorithm http://en.wikipedia.org/wiki/RSA_%28algorithm%29 for one application area. If you believe in your method, then locate a trustworthy organisation or individual to either market or develop your method, but discussing a mathematical breakthrough on an open web forum will not reward you, not even with a credit in the footnotes, for your idea.

lau
Veteran
Veteran

Joined: 17 Jun 2006
Age: 75
Gender: Male
Posts: 9,788
Location: Somerset UK

15 Feb 2012, 8:33 am

NakaCristo wrote:

lau wrote:

So, does my number (289582272970660878433) have two 11-digit prime factors - or is it prime?

Wolfram Alpha (http://www.wolframalpha.com/input/?i=28 ... 0660878433) gives quickly its two factors.

Interesting.

I'm impressed that they also managed to factorize 5382566094970237769431508041 in just a couple of seconds.

I'm sure I can find their limits...

... or maybe not... as they sailed through 35367552758762092399332712534976091451 within a few seconds as well.

I'm beginning to suspect that Wolfram have a functioning quantum computer, time travel, a tap into my computer, telepathy or maybe they are just controlling my fingers?

NakaCristo wrote:

There are asymptotically much better algorithms to check if a number is prime.

I have no idea what you mean by this. "Asymptotic" to what? In any case, I have not presented any way of checking primality, so I suspect your other remarks were directed at the OP.

_________________
"Striking up conversations with strangers is an autistic person's version of extreme sports." Kamran Nazeer

NakaCristo
Tufted Titmouse

Joined: 23 Jan 2012
Age: 37
Gender: Male
Posts: 49
Location: Santander, Spain

15 Feb 2012, 10:29 am

lau wrote:

I'm beginning to suspect that Wolfram have a functioning quantum computer, time travel, a tap into my computer, telepathy or maybe they are just controlling my fingers?

They simply use a good algorithm. I've just checked Maple, and it also factorize those numbers instantly.

lau wrote:

NakaCristo wrote:

There are asymptotically much better algorithms to check if a number is prime.

I have no idea what you mean by this. "Asymptotic" to what?

I am meaning Asymptotic complexity, which is the behaviour in the limit. Working in the limit gives a very good idea of the execution time but sometimes it can be deceiving.
For example the Schönhage–Strassen algorithm is a multiplication with very low asymptotic complexity, but only outperforms Karatsuba's algorithm when using numbers of more than 10000 digits, hence not very useful in practice.

lau wrote:

In any case, I have not presented any way of checking primality, so I suspect your other remarks were directed at the OP.

Yes, I was directing to them. Checking all divisors (even only up to the square root) for primality is very brute. Those are exponential algorithms and AKS is a polynomial one. Both in the limit and in practice. However AKS is not used much in practice, since there are probabilistic algorithms a lot faster. Only in a need of a complete confidence AKS is used.

lau
Veteran
Veteran

Joined: 17 Jun 2006
Age: 75
Gender: Male
Posts: 9,788
Location: Somerset UK

15 Feb 2012, 2:05 pm

NakaCristo wrote:

...
For example the Schönhage–Strassen algorithm is a multiplication with very low asymptotic complexity, but only outperforms Karatsuba's algorithm when using numbers of more than 10000 digits, hence not very useful in practice....

Nice. We're getting off-topic, but I guess the above means that I should re-visit my "ecalc" program... as I let it handle 300,000 digit numbers (a million bits), and I'm only using the classic multiplication algorithm.

_________________
"Striking up conversations with strangers is an autistic person's version of extreme sports." Kamran Nazeer

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 69
Gender: Male
Posts: 116
Location: Missoula, MT

15 Feb 2012, 2:56 pm

StuartN wrote:

jackmt wrote:

My method is better and more efficient. It does involve a two step filter after generating "prime candidates." It sounds like it may be valuable. Who should I see?

Thank you. And that is why I'm reluctant to show it. I've already had one of my papers stolen after being assured that my work being the earliest was enough proof of authorship. A former professor's paper looks like a rewriting of mine. I will be working with my former mentor. Neither of us are mathematicians, but he has computer savvy and math skills that I lack.

The method is much simpler than any of your comments indicate. I use the KISS method: Keep It Simple Stupid.

NeantHumain
Veteran
Veteran

Joined: 24 Jun 2004
Age: 44
Gender: Male
Posts: 4,837
Location: St. Louis, Missouri

15 Feb 2012, 8:01 pm

Shorttail wrote:

Did you program in C before it was cool?

Ha, anyway if we're talking optimizations, one thing is to substitute an equivalent iterative algorithm in place of the recursive one. The recursive algorithm runs the risk of a stack overflow for larger numbers, not to mention the overhead of calling a function, pushing its arguments onto the stack, etc.

Code:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

typedef enum {FALSE, TRUE} BOOL;

BOOL prime(unsigned long integer)
{
   BOOL result = TRUE;
   if (integer > 2)
   {
      unsigned long squareroot = (unsigned long) ceil(sqrt((double) integer));
      unsigned long factor = 3;
      for (factor = 3; factor < squareroot && result; factor += 2)
      {
         if (integer % factor == 0)
         {
            result = FALSE;
         }
      }
   }

   return result;
}

int main(int argc, char* argv[])
{
   if (argc > 1)
   {
      unsigned long maximum = strtoul(argv[1], NULL, 0);
      if (maximum > 1)
      {
         unsigned long* results = (unsigned long*) malloc(maximum * sizeof(unsigned long));
         if (results != NULL)
         {
            /*printf("2\n");*/
            results[0] = 2ul;
            unsigned long i = 0;
            unsigned long j = 1;
            for (i = 3; i <= maximum; i += 2)
            {
               if (prime(i))
               {
                  /*printf("%lu\n", i);*/
                  results[j++] = i;
               }
            }
            results[j] = 0ul;
            for (i = 0; i < maximum && results[i] != 0ul; i++)
            {
               printf("%lu\n", results[i]);
            }
            free(results);
         }
      }
   }
   return EXIT_SUCCESS;
}

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 36
Gender: Male
Posts: 1,807

15 Feb 2012, 8:07 pm

jackmt wrote:

Thank you. And that is why I'm reluctant to show it. I've already had one of my papers stolen after being assured that my work being the earliest was enough proof of authorship.

I don't mean to be rude, but are you sure that you're not becoming a crank?

http://en.wikipedia.org/wiki/Crank_(person)

The idea that you have found a method for generating primes that is better than any method that has ever been found, given that you have not trained as a mathematician, is bordering on "impossible". In fact, I would go even further and say that it actually is impossible. So much work has been put into this problem that any improvement would take at least fifty pages to write down. If your method is written on a couple of pages... there's something wrong with it. There just is.

Comments that you have made seem to indicate that you are no closer to generating primes than you ever were. You have a method that generates numbers that are "either primes or products of primes". That includes every single natural number greater than 1. It's not an achievement at all.

blahblah123
Yellow-bellied Woodpecker

Joined: 24 Jul 2010
Age: 45
Gender: Male
Posts: 59

15 Feb 2012, 8:48 pm

I found an O(n) time algorithm to generate the first n prime numbers. I've already sent it to the NSA.

C++ code:

Code:

#include<iostream>
using namespace std;

int main()
{
      int n;
      cin >> n;
      for(int i = 0; i < n; i++)
      {
            print_prime(i);
      }

     return 0;
}

This is assuming print_prime(i) runs in O(1) time.

Guys, please don't steal my work.

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 36
Gender: Male
Posts: 1,807

15 Feb 2012, 8:52 pm

blahblah123 wrote:

I found an O(n) time algorithm to generate the first n prime numbers.

Pffft. That's nothing. I just sent the NSA an O(n) algorithm that generates all of the first n natural numbers, not just the primes. Your method has been made redundant.

Page 3 of 8 [ 113 posts ] Go to page Previous 1, 2, 3, 4, 5, 6 ... 8 Next

Jump to:

Method for generating prime numbers Post Reply New Topic

Method for generating prime numbers