Short: Sieve of Eratosthenes prime test
Author: madmax@uni-paderborn.de (Dirk Held)
Uploader: madmax uni-paderborn de (Dirk Held)
Type: misc/math
Version: 2.01
Replaces: misc/math/aYaSieve
Architecture: m68k-amigaos
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 " )
This Version isnīt faster, or has more features than the previous Version. I
just merged the two Versions (68000/680x0) into one Soure and removed by the
way a stupid bug in the 680x0-Version ...-(
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:
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 the 68000 and aYaSieve.020 for the 68020/30/40/60)
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*
If you have questions drop me a mail.
Hellos and Greetings going out to:
- 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