## Prime Number Calculator

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

Moderators: SecretSquirrel, just brew it!

### Prime Number Calculator

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 DoubleDim PrimeDiv As DoubleDim DivValue As VariantDim flag As IntegerSub CalcPrime()PrimeTest = Range("A2")PrimeDiv = 0flag = 0DoPrimeTest = PrimeTest + 1PrimeDivision:flag = 0PrimeDiv = 1While PrimeDiv <= (PrimeTest) / 2DivValue = PrimeTest / PrimeDivIf DivValue = 1 Thenflag = flag + 1    ElseIf DivValue = Int(DivValue) Then            flag = flag + 1                ElseIf DivValue = PrimeTest Then                        flag = flag + 1    End IfPrimeDiv = PrimeDiv + 1WendIf flag = 1 Then GoTo PrimeConfirmIf flag <> 1 Then PrimeTest = PrimeTest + 1GoTo PrimeDivisionPrimeConfirm:Range("A2") = PrimeTestflag = 0Loop Until 1 > 1 + 1End 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

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

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

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.

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.
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

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

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

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

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

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

And that root 3 trick reference, that was muyuubyou,
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

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

Hmm...I see. 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

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 = 0flag = 0ArrayLoadDoPrimeTest = PrimeTest + 1PrimeDivision:flag = 0ArrayRef = 1While PrimeArray(ArrayRef) <= (PrimeTest) / 2DivValue = PrimeTest / PrimeArray(ArrayRef)If DivValue = 1 Thenflag = flag + 1    ElseIf DivValue = Int(DivValue) Then            flag = flag + 1                ElseIf DivValue = PrimeTest Then                        flag = flag + 1    End IfArrayRef = ArrayRef + 1WendIf flag = 1 Then GoTo PrimeConfirmIf flag <> 1 Then PrimeTest = PrimeTest + 1GoTo PrimeDivisionPrimeConfirm:Range("A2") = PrimeTestCells(ArrayRef, 3) = PrimeTestflag = 0Loop Until 1 > 1 + 1End Sub`

Code: Select all
`Sub ArrayLoad()DoPrimeArray(ArrayNumber) = Cells(ArrayNumber, 3)ArrayNumber = ArrayNumber + 1Loop Until Cells(ArrayNumber, 3) = 0End 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

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

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 ninitialize all elements of a to 0for 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!
Gold subscriber

Posts: 40810
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Aaaargh!!! C!!!!

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

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

IntelMole wrote:Aaaargh!!! C!!!!

Aaaargh!!! VB!!!

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

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!
just brew it!
Gold subscriber

Posts: 40810
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

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

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.... ,
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

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

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...

Hope that helps!
just brew it!
Gold subscriber

Posts: 40810
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Very cool JBI. You may have made me curious enough I might have to try this one out myself.
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

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

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

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

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

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

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: 2483
Joined: Wed May 29, 2002 10:49 am
Location: New York

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

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.
just brew it!
Gold subscriber

Posts: 40810
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

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 LongDim a() As BooleanDim 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 IfEnd Sub`

-LS
liquidsquid
Minister of Gerbil Affairs

Posts: 2483
Joined: Wed May 29, 2002 10:49 am
Location: New York

...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!
Gold subscriber

Posts: 40810
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

JBI, I take it that's a no

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

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 ), 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

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

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!
Gold subscriber

Posts: 40810
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Yeah, that's who I meant

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

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 typetypedef 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.

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!
Gold subscriber

Posts: 40810
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

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

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?

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.
just brew it!
Gold subscriber

Posts: 40810
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Benchmark!

I call dibs!
Forge
Lord High Gerbil

Posts: 8091
Joined: Wed Dec 26, 2001 7:00 pm
Location: SouthEast PA

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.

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