Quantcast

Results 1 to 8 of 8

Thread: A pointless toy, or a useful benchmark? Generating prime numbers on the Genesis.

  1. #1
    Comrade as in friend. Master of Shinobi ComradeOj's Avatar
    Join Date
    Dec 2012
    Location
    New Mexico, USA
    Age
    24
    Posts
    1,325
    Rep Power
    56

    Default A pointless toy, or a useful benchmark? Generating prime numbers on the Genesis.

    I'm learning a bit of python in a class I'm taking and one of the example programs caught my attention. It was a simple loop that calculated prime numbers. It worked was by brute-force dividing a given number by every number below it and seeing if any result was without a remainder. I wondered how well the good ol' Genesis would do at this task.

    I basically did the same thing, but with some optimizations:
    1: Skip any even numbers. Even numbers are never prime.
    2: Don't divide by any even numbers.
    3: Don't attempt to divide any number by anything greater than half of itself. (ex: don't try to divide 299 by 298, start at 149 instead)


    In total, these tricks made calculating prime numbers 2.8X faster than not using any tricks. One other trick would be to skip numbers ending in 5, but I wasn't really able to pull this off.
    As a consequence of these optimizations, the program is unable to calculate prime numbers lower than 11 (1,2,3,5,7). I think it's worth it though, because of the huge boost to calculating larger numbers.
    I would imagine there are faster ways to generate prime numbers than the method. I don't really know a lot about this, and just put this together for fun.

    I recorded a video showing a 5 minute run on different modded consoles and emulators. Largest prime number and relative performance is shown at the end.
    As far as I know, every number my program spits out is prime, and no prime numbers are skipped. There may be errors though, so let me know if you catch any. The largest number that can be generated is 65521, after that the counter rolls over.



    The first is a stock system. The second with a 10mhz overclock, the third with a 10mhz overclocked 68010. The two emulators I tried were BlastEm and Fusion.

    The 68010 was fastest as expected, being able to divide faster than the 68000. BlastEm came very close to matching the stock system. Fusion doesn't seem to know how slow dividing on the 68k really is.

    Download link with ROM and source: http://www.mode5.net/download/prime%...0generator.zip
    Last edited by ComradeOj; 10-03-2018 at 10:29 PM.
    Modded consoles:
    Master System (v7040) with s-video & direct AV out
    Model 1 with 10mhz overclock & halt switches
    Model 1 with 10mhz 68010
    Model 2 VA2.3 with unfiltered Mega Amp, & s-video
    Model 3 VA1 with compatibility fixes & s-video
    32X with s-video
    Visit my web site at www.mode5.net
    Or my collection of homebrew Genesis games, programs, and music on SEGA-16!

  2. #2
    For great justice! Outrunner Tor Landeel's Avatar
    Join Date
    Jan 2011
    Age
    37
    Posts
    545
    Rep Power
    17

    Default

    That's very interesting!
    Thank you for sharing the source, I don't know much of python but it could still be of use to learn something
    ***** トル・ランディール ******
    Cadash Arcade Colors hack:
    https://www.romhacking.net/hacks/3905/
    Out Run Arcade Colors hack:
    https://www.romhacking.net/hacks/3940/
    *****************************

  3. #3
    Hedgehog-in-Training Hedgehog-in-TrainingRoad Rasher
    Join Date
    Sep 2016
    Posts
    299
    Rep Power
    7

    Default

    Eratosthenes' sieve is one of the faster ways, it works by multiplication (which can be converted to addition).

  4. #4
    Raging in the Streets Sik's Avatar
    Join Date
    Jan 2011
    Posts
    3,242
    Rep Power
    61

    Default

    Quote Originally Posted by ComradeOj View Post
    3: Don't attempt to divide any number by anything greater than half of itself. (ex: don't try to divide 299 by 298, start at 149 instead)
    If I recall correctly the actual limit is the square root of the numberů but good luck computing it at decent speed on the 68000 (there are tricks for that, but dividing more numbers may still end up being faster, not sure). Although you can probably keep calculating the "current" square root by computing the next square as you scan through numbers.

  5. #5
    WCPO Agent
    Join Date
    Aug 2014
    Location
    France
    Posts
    800
    Rep Power
    35

    Default

    roce is right. But it requires you fix an upper bound N to your list before, and it is limited by your amount of RAM (even if you can use 1 bit per number, so it's virtually unlimited).

    Sik is right too, you only have to go to the square root, and his advice is good too (keep track of the next square).

  6. #6
    Comrade as in friend. Master of Shinobi ComradeOj's Avatar
    Join Date
    Dec 2012
    Location
    New Mexico, USA
    Age
    24
    Posts
    1,325
    Rep Power
    56

    Default

    Quote Originally Posted by Tor Landeel View Post
    That's very interesting!
    Thank you for sharing the source, I don't know much of python but it could still be of use to learn something
    The source is actually written in 68K ASM. It was just a python example that gave me the idea.
    Modded consoles:
    Master System (v7040) with s-video & direct AV out
    Model 1 with 10mhz overclock & halt switches
    Model 1 with 10mhz 68010
    Model 2 VA2.3 with unfiltered Mega Amp, & s-video
    Model 3 VA1 with compatibility fixes & s-video
    32X with s-video
    Visit my web site at www.mode5.net
    Or my collection of homebrew Genesis games, programs, and music on SEGA-16!

  7. #7
    Road Rasher
    Join Date
    Apr 2013
    Location
    SF Bay Area, California
    Posts
    301
    Rep Power
    20

    Default

    Neat! I guess the fact that BlastEm is pretty close to hardware here suggests that the divide microcode hasn't changed much from the version in the patent. The reason it's a little slower is that my emulation of refresh wait states is currently primitive. It mostly assumes that the 68K is always on the bus, except for when it's waiting on the VDP (either a write that is blocked due to a full FIFO or DMA). This assumption is pretty close to true for most instructions, but multiply and divide instructions result in a lot of time in which the 68K is off the bus. Refresh cycles that take place during these periods are effectively free and I don't take that into account currently.

  8. #8
    Road Rasher
    Join Date
    Apr 2013
    Location
    SF Bay Area, California
    Posts
    301
    Rep Power
    20

    Default

    For what it's worth, I suspect Genesis Plus GX would also be pretty close, but would err in the other direction. It has accurate divide cycle counts (or at least ones that match the patent microcode anyway), but no refresh wait state emulation.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •