1. 20

Moulick (মৌলিক – Bengali for Prime) is an Arduino powered mathematical toy that endlessly computes primes and shows fun statistics about them as it goes along. Watching primes born was never more exciting, or slow. Moulik starts from 2 and takes you primally all the way out to 10 decimal digits at a recklessly unsafe speed (for an Arduino, that is)*.

Also, a demo video and code repo

*10 decimal digits will not be achieved in a single lifetime. Your mileage may vary. Offer void where prohibited by law. Primes are facts of nature and can not be owned, bought, sold or patented.

  1.  

  2. 4

    That is amazing! I never do things like that with my arduinos because my projects are always either too simple for arduino or too complex for them (more often issues are with timing rathen than processing power though).

    Do you have stats on how much overhead does the whole graphic drawing add to the prime calculation?

    1. 4

      Thanks!

      I use a simple memory-less division algorithm (wheel factorization) though while researching I found several cool probabilistic algorithms on that page. The time taken to compute a prime increases as the square root of the number while the graphics overhead remains constant.

      Your question is cool in the context of figuring out at what number does the time spent drawing become less than, say 1%, of the compute time. I don’t have that value, but once you get to about a million, you can see that the graphics refreshes faster than the compute.

      Update: Actually, I take it back - most of the numbers are not prime, so their testing ends very quickly (e.g. half the numbers are even) and drawing that line representing 1/k of possible divisors probably takes a lot longer than the actual compute.

      I’d say you are right if you were thinking that the drawing overhead dominates. I’ll try by switching off the clock animation and just printing the numbers and see how different that is and get back.

      1. 2

        @Hamcha

        The timing test was a bit surprising for me:

        N is the integer tested i.e. how many numbers we did
        G is with graphics on, NG is with graphics OFF, which means
        we only update the display if we find a prime, and the update 
        is restricted to drawing the number's digits on the screen.
        
        **The timing is given in the format XX.YY where XX is min and YY is sec**
        
        timing_data = [
            #  N       G    NG
            (1000,    0.11,   0.03),
            (5000,    0.53,   0.14),
            (10000,   1.46,   0.28),
            (20000,   3.34,   1.00),
            (30000,   5.24,   1.35),
            (40000,   7.15,   2.11),
            (50000,   9.08,   2.48),
            (60000,  11.02,   3.26),
            (70000,  12.56,   4.06),
            (100000, 18.51,   6.14)
        ]
        

        When I plot this both lines are very linear with the graphics ON line having a slope (or rather inverse slope) of 88.41 numbers/s and the graphics OFF line is 267.37 numbers/s (about 3x faster)

        So I think, at least for these lower numbers the graphics drawing causes a 3x slowdown.

        Now, about the linearity - it’s possible that I don’t have a large enough range and it LOOKS linear in this short segment. However, there are two opposing pulls to this computation. As the number gets larger though in the worst case we have to do sqrt(N) operations, we mostly do 1 operation (divide by 3) or two operations (divide by 2 and 3) and so on AND the prime numbers get sparser and sparser.

        These two may counteract to make an average constant rate for testing numbers.

        It would be fun to work this out.

        Best -Kaushik

        PS. The following code will suffice to plot the data in an IPython notebook

        %matplotlib inline
        import matplotlib.pyplot as plt
        
        import math
        # A convenient way to represent time as min, sec by using the decimal point
        # XX.YY -> XX * 60 + YY
        def T(s):
            s, m = math.modf(s)
            return m * 60 + s * 100
        
        # N = integer tested
        # G - with graphics
        # NG - without graphics
        # Here 
        timing_data = [
            #  N       G    NG
            (1000,    0.11,   0.03),
            (5000,    0.53,   0.14),
            (10000,   1.46,   0.28),
            (20000,   3.34,   1.00),
            (30000,   5.24,   1.35),
            (40000,   7.15,   2.11),
            (50000,   9.08,   2.48),
            (60000,  11.02,   3.26),
            (70000,  12.56,   4.06),
            (100000, 18.51,   6.14)
        ]
        
        x = [n[0] for n in timing_data]
        y1 = [T(n[1]) for n in timing_data]
        y2 = [T(n[2]) for n in timing_data]
        
        plt.plot(x, y1, '.-', label='With graphics')
        plt.plot(x, y2, '.-', label='No graphics')
        plt.legend(loc='best')
        
        1. 2

          Nice, this was exactly what I was looking for (although I would have tested it by writing the number on the serial console instead to eliminate the graphics overhead completely).

          I.. definitely did not expect it to look that linear either, just like you I thought the overhead would get less and less significant the higher the numbers.