Finally learning C++!

[alexander]

elimination is what my algorithm does, it narrows the beam down to numbers that are multiples of 2 primes only. problem being that you still need the recursive check there... :naughty:

 

wait i just thought of optimizing it further, let me test

[alexander]

so, uh, when i said i was onto something, i meant it... check this out

 

this is the new code for the algorithm... let's um, put it this way... i just reran my 5 iteration tests

 

standard method takes 21.01-21.35s

previous generation takes 14.80-15.03s

new algorithm takes 5.4-5.5s

 

thats what almost 4 times more efficient?

 

bool is_prime(int num)
{
 //lets see we need to check for a couple of things first
 
 //compare to single digit primes, why? they are the only ones with irreglarities
 if (num < 8)
   {
     static bool firstPrimes[] = {false, false, true, true, false, true, false, true};
     return firstPrimes[num];
   }
   
 //now lett's check for simple division, this weeds out a LOT of numbers
 if (num%2==0 || num%3==0 || num%5==0 || num%7==0)
   {
     return false;
   }
 
 //exploiting what we know about the prime set, weed out even MORE numbers
 if((num+1)%6==0 || (num-1)%6==0)
   {
     //unfortunately we still need to do this, this is the only way to check if the number has prime factors...
     int to = sqrt(num+1);
     for(int i=2; (6*i)-1<=to; i++)
  {
    if(num%((6*i)+1)==0 || num%((6*i)-1)==0)
      {
        return false;
      }
  }
     return true;
   }
 return false;
}

 

please note where i cut down the time... it now no longer loops over a range of odd numbers to test for primity

 

after the initial checks, the only false positives generated are those that are produced when the only factors of the number are 2 primes larger then 7, so it is safe to set the inner checking loop to operate in the "prime number range" per say, cuts down the internal loop to be 6 times faster, or there-about

[alexander]

here's some testing data

 

 

running 5 iterations testing 5000000 numbers from 1000000 to 6000000 such that first 4 iterations output into /dev/null and the last iteration outputs to a file

 

alexander@Anubis ~/code $ time ./prime_stan.sh

real    2m14.734s
user    2m12.940s
sys    0m0.673s
alexander@Anubis ~/code $ time ./isprime.sh

real    0m13.316s
user    0m13.191s
sys    0m0.072s

alexander@Anubis ~/code $ cat prime_stan.sh
#!/bin/bash
./prime_stan > /dev/null && ./prime_stan > /dev/null && ./prime_stan > /dev/null && ./prime_stan > /dev/null && ./prime_stan > one

alexander@Anubis ~/code $ cat isprime.sh
#!/bin/bash
./isprime > /dev/null && ./isprime > /dev/null && ./isprime > /dev/null && ./isprime > /dev/null && ./isprime > two

alexander@Anubis ~/code $ tail -n 15 isprime.cpp
 
int main()
{
 int num;

  for( num=1000000; num<=6000000; num++)
    {
      if(is_prime(num))
	{
	  cout << num << "n";
	}
    }
  return 0;

}
alexander@Anubis ~/code $ tail -n 15 prime_stan.cpp
   }
 return true;
}

int main()
{
 for( int num=1000000; num<=6000000; num++)
   {
     if(is_prime(num))
{
  cout << num << "n";
}
   }
 return 0;
}

alexander@Anubis ~/code $ ls -lsah | grep "one|two"
5232 -rw-r--r--    1 alexander  alexander   2.6M Feb 24 00:10 one
5232 -rw-r--r--    1 alexander  alexander   2.6M Feb 24 00:11 two

[IDMclean]

I've been obsessed with tuning the sieve algorithm for my program, and I've got it mostly nailed down for eliminating powers of odd numbers.

 

Anyone want to take a crack at implementing

 

[math]i_{a^n}{(\displaystyle \sum_{n=0}^{\infty} a^{n-1})} = i_{a^n}(a^0 + a^1 + a^{...} + a^{n-1}) = i_{a^{n}} [/math]

Where

[math]a_i = a^0 + 2i = 1 + 2i[/math]

 

as a c++ algorithm?

 

The index, [math]i_{a^n}[/math], of the power, [math]a^n[/math], in an odd number sequence can be found by taking the sum of the powers of a,

 

[math]i_{a^n}{(\displaystyle\sum_{n=0}^\infty a^{n-1})}[/math]

 

A consequence of this relationship is that the value at an index is tied to the index.

 

examples:

[math] \begin{bmatrix} 3_1 & 5_2 & 7_3 & 9_4 & 11_5 & 13_6 & 15_7 & 17_8 & 18_9 & a_i \end{bmatrix}[/math]

 

[math]i_{3^2} = 1(3^1+3^0) = 4 \text{, so } 3^2 = 1+2(4) = 9[/math]

 

[math]i_{3^3} = 1(3^2+3^1+3^0) = 13 \text{, so } 3^3 = 1+2(13) = 27[/math]

 

[math]i_{3^{20}} = 1(3^{19}+3^{18}+3^{...}+3^0) = 1743392200 \text{, so } 3^{20} = 1+2(1743392200) = 3486784401[/math]

 

Resources:

Euler's factorization method

[alexander]

ok, ok, first of all, please switch to using the [math][/math] tags, they are better run cleaner, cache and are faster for the forums, if you've noticed, i updated the math 2.0 instructions to not even mention the deprecated latex tags.... only reason they still work is for reverse compatibility, so please use the math tags in the future (they also allow you and me to plainly copy the equation and not have to reverse engineer the whole damn thing)

 

KAC, the seive algorithm is essentially what i have used, problem with it is that it quickly starts consuming memory, because after you test for the division by 2,3,5,7, you have to continue testing for the rest of the primes, and problem is that it is not so simple to do when your numbers reach to be large. Though essentially it is what i have done with the algorithm, i just made it a lot more efficient then the seive. After preliminary tests, it only has to check for numbers that are multiples of 2 primes, but unless you store your found primes in an array (and that is not always an option) you have to generate prime numbers on the fly. And problem with that is that it's not so simple to do. That is also the problem with euler's factorization, and why it is not favorable for comp-sci, you would have to figure out if the number is a multiple of 2 primes first, then, if it's not the euler's factoring method is favorable, but using euler's method is not 100% accurate

 

also 3486784401 is not prime

[IDMclean]

I switched gears on you, Alex. I'm searching for non-primes. I can predict the occurance of a non-prime deterministically. 3486784401 is a power of 3, [math]3^{20}[/math], to be exact. I'm working on an algorithm which will determine the placement of all non-primes in a sequence and mark them as false. The first step towards that is the determine where the powers of primes (or as my equation above would indicate, all powers) are and mark them as false.

 

I've got the powers nailed, but I'm encountering issues with determining the indexes of multiples of prime factors (by eliminating all the non-primes below the square of the highest number in a given segment of an arbitrary sequence of positive integer non-zero numbers, you will find all the primes up to the highest number in the given segment).

 

To see what I mean, check the code I submitted. I have zero trail division in my sieve. I'm using only addition, multiplication, and bit-wise operators. The only division I do is the modulus check to see if a number ends in five while I am making the set of odd numbers minus multiples of five.

 

I'm working on the principle that once you eliminate all the things which aren't prime, The only thing you're left with is prime numbers. Technically and practically speaking, my program generates a prime number table by the process of elimination. I don't check for primality, I procedurally falsify the multiples and powers of primes.

 

It bugs me to do it this way, but it requires fewer checks than iterating through the odd sequence dividing everything by everything else up to the square root of each individual element in the sequence. Even as such, I'm dealing with 85% of the junk data (and growing as the number of primes in a given interval decrease). But 34% of the number line is easier to deal with than 40%.

 

Once again, check my code to see what I am doing.

[alexander]

so you are looking at something like this then:

 

elim.h

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

// The long long type is now standard in C, but I don't know if it's
// standard in C++.  Anyway, this makes it easy to change to something
// else.
typedef unsigned long long Integer;

// Prime eliminator.  It is essentially a pair of numbers, the first prime
// and the second a multiple of the first.  The program keeps a collection
// of these in a heap to eliminate candidate primes.
class Eliminator 
{
private:
       // The base is a prime number, and the target is the next multiple
       // which it has not yet eliminated.
       Integer base, target;
public:
       // Create at a prime, ready to eliminate the first multiple thereof.
       Eliminator(Integer p)
       {
               base = p;
               target = 2*p;
       }

       // See what number is eliminated next.
       Integer eliminates()
       {
               return target;
       }

       // Advance to the next elimination.
       void advance()
       {
               target += base;
       }

       // Compare Eliminators according to their eliminated value.
       bool operator<(const Eliminator &e) const
       {
               return target > e.target;        // Note: Inverted sense
       }
       bool operator==(const Eliminator &e) const
       {
               return target == e.target;
       }

       void print()
       {
               cout << "(" << base << ", " << target << ")";
       }
};

// This is a collection of Eliminators organized as a heap, so the next largest
// one can be found quickly.
class EliminatorCollection
{
private:

       // This holds the heap data structure.
       vector<Eliminator> heap;

public:
       // What does the heap eliminate just now?
       Integer eliminates()
       {
               return heap.front().eliminates();
       }

       // Insert a new prime eliminator into the collection.
       void insert(Integer i);

       // Move to the next eliminator.
       void advance();

       // Get 'em out.
       void dump();
};

void EliminatorCollection::insert(Integer i)
{
       heap.push_back(Eliminator(i));
       push_heap(heap.begin(), heap.end());
}

void EliminatorCollection::advance()
{
       // Get the current eliminee.
       Integer you_die = eliminates();

       // Get rid of all the nodes which eliminate this same number.
       vector<Eliminator>::iterator heap_end = heap.end();
       while(heap_end != heap.begin() && heap.front().eliminates() == you_die)
       {
               pop_heap(heap.begin(), heap_end);
               --heap_end;
               heap_end->advance();
       }

       // Return them, now advanced, to the heap.
       do
       {
               ++heap_end;
               push_heap(heap.begin(), heap_end);
       }
       while(heap_end != heap.end());
}
void EliminatorCollection::dump()
{
       vector<Eliminator>::iterator scan = heap.begin();
       while(scan != heap.end())
       {
               scan->print();
               cout << endl;
               ++scan;
       }
}

 

primegen.cpp

//
// Generate primes until you get tired of it (or run out of 
// unsigned long long).  This uses a form of the seive method which
// eliminates non-prime candidate primes by checking if they are a
// multiple of any previous prime found.  This is done efficiently by
// keeping the set of multiples of previously-found primes in a heap.
// A heap is a data structure which can quickly find the smallest
// number it contains.
//
#include <iostream>
#include <strstream>
#include "elim.h"

using namespace std;

// Figure out the number of bits for printing, since nothing in the stupid
// streams that actually outputs to strings is actually there.

// Output with appropriate wrap.
void outprime(Integer n)
{
       static int outlen = 0;  // Output line width.

       // Get the string for n.
       ostrstream os;
       os << n << ends;
       string strint = os.str();

       // Do any needed wrap.
       if(outlen + strint.length() + 1 > 75) {
               cout << endl;
               outlen = 0;
       } else {
               cout << " ";
               outlen++;
       }

       cout << strint;
       outlen += strint.length();
}

main()
{
       outprime(2);

       EliminatorCollection ec;
       ec.insert(2);
       for(int m=3; 1; m++)
       {
               if(m == ec.eliminates())
                       ec.advance();
               else {
                       //cout << m << endl;
                       outprime(m);
                       ec.insert(m);
               }
       }

       cout << endl;
}

 

note not my code, uses the seive method, and runs very fast...

[buddyzen]

lol your first post made if sound like you were typing a book ....

[IDMclean]

Alright, here's some interesting things about the odd number line and it's indexes.

 

Any odd number on the positive non-zero integer odd number line is of the form:

 

[math]a_i =a_i^0 + 2i [/math]

 

Odd numbers have the property, if(a & 1) = true, where as even numbers have the property, if(a & 1) = false.

 

You can find the index, i, of any power, n, of a number, a:

 

[math]\large i_{a^n} ( \sum_{n=0}^{\infty} a^{n-1} )[/math]

 

You can find the index, m, of any product, [math]a_m = a_i \times a_j[/math], of a number, [math]a_i[/math] , and another number, [math]a_j[/math] , on the odd number line:

 

[math]\large m = ja_i + i = i + 2ij + j[/math]

 

Using this, can you yield the primes by skipping the non-primes?

[alexander]

ok lets think about this, you could try to eliminate some of the odd numbers, but as far as i know its not so simple to tell a prime from a regular odd number all too simply

 

ok we can take your thought further by looking for these properties:

 

first of all it is easier to start with an already refined set of numbers. Above 3, all the primes fall into the set [math]6\times n \pm 1[/math]

 

so starting with 2 and 3 the rest of the primes will fall into that set 5,7,11,13 etc

 

not to say that all the numbers in that set are prime though

 

so then we can use proth's theorem to determine if the numbers in this set are prime by using this pseudo code (this is the AKS primity test) (perhaps the fastest deterministic method for finding prime, fastest before probabilistic ones, but they don't definitely tell you)

Input: Integer n > 1

if (n is has the form ab with b > 1) then output COMPOSITE

r := 2
while (r < n) {
   if (gcd(n,r) is not 1) then output COMPOSITE
   if (r is prime greater than 2) then {
       let q be the largest factor of r-1
       if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break
   }
   r := r+1
}

for a = 1 to 2sqrt(r)log n {
   if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE
}

output PRIME;

 

this primity algorithm has a run time of O((log n)12f(log log n)) at most (f is a polynomial)

[maddog]

I find it odd (and this is compiler version dependent) that including some header files as

 

#include <iostream.h>

 

and others

 

#include <string>

 

I got this from a C++ rep from Green Hills C++ on the Integrity RTOS platform.

 

Just odd!

 

maddog :singer:

[maddog]

Has anyone tried learning Objective-C. I am finding a bit of an adjustment from either

C, C++ or C#. I haven't quite got my head around yet. I am still trying to convince my

wife that buying Leopard can be a good thing (I found out recently that to use Xcode 3.12

-- latest, you Need Leopard! & to program for iPhone, you Need Xcode 3.12!!!).

 

maddog

[IDMclean]

Has anyone tried learning Objective-C. I am finding a bit of an adjustment from either

C, C++ or C#.

 

I've just started in on C/C++, so no, I have yet to check out Objective-C or C#.

[alexander]

GCC forever here :singer:

 

i am not a fan of C# or Objective C though i know some people that develop in it

[maddog]

GCC forever here :singer:

 

i am not a fan of C# or Objective C though i know some people that develop in it

Well, I must say I am definite Not a fan of C# either. There staunch notion that Everything is an object is a bit too Orwellian for me.

 

As for Objective-C my impression it was written by Aliens so I am still deciding on it. I have written in C more years than I care to divulge. C++ I only have about 10 yrs, roughly.

 

What I am finding weird is how some compilers deal with header files and namespaces.

The ANSI/ISO Standard seems to allow a lot of leeway. Maybe I am just rusty, I don't

last couple of positions, I was spending to much time on UML than actually writing code.

 

maddog

[alexander]

ansi standard allows no leeway, many compilers dont comply with ansi standards though, example of such a compiler would be Microsoft Visual C++ compiler, but there are many compilers out there that dont comply, borland compilers are that way, and its a problem for any developer having to adjust to work with them. That's actually why i love GCC so much, its ANSI compiant, it's available for almost any platform, and regardless of the platform it works nearly the same way, there are some platform-dependant switches, and some platforms have weird quirks, but i trust GCC more then any other compiler out there, and i, as i am sure you have too, have tried MANY...

[ElSheldonO]

i envy most of you because you guys atleast understand C++ but i started taking a class in it and i'm having a tough time...i mean i'm good at programming but when it comes to midterms and having to write it all out, well i'm bad at that.