Prime Number Calculator

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

Prime Number Calculator

Postposted on Tue Jun 24, 2003 4:56 pm

Recently, for a friend of mine doing looking to get a maths theorem on "Pythagorean triples" (Don't ask, I don't know), I made a little VBA script for excel to generate endless prime numbers...

Code: Select all
Dim PrimeTest As Double
Dim PrimeDiv As Double
Dim DivValue As Variant
Dim flag As Integer

Sub CalcPrime()

PrimeTest = Range("A2")
PrimeDiv = 0
flag = 0

Do
PrimeTest = PrimeTest + 1

PrimeDivision:
flag = 0
PrimeDiv = 1
While PrimeDiv <= (PrimeTest) / 2
DivValue = PrimeTest / PrimeDiv
If DivValue = 1 Then
flag = flag + 1
    ElseIf DivValue = Int(DivValue) Then
            flag = flag + 1
                ElseIf DivValue = PrimeTest Then
                        flag = flag + 1
    End If
PrimeDiv = PrimeDiv + 1
Wend

If flag = 1 Then GoTo PrimeConfirm
If flag <> 1 Then PrimeTest = PrimeTest + 1
GoTo PrimeDivision

PrimeConfirm:
Range("A2") = PrimeTest
flag = 0
Loop Until 1 > 1 + 1
End Sub


Every now and then, I like to come back to my code from the past, to see if I can improve it. I think I've found a way, but I'd like to run it past you guys first...

This code tests every number halfway up to the number being checked, to see if it's a factor (the reason being that after halfway, there are no factors of any number)

Now, the question is, is every non-prime number divisible by 2 or 3? (1 is irrelevant IMO)

If so, I could make an prime number array, with the first two numbers being 2 and 3 (themselves prime numbers), and so test a number by every non-zero prime in this array?

That would probably speed up the numbers by a fair bit... seeing as I'm got it up to 80,021, from 1 :-D

The other thing I thought of doing, which I know would work, is to cause it to loop back to PrimeDivision after a factor is found...

Also, note the "cute trick" that I used on the "loop until 1 > 1+1"... I can't remember who picked me up on the "loop root 3" in my scanf thread, but hey, I told you I liked shortcuts :-D

Thanks guys,
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Tue Jun 24, 2003 5:05 pm

Now, the question is, is every non-prime number divisible by 2 or 3? (1 is irrelevant IMO)


No. I don't have a formal proof, but a while ago I was bored so I wrote a program in VB that would break a number down into its prime factors. I threw a few numbers at it until I got a factoring that didn't include 2 or 3.

989891=141413x7

Factoring large numbers is something that math and computer people have gone bonkers over. A common way of finding prime numbers other than by simple division and checking is to use a quadratic sieve.

http://mathworld.wolfram.com/QuadraticSieve.html

It's been a while since I've dealt with heavy math so it kinda makes my brain hurt to look at it, but I'm sure it'll work well. :lol:
Do not meddle in the affairs of archers, for they are subtle and quick to anger.
Mime
Graphmaster Gerbil
 
Posts: 1193
Joined: Sat May 24, 2003 11:49 pm
Location: A tiny cubicle

Postposted on Tue Jun 24, 2003 5:13 pm

Mime wrote:
Now, the question is, is every non-prime number divisible by 2 or 3? (1 is irrelevant IMO)


No. I don't have a formal proof, but a while ago I was bored so I wrote a program in VB that would break a number down into its prime factors. I threw a few numbers at it until I got a factoring that didn't include 2 or 3.

989891=141413x7


Basically, this program is going to go from 1-God knows...

By the time it gets to 989891, 7 will be in the array of prime numbers :-D

Sorry that I forgot to mention that bit lol...

Oh yeah, and isn't encryption one use of factoring large numbers? This friend of mine was mentioning that, if someone had found a way to factor numbers real fast, it would be as if he'd invented a working QC, and every encryption this side of Sunday would be his for the taking...

Excluding the more bullet-proof ones, that use a different method, can't remember the name... begins with "a" IIRC :-D

But you have opened up a new can of worms for me... anyone know how to store a string in excel so I can use it next time? I'm thinking of using a Cells(y,x) command but then every time I'd have to load it in and save it... surely there must be a quicker way :-D

Cheers guys,
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Tue Jun 24, 2003 5:20 pm

For those who are interested, and for possible future reference, I ran the program starting with A2 = 80,021, and counted how long it took the program to find the next number... counting on my nokia phone's stopwatch...

To get the next number, 80,039, took about 5 seconds (the stopwatch says 5.34s, but that's including human delays etc.)

Now this program has considered about 700-760k possible factors, and flagged probably in the range of thousands, you can see how this program could be sped up a fair bit :-D

And that root 3 trick reference, that was muyuubyou, :-D
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Tue Jun 24, 2003 5:38 pm

By the time it gets to 989891, 7 will be in the array of prime numbers


Hmm...I see. :P There could be a prime number much smaller that isn't divisible by 2 or 3 also, I dunno.

It's true, there's a number of encryption methods that use large prime numbers. If, say, a 200 digit prime number was found that nobody else knew about, it'd be quite a challenge for that encryption to be broken.
Do not meddle in the affairs of archers, for they are subtle and quick to anger.
Mime
Graphmaster Gerbil
 
Posts: 1193
Joined: Sat May 24, 2003 11:49 pm
Location: A tiny cubicle

Postposted on Tue Jun 24, 2003 6:05 pm

Okay, I'm having a quick go at this, but I've never used arrays before in VB, so I think I'm getting hung up on syntax, but it could be another error I've not seen lol... here comes the code

Code: Select all
Sub CalcPrime2()

PrimeTest = Range("A2")
PrimeDiv = 0
flag = 0

ArrayLoad

Do
PrimeTest = PrimeTest + 1

PrimeDivision:
flag = 0
ArrayRef = 1
While PrimeArray(ArrayRef) <= (PrimeTest) / 2
DivValue = PrimeTest / PrimeArray(ArrayRef)
If DivValue = 1 Then
flag = flag + 1
    ElseIf DivValue = Int(DivValue) Then
            flag = flag + 1
                ElseIf DivValue = PrimeTest Then
                        flag = flag + 1
    End If
ArrayRef = ArrayRef + 1
Wend

If flag = 1 Then GoTo PrimeConfirm
If flag <> 1 Then PrimeTest = PrimeTest + 1
GoTo PrimeDivision

PrimeConfirm:
Range("A2") = PrimeTest
Cells(ArrayRef, 3) = PrimeTest
flag = 0
Loop Until 1 > 1 + 1
End Sub



Code: Select all
Sub ArrayLoad()

Do

PrimeArray(ArrayNumber) = Cells(ArrayNumber, 3)
ArrayNumber = ArrayNumber + 1

Loop Until Cells(ArrayNumber, 3) = 0

End Sub


FWIW, I've declared all variables I've used in this program, and even ones I've got rid of lol, so I'm fairly sure it's array syntax...

I've looked quickly but intensely at the help files and they were.... cryptic as usual... lol,
IntelMole[/code]
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Re: Prime Number Calculator

Postposted on Tue Jun 24, 2003 6:14 pm

IntelMole wrote:Every now and then, I like to come back to my code from the past, to see if I can improve it. I think I've found a way, but I'd like to run it past you guys first...

This code tests every number halfway up to the number being checked, to see if it's a factor (the reason being that after halfway, there are no factors of any number)

It is sufficient to test every number up to the square root of the number being checked, since if there was a factor that was larger than the square root of the number, there would have to be another factor that was less than the square root (so you would have found it already).

Now, the question is, is every non-prime number divisible by 2 or 3? (1 is irrelevant IMO)

No. E.g., 25 is not divisible by 2 or 3.

If so, I could make an prime number array, with the first two numbers being 2 and 3 (themselves prime numbers), and so test a number by every non-zero prime in this array?

That would probably speed up the numbers by a fair bit... seeing as I'm got it up to 80,021, from 1 :-D

Here's some pseudo-code for finding all primes up to a given number n... it is much faster, at the expense of using a lot more memory:
Code: Select all
create an array a with highest subscript n
initialize all elements of a to 0
for each integer i from 2 to square root of n
    if a[i] is 0
        for each integer j from i*2 to n, stepping by i
            set a[j] to 1

At the conclusion of this double loop, each array element a[x] will be 0 (false) if x is prime, or 1 (true) if x is non-prime.

For efficiency reasons, you may want to take the square root of n outside the loop and assign it to a variable (in case your compiler isn't smart enough to realize it doesn't change each time through, and tries to recompute it each time thru the loop).

What this algorithm does -- instead of individually testing each number for primeness -- is to find each prime in sequence, then immediately mark all multiples of that number as non-prime. This vastly cuts down on the amount of work.

Here is the C++ for a command line version... on an Athlon XP 1800+, it can calculate all of the primes up to 10000000 -- that's right, ten million -- and write them to a file in approximately 2 seconds:
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{

    // Make sure user specified upper bound
    if (argc > 1)
    {

        // Get upper bound from command line
        int n = atoi(argv[1]);
        if (n > 0)
        {

            // Allocate array and clear it
            bool *a = new bool[n + 1];
            for (int i = 0; i < n + 1; i++)
                a[i] = false;

            // Find the primes
            int sqrtn = (int) sqrt(n);  // in case compiler is stupid
            for (int i = 2; i <= sqrtn; i++)
            {
                if (!a[i])  // i is prime
                {
                    for (int j = i * 2; j <= n; j += i)
                        a[j] = true;
                }
            }

            // Print them all out
            for (int i = 2; i <= n; i++)
            {
                if (!a[i])
                    printf("%d\n", i);
            }

            // Deallocate the array
            delete [] a;

        }

    }
    else
    {
        printf("please specify highest desired prime\n");
    }

    return 0;

}
Last edited by just brew it! on Tue Jun 24, 2003 7:34 pm, edited 1 time in total.
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37514
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Tue Jun 24, 2003 6:47 pm

Aaaargh!!! C!!!! :-D

Thanks, but I can't even begin to understand the pseudocode and why you do it that way, let alone begin to penetrate the C++ version, I've been sitting here for the best part of 10-15 minutes trying... lol

Maybe you could run it past me again :-D

Goddammit, whenever I go on this thread it always reminds me how useless I am at this, I hope Uni's a damn sight easier!
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Tue Jun 24, 2003 6:51 pm

IntelMole wrote:Aaaargh!!! C!!!! :-D

Aaaargh!!! VB!!! :D

Thanks, but I can't even begin to understand the pseudocode and why you do it that way,

It's a way to visualize an algorithm without language syntax getting in the way.

let alone begin to penetrate the C++ version, I've been sitting here for the best part of 10-15 minutes trying... lol

Maybe you could run it past me again :-D

I'll try and provide a better explanation later... I've gotta go and feed the kids right now! :)

Goddammit, whenever I go on this thread it always reminds me how useless I am at this, I hope Uni's a damn sight easier!
IntelMole

Well, after Uni, you'll probably be able to read pseudo-code and C++ like a pro! :wink:
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37514
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Tue Jun 24, 2003 7:02 pm

I understand why you do pseudocode, I did it when I did a computing A-Level for a term... I didn't understand it then, but it came together seamlessly in the New Testament...

Just don't understand why you do the algorithm in that way :-D

In the pseudocode version, the algorithm gets in the way

In the C version, the syntax gets in the way!

This could be a long night.... :lol:,
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Tue Jun 24, 2003 7:33 pm

There, ordered some Chinese carry-out for the kids... I have a few minutes before I need to go and pick it up. :D

The algorithm is an implementation of the "Sieve of Eratosthenes". It makes use of the fact that once a number is found to be prime, you know that all integer multiples of that number are non-prime, by definition. This avoids much duplicated work, making the algorithm more efficient. It also allows the algorithm to be done almost entirely using integer arithmetic (except for the square root, which is only done once before entering the main loop), and avoids the use of any kind of division or modulo operation in the inner loop (division and modulo are the least efficient arithmetic operations for a CPU to execute).

In this implementation, rather than keeping an actual list of the primes found, we merely set a flag in an array for each integer 2..n, indicating whether that integer is prime or not.

The flags in my C++ code are boolean variables... if you wanted to get fancy, you could reduce the memory usage tremendously by packing the flags 8 to a byte (i.e., using individual bits to represent the flags). But this would complicate the code a fair amount, and further obfuscate the the underlying algorithm (this is why I didn't attempt to do this).

This link probably explains the basic algorithm better than I can:

http://www.math.utah.edu/~alfeld/Eratosthenes.html

There was also a minor error in the original code I posted -- it erroneously prints "1" as the first prime. I'll edit the post to correct this...

You could also try googling "sieve of eratosthenes" for more info.

Hope that helps!
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37514
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Tue Jun 24, 2003 7:45 pm

Very cool JBI. You may have made me curious enough I might have to try this one out myself. :wink:
Do not meddle in the affairs of archers, for they are subtle and quick to anger.
Mime
Graphmaster Gerbil
 
Posts: 1193
Joined: Sat May 24, 2003 11:49 pm
Location: A tiny cubicle

Postposted on Tue Jun 24, 2003 8:09 pm

Hell, maybe this is me, but I feel stupid...

For some reason, unknown to anyone but God, who felt like a joke on a cold spring night in 1985, I have a problem with learning...

It goes a bit like this:

Unless I can see EXACTLY where it comes from, I've not got a clue...

The same happened when I asked about heat engines (I'll find that thread later), when I was taught chemical reactions in Chemisty (which I subsequently ignored because I just COULD NOT get them), and any other non-explainable phenomena...

It's probably this which led to me doing maths, because I can easily see the links and connections...

Like some sort of ever-growing hurdle, I just can't make the conceptual leap of faith anywhere unless it makes sense...

Unfortunatly, even that link doesn't make sense to me... the over-riding question is: WHY? Why, if you take those numbers, and do that, do you get the prime numbers?

This link kind of makes sense, but still seems like you're just repeating the calculations "in reverse..."

I hope that makes sense... If the sieve makes sense I'll see if I can fill in the holes... <sighs at own bad joke, that's the best I've got ATM>
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Tue Jun 24, 2003 8:49 pm

5*7=35
AMD Athlon 64 3000+, 1 gb DDR 400, Radeon x800.
endersdouble
Gerbil First Class
 
Posts: 136
Joined: Sun May 04, 2003 8:41 pm

Postposted on Tue Jun 24, 2003 8:55 pm

endersdouble wrote:5*7=35


Erm....

<tumbleweed goes past, accompanied by dust and all>

Yeah...

by the way, that heat pump link,
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Tue Jun 24, 2003 9:20 pm

Okay, I've mostly got the sieve, I think...

Ah-hah!

What was causing me all the grief (I think...) was that I was reading the thing wrong... here's my take on the pseudocode. Not that I'm calling it wrong, but your version of the pseudocode would be easier to understand if you removed the majority of the first two lines (apart from the array def.), for the simple reason that they complicate the operations performed.

So there's a couple of basic operations here:

- Write out all the numbers
- Mark all multiples of x= 2
- Mark all multiples of x+= 1... until you reach root n
- Print/Save the unmarked numbers...

Sorry that it took me so long :-D

One last question... is it possible to modify the operation so that it does it infinitly, or will I have to resort to an array of primes, 2,3,5,7,11, etc...

If so, any luck on VBA arrays syntax?
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Tue Jun 24, 2003 9:36 pm

Hey, I went to convert the C code to VB, then I realized I didn't have VB installed on my new box. I will do it for you tomorrow, and maybe a few possible "improvements".

BTW one method:
myArray() = Array(1,2,3,4,5,6,....)

The other way is by using another sheet in Excel, or using files. Lots more too...

dim myArray(100) as long

or dynamically:

dim myArray() as long

redim myArray(numElements) as long 'Makes all elements 0

redim preserve myArray(numElements) as long 'Preserves any existing element's values
liquidsquid
Minister of Gerbil Affairs
 
Posts: 2447
Joined: Wed May 29, 2002 10:49 am
Location: New York

Postposted on Tue Jun 24, 2003 9:46 pm

liquidsquid wrote:dim myArray() as long


I've got "Dim PrimeArray() As Single"

Yet I get a message saying 400, and I've never known what it means :-S...

Anyways, I'm going to bed,
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Tue Jun 24, 2003 9:51 pm

Not that I'm calling it wrong, but your version of the pseudocode would be easier to understand if you removed the majority of the first two lines (apart from the array def.), for the simple reason that they complicate the operations performed.

Hmm... well, some languages require you to explicitly allocate/dimension arrays, and some don't pre-clear arrays to some defined value. So while those steps aren't necessary in some languages, they are in others (like C++). It's up to the coder to decide whether it is necessary...

One last question... is it possible to modify the operation so that it does it infinitly, or will I have to resort to an array of primes, 2,3,5,7,11, etc...

The amount of available memory puts an upper limit on how many primes you can calculate with this algorithm. Practically speaking, you want the "marker array" to fit entirely in physical memory; virtual memory is no good, since it will thrash your disk horribly (and run very, very slow).

If you do some bit-twiddling (packing one marker into each bit of memory), a 512MB array would allow you to calculate all of the primes up to 2^29*8, or 4 billion (approximately).

That's the tradeoff versus a "brute force" approach -- we are trading off memory usage for a huge boost in speed. The marker array makes it unnecessary to re-test every possible factor for every potential prime number.

I'll let liquidsquid handle the VB conversion... it's been a few years since I've done VB (and I never used it much), so my VB skills are a little rusty. :wink:
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37514
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Wed Jun 25, 2003 12:52 pm

Here is the conversion from C to VB:

Code: Select all
'**************************************************************************
'Call routine with the limit of values you wish to find, and a destination
'list box for the values to be shown in.
'example:
'
' findPrimes 10000, frmMain.lstResults
'
' Returns: Nothing.
'
'**************************************************************************
Public Sub findPrimes(upperBound As Long, destList As ListBox)
Dim I, J As Long
Dim a() As Boolean
Dim sqrtn As Long

    destList.Clear                          'Clear the list box

    If upperBound > 0 Then                  'Check the uper bounds value
        ReDim a(upperBound) As Boolean      'Will also empty array to 0, or False.
       
        sqrtn = Sqr(upperBound)             'Find out how far we really need to go, and calc once only
       
        For I = 2 To sqrtn
            If Not a(I) Then                'I is a prime
                J = I * 2
                Do
                    a(J) = True
                    J = J + I
                Loop While J <= upperBound
            End If
        Next I
       
        For I = 2 To upperBound             'Essentially print them all out to the list box.
            If Not a(I) Then destList.AddItem I
        Next I
    Else
        MsgBox "Upper bound must be > 0", vbCritical
    End If
End Sub


-LS
liquidsquid
Minister of Gerbil Affairs
 
Posts: 2447
Joined: Wed May 29, 2002 10:49 am
Location: New York

Postposted on Wed Jun 25, 2003 1:09 pm

...and as a minor tweak, you could make the code a little shorter (both the C++ and VB versions) by printing out the numbers as they are found, instead of using a separate loop. I originally split it into two loops to avoid cluttering the sieve code.

For lots of primes, you may run into problems with the VB version due to capacity of the listbox. (Not sure what the maximum size of a listbox is.)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37514
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Wed Jun 25, 2003 1:37 pm

JBI, I take it that's a no :-D

Lol I'm probably already running this browser in virtual memory :-D Oh no, it's a K6-2 :-D

Anyways, so I can't use this to count primes infinitly... Basically, this friend of mine's maths teacher had some algorithm that could test if a number was prime easily... within something like a few seconds for a multi-digit number... considering that 80,029 took 5 seconds, a ten digit number or so (he was working in that range...) would take minutes on my macro... I was wondering if anybody had heard of an algorithm like this... I'll do some research, see if I can find anything...

(Hey, if you're really interested in this, google for "mersenne primes," it's not a good use of your distributed computing time though...)

JBI, I did a copy n paste of your code, and VBA doesn't recognise ListBox as a variable type (or something :-D), I searched the helpfile to find it calling ListBox a control, here's the helpfile entry:

Displays a list of values and lets you select one or more.

Remarks

If the ListBox is bound to a data source, then the ListBox stores the selected value in that data source.

The ListBox can either appear as a list or as a group of OptionButton controls or CheckBox controls.

The default property for a ListBox is the Value property.

The default event for a ListBox is the Click event.

Note You can't drop text into a drop-down ListBox.


Anyways guys, so it looks as though the prime array is the only way I'm gonna get this to do primes indefinitly, anyone remember what a "400" box means?

Thanks for the help,
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Wed Jun 25, 2003 1:40 pm

Very nice jbi! You taught erastothenes sieve in 5 mins!

You could post your packed flag version, there would be some fun bit twiddling there.
moog
Gerbil Elite
 
Posts: 836
Joined: Wed Jun 11, 2003 9:10 am
Location: Here

Postposted on Wed Jun 25, 2003 2:08 pm

JBI, I did a copy n paste of your code, and VBA doesn't recognise ListBox as a variable type (or something ),

Actually, that was liquidsquid's VB code. Not sure what the problem is; as I've already mentioned, it has been quite a while since I've done any VB...
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37514
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Wed Jun 25, 2003 2:22 pm

Yeah, that's who I meant :-P

Cheers anyways to the both of ya again,
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Postposted on Wed Jun 25, 2003 2:32 pm

You could post your packed flag version, there would be some fun bit twiddling there.

Here's a packed flag version:
Code: Select all
//  Sieve of Eratosthenes - packed bit flag version

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

// Define a useful type
typedef unsigned char byte;

// Macro SetBit(a, n) sets the nth bit of byte array a
#define SetBit(a, n) ((a)[(n) >> 3] |= (1 << ((n) & 0x7)))

// Macro TestBit(a, n) tests the nth bit of byte array a
#define TestBit(a, n) (((a)[(n) >> 3] & (1 << ((n) & 0x7))) != 0)

int main(int argc, char *argv[])
{

    // Make sure user specified upper bound
    if (argc > 1)
    {

        // Get upper bound from command line
        int n = atoi(argv[1]);
        if (n > 0)
        {

            // Allocate array and clear it
            int alen = (n + 1) / 8 + 1;
            byte *a = new byte[alen];
            for (int i = 0; i < alen; i++)
                a[i] = 0;

            // Find the primes
            int sqrtn = (int) sqrt(n);  // in case compiler is stupid
            for (int i = 2; i <= sqrtn; i++)
            {
                if (!TestBit(a, i))  // i is prime
                {
                    for (int j = i * 2; j <= n; j += i)
                        SetBit(a, j);
                }
            }

            // Print them all out
            for (int i = 2; i <= n; i++)
            {
                if (!TestBit(a, i))
                    printf("%d\n", i);
            }

            // Deallocate the array
            delete [] a;

        }

    }
    else
    {
        printf("please specify highest desired prime\n");
    }

    return 0;

}

This version uses roughly 1/8th the amount of memory compared to my original C++ version, for a given upper bound. Using an actual C++ class to represent the bit array would have been more elegant, but this kludgy "old school C" way of doing it should run faster. :D

Interestingly enough, this version actually runs somewhat faster than the original one, in spite of the extra bit twiddling. I'll bet this is because it is less constrained by memory bandwidth, since the flag array is 1/8th the size.

Edit: Fixed up the macro syntax a bit, to make them less likely to break if someone else takes this code and modifies it.
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37514
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Wed Jun 25, 2003 2:55 pm

Interestingly enough, this version actually runs somewhat faster than the original one, in spite of the extra bit twiddling. I'll bet this is because it is less constrained by memory bandwidth, since the flag array is 1/8th the size.


Right. Better cacheability too. And if the compiler really sucks then the array was bools of 32bits and now your packing allows for 32X bandwidth!

Nice work!

Edit: It hit me that we could skip over the even numbers. 1/2 iterations, 1/2 array size. Anyway, don't bother unless you've got time to kill.
moog
Gerbil Elite
 
Posts: 836
Joined: Wed Jun 11, 2003 9:10 am
Location: Here

Postposted on Wed Jun 25, 2003 3:04 pm

The cacheability will still suck once the upper bound gets large enough. The algorithm repeatedly sweeps through a large array with a stride length that changes on each sweep -- pretty much a worst-case scenario for cache management.

I think it's been quite a while since any C++ compilers used 32-bit bools, though I do seem to recall encountering at least one that did this some years back. The current versions of Visual C++ and g++ store bool in a single byte, as you would expect.

Wow... have we beaten this dead horse enough yet? :lol:

Edit: Yes, eliminating the even flags would cut the array size in half. It only eliminates extra work on the very first sweep (the one to mark all of the even numbers) though. I'll leave this as an exercise for the reader. :D
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37514
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Postposted on Wed Jun 25, 2003 4:09 pm

Benchmark!

I call dibs!
Forge
Darth Gerbil
 
Posts: 7959
Joined: Wed Dec 26, 2001 7:00 pm
Location: SouthEast PA

Postposted on Wed Jun 25, 2003 7:04 pm

just brew it! wrote:This version uses roughly 1/8th the amount of memory compared to my original C++ version, for a given upper bound. Using an actual C++ class to represent the bit array would have been more elegant, but this kludgy "old school C" way of doing it should run faster. :D

Interestingly enough, this version actually runs somewhat faster than the original one, in spite of the extra bit twiddling. I'll bet this is because it is less constrained by memory bandwidth, since the flag array is 1/8th the size.


I'd be willing to bet a sizeable amount of the money in my wallet that even the bit-twiddled program is mainly memory bound... Let's be honest, how taxing is a few bits of integer arithmetic and bit-changing for a CPU?

If you can (and want to, incidentally), run it on a SDRAM system of similar CPU spec.... I reckon it'd be a fair bit slower, but that's just my instinct talking...

LiquidSquid/anyone, any ideas on why my array syntax is screwed?
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 7:00 pm
Location: The nearest pub

Next

Return to Developer's Den

Who is online

Users browsing this forum: No registered users and 1 guest