On Sun, 1 Apr 2012, Dennis Boone wrote:
I WAS LOOKING FOR A SMALL SOFTWARE PROJECT TO DO ON
VINTAGE HARDWARE.
Howzbout: ADD lower case capability! It's a fun project for any vintage
hardware. You might need to add another bit to the display RAM, and maybe
even develop a set of escapade-codes for switching case.
THE HUNT DIDN'T GO ON LONG BEFORE IT HIT ME.
ONLY ONE THING COULD
POSSIBLY DO: CALCULATE PRIME NUMBERS ON MY TRUSTY PR1ME 5340
MINICOMPUTER.
SINCE THE PR1ME ARCHITECTURE IS TARGETED AT SCIENTIFIC USERS, AN
ARBITRARY PRECISION NUMBER PACKAGE IS NOT READILY AVAILABLE. AFTER A
FEW TESTS, I CONCLUDED THAT THE HARDWARE QUAD PRECISION FLOATING POINT
Oh.
April first.
I WAS NOT WILLING TO SIMPLY CODE UP SOME
MATHEMATICIAN'S DUBIOUS
ALGORITHM -- I WANTED TO BE SURE NOT TO MISS ANY VALID PRIMES.
INSTEAD, I CAREFULLY DESIGNED MY OWN, AND VALIDATED IT USING A LARGE
CORPUS OF TEST DATA (ALL INTEGERS BETWEEN 1 AND 100). THE CODE USES A
NUMBER OF ADVANCED TECHNIQUES FOR ACCURACY AND HIGH PERFORMANCE,
INCLUDING:
* SEQUENTIAL SEARCH FOR POSSIBLE FACTORS.
* CYCLING TO THE NEXT POTENTIAL PRIME IMMEDIATELY UPON DISCOVERING AN
INTEGRAL FACTOR, INSTEAD OF CONTINUING TO TEST ALL REMAINING POSSIBLE
FACTORS.
* TESTING ONLY FACTORS LESS THAN HALF OF THE CANDIDATE PRIME.
You can cut that down way further by only testing factors less than or
equal to the square root. NO. Do NOT compute the square root. If you
think about it, there are prime opportunities to test the square of the
factor while checking with it, and not trying any more factors when you
have tried with a factor whose square is greater than the candidate.
* NOT TESTING FOR DIVISIBLENESS BY 1
ONE IS
PRIME. You can not come up with a positive integer divisor of one
other than itself or one.
* TESTING ONLY ODD CANDIDATE PRIMES.
* HAND-CODED IN PR1ME ASSEMBLER.
You might find better performance using INTEGERs instead of float.
In fact, try doing it by elimination.
Make a list of all the numbers that you want to test. Delete 4. add 2 and
delete 6. add 2 and delete 8. keep deleting all of those multiples of 2.
(You COULD make your array of candidates out of only odd numbers. . . )
Now delete 6, 9, 12, 15, 18, and the rest of the multiples of 3.
now delete 4, 8, 12 WAITAMINIT! ONLY delete multiple of the numbers that
haven't been deleted!
When the square of the number whose multiples you are deleting exceeds the
number, you are DONE.
USING THESE METHODS, I WAS ABLE TO ACHIEVE REMARKABLE
PERFORMANCE. IN
TESTING, THE PROGRAM EXECUTED ABOUT 3,086,913,596 DECIMAL DIVISION
OPERATIONS IN 11 HOURS AND 17 MINUTES, FINDING THE FIRST 10544 PRIME
NUMBERS, AT A RATE OF ABOUT 75994 DIVISIONS PER SECOND, AND NEARLY 935
PRIMES PER HOUR. TRY _THAT_ IN BASIC ON YOUR IBM 5150!
Not hard with DEFINT and paging in banks of the array.
THE SOURCE PROGRAM, AND AN OUTPUT FILE WITH START AND
END DATE STAMPS
AND THE FOUND PRIMES, ARE AVAILABLE FOR PERUSAL AT
http://yagi.h-net.msu.edu/primenumbers/.
HOW AM I SUIPPOSED TO TYPE THAT INT THE BROWSER USING AN UPPERCASE ONLY
KEYBOARD?