John Brooks
2018-03-18 18:56:21 UTC
I wrote an optimized Apple IIGS program to calculate all the prime numbers up to 16834. Finding primes via the SoE method is a common CPU benchmark and I wanted to see how fast the GS could compute primes.
The fastest previous versions for the 6502/65c02/65802/65816 was 140 usec @ 1 MHz.
This version is over 2x faster, finding the 1899 primes in ~59 usec @ 1 MHz, and ~24 usec @ 2.8 MHz.
The program is 245 bytes long, consisting of the sieve routine at 192 bytes, and a 53 byte test program which runs the sieve 100 times and prints out the number of primes found: 1899.
00/2000:A2 64 18 FB C2 30 86 40 20 35 20 C6 40 D0 F9 38
00/2010:FB 20 3A FF 18 FB C2 30 78 BA 9B A9 00 60 1B 7B
00/2020:AB D0 01 1A BA 10 F9 BB 9A 4B AB AA EB 58 FB 20
00/2030:24 ED 4C 8E FD 0B 3B 8D EC 20 A9 FF 7F 1B A2 4E
00/2040:00 86 42 7B 1A AA EB A8 7B 3A 5A 8B 48 48 0B 5A
00/2050:DA DA 5A DA 5A 5A DA DA 5A 48 0B 48 DA 0B 48 DA
00/2060:DA 5A 48 5A 5A DA 0B 5A 48 5A 48 DA DA 5A DA DA
00/2070:5A DA 5A 48 DA 0B 5A 48 0B 48 DA 0B 5A DA 48 C6
00/2080:42 D0 C7 7A 0B 0B E2 14 A9 00 20 5B A9 05 60 1B
00/2090:A9 3C 60 A0 0A 85 E2 C8 84 AE 84 B3 84 B8 84 BD
00/20A0:84 C2 84 C7 84 CC 84 D1 C2 10 BA 1B 08 69 00 00
00/20B0:1B 08 69 00 00 1B 08 69 00 00 1B 08 69 00 00 1B
00/20C0:08 69 00 00 1B 08 69 00 00 1B 08 69 00 00 1B 08
00/20D0:69 00 00 10 D6 9A E2 10 C8 10 04 C8 C8 30 0C 98
00/20E0:0A 69 00 00 85 E2 AB D0 F2 80 AC A9 00 00 1B 2B
00/20F0:4B AB C2 34 60
The sieve routine at $2035 is called in native 65816 mode with 16-bit AXY, B=0, D=0.
Enjoy.
-JB
@JBrooksBSI
00/2000: A2 64 LDX #64
00/2002: 18 CLC
00/2003: FB XCE
00/2004: C2 30 REP #30
00/2006: 86 40 STX 40
00/2008: 20 35 20 JSR 2035
00/200B: C6 40 DEC 40
00/200D: D0 F9 BNE 2008 {-07}
00/200F: 38 SEC
00/2010: FB XCE
00/2011: 20 3A FF JSR FF3A
00/2014: 18 CLC
00/2015: FB XCE
00/2016: C2 30 REP #30
00/2018: 78 SEI
00/2019: BA TSX
00/201A: 9B TXY
00/201B: A9 00 60 LDA #6000
00/201E: 1B TCS
00/201F: 7B TDC
00/2020: AB PLB
00/2021: D0 01 BNE 2024 {+01}
00/2023: 1A INC
00/2024: BA TSX
00/2025: 10 F9 BPL 2020 {-07}
00/2027: BB TYX
00/2028: 9A TXS
00/2029: 4B PHK
00/202A: AB PLB
00/202B: AA TAX
00/202C: EB XBA
00/202D: 58 CLI
00/202E: FB XCE
00/202F: 20 24 ED JSR ED24
00/2032: 4C 8E FD JMP FD8E
00/2035: 0B PHD
00/2036: 3B TSC
00/2037: 8D EC 20 STA 20EC
00/203A: A9 FF 7F LDA #7FFF
00/203D: 1B TCS
00/203E: A2 4E 00 LDX #004E
00/2041: 86 42 STX 42
00/2043: 7B TDC
00/2044: 1A INC
00/2045: AA TAX
00/2046: EB XBA
00/2047: A8 TAY
00/2048: 7B TDC
00/2049: 3A DEC
00/204A: 5A PHY
00/204B: 8B PHB
00/204C: 48 PHA
00/204D: 48 PHA
00/204E: 0B PHD
00/204F: 5A PHY
00/2050: DA PHX
00/2051: DA PHX
00/2052: 5A PHY
00/2053: DA PHX
00/2054: 5A PHY
00/2055: 5A PHY
00/2056: DA PHX
00/2057: DA PHX
00/2058: 5A PHY
00/2059: 48 PHA
00/205A: 0B PHD
00/205B: 48 PHA
00/205C: DA PHX
00/205D: 0B PHD
00/205E: 48 PHA
00/205F: DA PHX
00/2060: DA PHX
00/2061: 5A PHY
00/2062: 48 PHA
00/2063: 5A PHY
00/2064: 5A PHY
00/2065: DA PHX
00/2066: 0B PHD
00/2067: 5A PHY
00/2068: 48 PHA
00/2069: 5A PHY
00/206A: 48 PHA
00/206B: DA PHX
00/206C: DA PHX
00/206D: 5A PHY
00/206E: DA PHX
00/206F: DA PHX
00/2070: 5A PHY
00/2071: DA PHX
00/2072: 5A PHY
00/2073: 48 PHA
00/2074: DA PHX
00/2075: 0B PHD
00/2076: 5A PHY
00/2077: 48 PHA
00/2078: 0B PHD
00/2079: 48 PHA
00/207A: DA PHX
00/207B: 0B PHD
00/207C: 5A PHY
00/207D: DA PHX
00/207E: 48 PHA
00/207F: C6 42 DEC 42
00/2081: D0 C7 BNE 204A {-39}
00/2083: 7A PLY
00/2084: 0B PHD
00/2085: 0B PHD
00/2086: E2 14 SEP #14
00/2088: A9 00 20 LDA #2000
00/208B: 5B TCD
00/208C: A9 05 60 LDA #6005
00/208F: 1B TCS
00/2090: A9 3C 60 LDA #603C
00/2093: A0 0A LDY #0A
00/2095: 85 E2 STA E2
00/2097: C8 INY
00/2098: 84 AE STY AE
00/209A: 84 B3 STY B3
00/209C: 84 B8 STY B8
00/209E: 84 BD STY BD
00/20A0: 84 C2 STY C2
00/20A2: 84 C7 STY C7
00/20A4: 84 CC STY CC
00/20A6: 84 D1 STY D1
00/20A8: C2 10 REP #10
00/20AA: BA TSX
00/20AB: 1B TCS
00/20AC: 08 PHP
00/20AD: 69 00 00 ADC #0000
00/20B0: 1B TCS
00/20B1: 08 PHP
00/20B2: 69 00 00 ADC #0000
00/20B5: 1B TCS
00/20B6: 08 PHP
00/20B7: 69 00 00 ADC #0000
00/20BA: 1B TCS
00/20BB: 08 PHP
00/20BC: 69 00 00 ADC #0000
00/20BF: 1B TCS
00/20C0: 08 PHP
00/20C1: 69 00 00 ADC #0000
00/20C4: 1B TCS
00/20C5: 08 PHP
00/20C6: 69 00 00 ADC #0000
00/20C9: 1B TCS
00/20CA: 08 PHP
00/20CB: 69 00 00 ADC #0000
00/20CE: 1B TCS
00/20CF: 08 PHP
00/20D0: 69 00 00 ADC #0000
00/20D3: 10 D6 BPL 20AB {-2A}
00/20D5: 9A TXS
00/20D6: E2 10 SEP #10
00/20D8: C8 INY
00/20D9: 10 04 BPL 20DF {+04}
00/20DB: C8 INY
00/20DC: C8 INY
00/20DD: 30 0C BMI 20EB {+0C}
00/20DF: 98 TYA
00/20E0: 0A ASL
00/20E1: 69 00 00 ADC #0000
00/20E4: 85 E2 STA E2
00/20E6: AB PLB
00/20E7: D0 F2 BNE 20DB {-0E}
00/20E9: 80 AC BRA 2097 {-54}
00/20EB: A9 00 00 LDA #0000
00/20EE: 1B TCS
00/20EF: 2B PLD
00/20F0: 4B PHK
00/20F1: AB PLB
00/20F2: C2 34 REP #34
00/20F4: 60 RTS
The fastest previous versions for the 6502/65c02/65802/65816 was 140 usec @ 1 MHz.
This version is over 2x faster, finding the 1899 primes in ~59 usec @ 1 MHz, and ~24 usec @ 2.8 MHz.
The program is 245 bytes long, consisting of the sieve routine at 192 bytes, and a 53 byte test program which runs the sieve 100 times and prints out the number of primes found: 1899.
00/2000:A2 64 18 FB C2 30 86 40 20 35 20 C6 40 D0 F9 38
00/2010:FB 20 3A FF 18 FB C2 30 78 BA 9B A9 00 60 1B 7B
00/2020:AB D0 01 1A BA 10 F9 BB 9A 4B AB AA EB 58 FB 20
00/2030:24 ED 4C 8E FD 0B 3B 8D EC 20 A9 FF 7F 1B A2 4E
00/2040:00 86 42 7B 1A AA EB A8 7B 3A 5A 8B 48 48 0B 5A
00/2050:DA DA 5A DA 5A 5A DA DA 5A 48 0B 48 DA 0B 48 DA
00/2060:DA 5A 48 5A 5A DA 0B 5A 48 5A 48 DA DA 5A DA DA
00/2070:5A DA 5A 48 DA 0B 5A 48 0B 48 DA 0B 5A DA 48 C6
00/2080:42 D0 C7 7A 0B 0B E2 14 A9 00 20 5B A9 05 60 1B
00/2090:A9 3C 60 A0 0A 85 E2 C8 84 AE 84 B3 84 B8 84 BD
00/20A0:84 C2 84 C7 84 CC 84 D1 C2 10 BA 1B 08 69 00 00
00/20B0:1B 08 69 00 00 1B 08 69 00 00 1B 08 69 00 00 1B
00/20C0:08 69 00 00 1B 08 69 00 00 1B 08 69 00 00 1B 08
00/20D0:69 00 00 10 D6 9A E2 10 C8 10 04 C8 C8 30 0C 98
00/20E0:0A 69 00 00 85 E2 AB D0 F2 80 AC A9 00 00 1B 2B
00/20F0:4B AB C2 34 60
The sieve routine at $2035 is called in native 65816 mode with 16-bit AXY, B=0, D=0.
Enjoy.
-JB
@JBrooksBSI
00/2000: A2 64 LDX #64
00/2002: 18 CLC
00/2003: FB XCE
00/2004: C2 30 REP #30
00/2006: 86 40 STX 40
00/2008: 20 35 20 JSR 2035
00/200B: C6 40 DEC 40
00/200D: D0 F9 BNE 2008 {-07}
00/200F: 38 SEC
00/2010: FB XCE
00/2011: 20 3A FF JSR FF3A
00/2014: 18 CLC
00/2015: FB XCE
00/2016: C2 30 REP #30
00/2018: 78 SEI
00/2019: BA TSX
00/201A: 9B TXY
00/201B: A9 00 60 LDA #6000
00/201E: 1B TCS
00/201F: 7B TDC
00/2020: AB PLB
00/2021: D0 01 BNE 2024 {+01}
00/2023: 1A INC
00/2024: BA TSX
00/2025: 10 F9 BPL 2020 {-07}
00/2027: BB TYX
00/2028: 9A TXS
00/2029: 4B PHK
00/202A: AB PLB
00/202B: AA TAX
00/202C: EB XBA
00/202D: 58 CLI
00/202E: FB XCE
00/202F: 20 24 ED JSR ED24
00/2032: 4C 8E FD JMP FD8E
00/2035: 0B PHD
00/2036: 3B TSC
00/2037: 8D EC 20 STA 20EC
00/203A: A9 FF 7F LDA #7FFF
00/203D: 1B TCS
00/203E: A2 4E 00 LDX #004E
00/2041: 86 42 STX 42
00/2043: 7B TDC
00/2044: 1A INC
00/2045: AA TAX
00/2046: EB XBA
00/2047: A8 TAY
00/2048: 7B TDC
00/2049: 3A DEC
00/204A: 5A PHY
00/204B: 8B PHB
00/204C: 48 PHA
00/204D: 48 PHA
00/204E: 0B PHD
00/204F: 5A PHY
00/2050: DA PHX
00/2051: DA PHX
00/2052: 5A PHY
00/2053: DA PHX
00/2054: 5A PHY
00/2055: 5A PHY
00/2056: DA PHX
00/2057: DA PHX
00/2058: 5A PHY
00/2059: 48 PHA
00/205A: 0B PHD
00/205B: 48 PHA
00/205C: DA PHX
00/205D: 0B PHD
00/205E: 48 PHA
00/205F: DA PHX
00/2060: DA PHX
00/2061: 5A PHY
00/2062: 48 PHA
00/2063: 5A PHY
00/2064: 5A PHY
00/2065: DA PHX
00/2066: 0B PHD
00/2067: 5A PHY
00/2068: 48 PHA
00/2069: 5A PHY
00/206A: 48 PHA
00/206B: DA PHX
00/206C: DA PHX
00/206D: 5A PHY
00/206E: DA PHX
00/206F: DA PHX
00/2070: 5A PHY
00/2071: DA PHX
00/2072: 5A PHY
00/2073: 48 PHA
00/2074: DA PHX
00/2075: 0B PHD
00/2076: 5A PHY
00/2077: 48 PHA
00/2078: 0B PHD
00/2079: 48 PHA
00/207A: DA PHX
00/207B: 0B PHD
00/207C: 5A PHY
00/207D: DA PHX
00/207E: 48 PHA
00/207F: C6 42 DEC 42
00/2081: D0 C7 BNE 204A {-39}
00/2083: 7A PLY
00/2084: 0B PHD
00/2085: 0B PHD
00/2086: E2 14 SEP #14
00/2088: A9 00 20 LDA #2000
00/208B: 5B TCD
00/208C: A9 05 60 LDA #6005
00/208F: 1B TCS
00/2090: A9 3C 60 LDA #603C
00/2093: A0 0A LDY #0A
00/2095: 85 E2 STA E2
00/2097: C8 INY
00/2098: 84 AE STY AE
00/209A: 84 B3 STY B3
00/209C: 84 B8 STY B8
00/209E: 84 BD STY BD
00/20A0: 84 C2 STY C2
00/20A2: 84 C7 STY C7
00/20A4: 84 CC STY CC
00/20A6: 84 D1 STY D1
00/20A8: C2 10 REP #10
00/20AA: BA TSX
00/20AB: 1B TCS
00/20AC: 08 PHP
00/20AD: 69 00 00 ADC #0000
00/20B0: 1B TCS
00/20B1: 08 PHP
00/20B2: 69 00 00 ADC #0000
00/20B5: 1B TCS
00/20B6: 08 PHP
00/20B7: 69 00 00 ADC #0000
00/20BA: 1B TCS
00/20BB: 08 PHP
00/20BC: 69 00 00 ADC #0000
00/20BF: 1B TCS
00/20C0: 08 PHP
00/20C1: 69 00 00 ADC #0000
00/20C4: 1B TCS
00/20C5: 08 PHP
00/20C6: 69 00 00 ADC #0000
00/20C9: 1B TCS
00/20CA: 08 PHP
00/20CB: 69 00 00 ADC #0000
00/20CE: 1B TCS
00/20CF: 08 PHP
00/20D0: 69 00 00 ADC #0000
00/20D3: 10 D6 BPL 20AB {-2A}
00/20D5: 9A TXS
00/20D6: E2 10 SEP #10
00/20D8: C8 INY
00/20D9: 10 04 BPL 20DF {+04}
00/20DB: C8 INY
00/20DC: C8 INY
00/20DD: 30 0C BMI 20EB {+0C}
00/20DF: 98 TYA
00/20E0: 0A ASL
00/20E1: 69 00 00 ADC #0000
00/20E4: 85 E2 STA E2
00/20E6: AB PLB
00/20E7: D0 F2 BNE 20DB {-0E}
00/20E9: 80 AC BRA 2097 {-54}
00/20EB: A9 00 00 LDA #0000
00/20EE: 1B TCS
00/20EF: 2B PLD
00/20F0: 4B PHK
00/20F1: AB PLB
00/20F2: C2 34 REP #34
00/20F4: 60 RTS