fastest primes / News: Recent posts

Fastest Primes v.90 has been released.

Bug fix:
_1. Fixed crash under specific conditions.

Speed increase:
_1. Removed some redundant code. I did not actually do speed testing, but the first work unit should be a tiny bit faster.

Upgraded 3rd party packages:
_1. ting 3.0.0
_2. fastformat 0.7.1-alpha-9
_3. stlsoft 1.9.117

Notes:
_1. Only VS2010 project is included with the source since I have not used the VS2008 project in a long time and it would definitely not work any more.... read more

Fastest Primes v.90 and v.90b are in the works.

Planned changes are:
v.90
Bug fixes:
_1. Crashes when using 1 thread and 1 work unit - confirmed when finding primes between 0 and 1,000,000, 2,000,000, and 4,000,000.

Speed increases:
_1. Remove some unneeded code.

v.90b
Speed increases:
_2. Implement SSE2 code. This should provide a significant speed increase.

1. Updated libraries:
___a: STLSOFT 1.9.112
___b: FASTFORMAT 0.7.1(alpha 7)
___c: libting 0.11.0
2. Changed VC++ version checking in libraries so they will work with Visual Studio 2011
3. Unrolled main sieve loop. This gave a 25-28% speed increase over v0.89.
4. Added options for array size adjustment.
___a: Increase work unit size by 120 numbers
___b: Increase number of work units.
___c: Auto select according to memory footprint
5. Made it so that the range searched is no longer required to be an exact multiple of 120. You can start/end wherever you want.
6. Changed range search so that when starting number is below 120, it will use the same code as when starting from 0.
7. Did some code cleanup and made some changes to the Visual Studio project settings.... read more

The changes for the next release of Fastest Primes include:

1. No more having to use multiples of 120 for the range you are searching in.
2. The above will offer 3 different options for adjusting the array size when needed to work.
3. The current timer is not as accurate as I would like. I am looking into different timer functions to change this.

Version 0.89 includes these changes:

1. All multiples of primes below 73 are eliminated via pre-defined wheel sieves before calculation begins. This portion of the program is multithreaded just like the main calculation is.
2. Added setup time output.

The added wheel sieving resulted in ~28% calculation speed increase. Even when including the setup time, it is ~19% faster overall than version 0.88, which didn't include or check the setup time.

Version .89 is just about ready to be released. After doing some testing, it looks like this version is going to be about 28% faster than v.88.

Before calculation begins, all multiples of primes below 73 are now being wheel sieved out from pre-calulated sieves.

Wheel sieveing time has not been checked in the past. I tested overall time including wheel sieveing and even with the wheel sieving time included, v.89 is still 4.3% faster than v.88 is when only counting the calculation time in v.88. Changing the pre-calculation wheel-sieving to using more than one thread may make the overall time even lower.

v.89 will use more wheel sieving than previous versions. So far this appears to be showing a pretty good speed increase.

Currently, only multiples of 7, 11, and 13 are wheel sieved out before other calculations. (multiples of 2, 3, and 5 are never there because of the mod 30 scheme).

It looks like wheel sieving will help a lot up to a certain point. Past that it looks like it will end up using too much RAM and would possibly slow down to the point where my current method would be faster.

The build instructions have an error in them. Whether or not you are building the fasformat library, you will need the FASTFORMAT_ROOT and STLSOFT environment variables in order to compile fastest primes.

Changes in this release include:

1. Moved to a mudulo 30 scheme to pack results from 30 numbers into each byte (120 numbers in each unsigned int - 32-bits). This is up from 64 numbers in each unsigned int. A memory savings of ~47% is realized by this change.

2. Instead of multiples of 64, multiples of 120 are used for the range of numbers to find primes in.

3. Upped the max range to 192b for each search. 8GB RAM is highly recommended if you want to try this large of a search.... read more

v.88 will be released very soon.

Initial thoughts on the 32-bit speedup were wrong. I hadn't finished changing the code and it was giving the wrong results. Current speedup on both 32-bit and 64-bit is ~20% with 64-bit being about 4x as fast as the 32-bit code once you go past the 32-bit limit.

The next release is coming along nicely.

RAM usage has dropped by about 47%.

The 32-bit version has sped up a lot more than I had expected. For example, when searching for Primes between 1 and
~4 billion using a single thread, the calculation time went from a little over 5 seconds down to 0.125 seconds.

But I am having performance issues with the 64-bit version. Calculation time has more than doubled for some reason. Before I release v.88 I will have this fixed. The performance increase should be about the same as the 32-bit version.

Changes in this release include:

1: Output to file now saves to the same directory/folder that the primes executable is in.

2: Compile bug fixes for Linux - stuff I forgot to change/check before I uploaded v.87b

3: Updated compile instructions

Notes:
1: I was not able to test a 64-bit version the Linux binary due to an apparent bug in the current release of the g++ compiler for Debian. It compiles but throws a segfault when trying to look for primes above 256. 32-bit works as expected.... read more

The next release will have:
1: File output when used will always output to the folder/directory that the primes executable is in instead of it going to the current working directory. This should work on both Windows and *nix systems.
2: I think that there are a couple bugs specific to the Linux code that were oversights on my part. Those wil lbe fixed as well.

After this next release I will work on getting the memory usage down even more. More bit packing should result in about 47% drop in RAM usage and should also give a nice speed boost as well.

Changes in this release:

1: Fixed a weird bug that was breaking some of the timing output from being displayed.

2: Upgraded from Ting 0.5.1 to 0.6.0.

3: The source code will now compile under Linux again.

Changes in this release include:

1: Now using buffered output when outputting to the console and to file. Output to console is now about 23-38x faster than in v.86b. The range of difference is because I was getting a wide rand of times with the unbuffered output. Buffered output time is a lot more stable.

2: Switched from using cout to the Fastformat library for output to file. Output to file is now about 5x faster than in v.86b. Adding buffered output contributed a small amount to this speed increase.

Changes in this release:
1. Switched counting primes when outputting the primes to do it the same way it is when just counting the primes.
2. Changed the way the primes are read and output - this was necessary because of the first change. These first two changes resulted in about 20% increase in speed of both output to screen and to file.
3. The version number is actually correct in this version.... read more

The changes in this release are:

#1. When only counting the number of primes generated, the count time is now about 31x faster than v.85.
On my machine, when counting the number of primes generated between 1 and 4 billion, the count time went from 3.85s to 0.11s.

#2. Changed from bthread to Ting 0.5.1 for the threading class.

#3. Added pre-elimination of multiples of 11 and 13 to help speed up prime number generation.... read more

Version 0.85 changes include:

#1. 2x - 4x faster than version 0.83 depending on the calculation
#2. RAM usage has been cut in half.
#3. Input calculation has been redone yet again. Due to bit packing, multiples of 64 are now used.
#4. Available search ranges have been raised significantly.
#5. Program will exit after 3 failed attempts to allocate memory for the calculation. If it exits, it means that there wasn't enough RAM available.

Found that there is an apparent bug when using a large number of work units. Basically, some numbers are being skipped.

I was able to fix some of it, but some numbers are still being skipped. For that reason, unless I can figure out how to keep the remaining numbers from being skipped, I will not release another version until I rewrite the code to the faster/more efficient way of sieving.

The next version will be released within the next couple of days.

Memory usage has been cut in half. This has also helped increase the speed, especially when finding larger ranges of primes.

There are one or two more optimizations that will be added and/or tweaked before I post the next release.

Arbitrary number support will come in hopefully one or two releases after v0.90.

The reason being is I have found a much more efficient primes generator and will be basing v0.90 off of that. Compared to my current code, it is over 3 times as fast running on one thread than mine running on 4 threads.

The next release will be v0.90 and will have arbitrary number support via the MPIR library.

Quite a few changes and bug fixes have gone into this release.

Changes :
1. Changed from a multidimensional array to a basic array in order to slightly lower RAM usage.

2.Re-did the order of some calculations in all sieves in order to slightly lessen the amount of work that has to be done.

A slight speed increase of ~2% should be expected.

Bug Fixes:
1. Fixed a bug that was introduced in v0.80 that was causing the 64-bit range function to break out right after starting. It will now calculate the correct primes again.... read more

Some minor changes have been made in this release.

Performance should be exactly the same as v0.80.

#1: Thanks to my bro for making slight changes for *nix compilation as well as testing in Linux.

#2: Added version info when program starts.

#3: Added a pause at the end of the program so it doesn't just exit when finished - for those who just run it instead of opening up a command prompt first.

#4: Added an instruction file in the source code release for compilation information.... read more

A lot of changes have gone into this release.

You can now:
Output the results to a file - a result file with primes between 1 and 4 billion is around 1.7GB

Output to the screen (the only option before)
Output only calculation time(good for benchmarking)
Output calculation time and number of primes found.

The maximum number for finding primes when starting at 33+ has been raised from 63,000,000,000 to 18,446,744,073,709,551,584. You can still only find a maximum range of 16,000,000,000 at one time when starting at 33+ but this will be changed in a later release.... read more