Short: Fastest Sieve of Eratosthenes prime test Author: madmax@uni-paderborn.de (Dirk Held) Uploader: madmax@uni-paderborn.de (Dirk Held) Type: misc/math Replaces misc/math/aYaSieve* Version: 1.9 AndYetAnotherSieve ~~~~~~~~~~~~~~~~~~ (the fastest prime-sieve at this time) (at least on the Amiga) On my system (A4k40+FPU+MMU,25 MHz, 16 MB RAM) it tests primes upto 240.000.000 in about 106.4 seconds ! (+ 9.2 counting) 100.000.000 in about 41.1 seconds, (+ 3.9 " ) 10.000.000 in about 3.5 seconds, (+ 0.4 " ) 1.000.000 in about 0.3 seconds, (+ 0.04 " ) So itīs about 50% faster than the previous Version. The (internal) Version 1.8 was ready to upload some months ago, but i thought about, using BitField- Operations instead of BitChangeOpeations, to gain some speed, but actualy this Version is only smaller (476 Bytes) and not faster (sight). I was just too lazy, to complete it earlier ;-). Is this the End of the contest ? Iīve 0.5 ideas left.....|-)) well..i could save about 6%, but the Size of the Program would be about 38 KB... More 3% are possible with a Program-size of 540 KB.....;-) The time cost is about O(n*1.35) = O(n), this means, if the Programm calcs to a 10 times higher Number, the Program needs 13.5 times longer. The Runtime seems to be slightly superlinear. The Program needs about Number DIV 16 Bytes Memory. Usage: (now with standard Amiga-Arguments) aYaSieve NUMBER/N,DISPLAY/S,TEST/S,LEN=LINELEN/K/N,HELP/S,FROM/K/N,DUMP/K/F HELP prints Usage NUMBER to test 2..Number for primality (Number < 2^31) DISPLAY all Primes are printed TEST enter Numbers to factorize LEN Linewidth FROM prints Primes starting with n DUMP saves the BitField to file, if NUMBER was given, or loads it from the file, if no number was given. aYaSieve isnīt completely written in *pure* Amiga Modula-II anymore. I used the builtin Assembler where appropriate. "Amiga Modula-2 Compiler 68881, 4.301d, 19.06.94, Đ AMSoft" Marcel Timmermans Cyclone-Compiler should do, too (with some slightly modifications of the Import-List and the Compiler-Options). This Program runs on every Amiga with Kick 2.0. (aYaSieve.000 for M680x0, and aYaSieve.020 for x >= 2) The Source is included now. It is strictly ALLOWED to produce any aYaSieve-like program without my permission :). (But who really cares about it ? Proggis like these are`n usefull to factorise LARGE numbers (i.e. 100 or more digits), so why bother. Try KillPrime on Aminet instead (Hi Brice:). *IMPORTANT* NO (more?) BUGs ups, there used to be a Bug in Version 1.1 (thank you Brice), but itīs already converted to a feature, before you (Brice) noticed it. Due to internal limitations, my program at least sieves to 18481, so wYgimtYmw (what You get, is more than You might wanted). ups2, there is another not so obvious bug in version 1.3. If you enter >aYaSieveNT -v The Program runs wild...|-\ If you have questions drop me a mail. Hellos and Greetings going out to: - Peachy 4 his ß-testing - Brice Allenbrand, he forced me, to work even harder....(puuh) - Bill J. Phillips (he tested my Program (Version 1.1) on his A3000/60 its about 3 times faster then. - Larry Deering, for the inspiration he gave me, with his BlackKeySieve, which he programmed on his urgh mhmm gnaagnagna .... PeeCee. It may be even faster than mine (8-(. Although i canīt test or believe it yet, because i havenīt the Source to port it to the Amiga, nor do i have a C-Version of my Proggi, to port it to other Platforms (yet). - everyone, whoīs able to code a at least 3% faster Version of Eratothenesīs Sieve (according to Big-o Notation) - those guys, which prefer a REAL 32 Bit (or even 64 (SGI-O^2...)) Maschine, Aetschi-Baetschis and Buuhs going out to: - nobody ============================= Archive contents ============================= Original Packed Ratio Date Time Name -------- ------- ----- --------- -------- ------------- 7396 4333 41.4% 28-Oct-97 11:14:34 +aYaSieve.000 6572 4153 36.8% 28-Oct-97 11:14:34 +aYaSieve.020 24393 5873 75.9% 28-Oct-97 11:14:34 +aYaSieve.Mod 4085 2102 48.5% 28-Oct-97 11:14:34 +aYaSieve.ReadMe 1047 392 62.5% 28-Oct-97 11:14:34 +Init_BF.Mod -------- ------- ----- --------- -------- 43493 16853 61.2% 29-Oct-97 00:01:36 5 files