Ulam spiral sketcher using NumPy and tkinter optimisations

ulam.py

from itertools import count, cycle
from math import ceil, sqrt
from numpy import arange, array, full, ones, insert, where
from numpy import append as ap
from time import perf_counter as pf
from time import sleep
from tkinter import Canvas, Tk, constants

root = Tk()
# root.attributes('-fullscreen', True) # make fullscreen window
n, w, h = 1, 1300, 1300 # n=2 because 1 messes with the algo, starting number
canvas = Canvas(root, bg="black", width=w, height=h)
ct = canvas.create_text

text_size, text_font = 2, "Hack" # text size
pixels_to_jump = text_size/0.9 # not sure why this value works!
upto = 50_000 # 100M will take ~2.3GB RAM and 20s on powerful machine
ANIMATION_DELAY = 0.0125 # def: 0.05
PRINT_CHAR = '❖' # '×'

primes = arange(2,upto+1)
isprime = ones((upto-1),dtype=bool)
R, U, L, D = ((pixels_to_jump, 0), 0), ((0, -pixels_to_jump), 90), \
        ((-pixels_to_jump, 0), 180), ((0, pixels_to_jump), 270)

run_times = {}

# print_me = arange(1,upto)
# ^ uncomment for numbers, also switch the ct() in draw loop
print_me = full((len(primes)) + 1, ' ')

def prime6(): # new prime generation algo
    """Prime number generation algo"""

    time_it(1)
    for factor in primes[:int(sqrt(upto))]:
        if isprime[(factor)//2]: # if it is an even number
            isprime[((factor*3)-2)::factor]=0 # find a factor amongst the existing primes
    insert(primes[isprime],0,1) # no factors found, add to list of primes
    time_it(1)

def direction():
    """Legacy function, will be removed next version"""
    for _ in range(1, int(sqrt(upto))):
        # return cycle((R, U, L, D)) # movement sequence
        return cycle((L, D, R, U)) # movement sequence
# ((-pixels_to_jump, 0), 180), ((0, pixels_to_jump), 270)...

def distance():
    """Legacy function, will be removed next version"""
    # loop increments x every 2 loops
    for x in range(1, int(sqrt(upto))+1):
        for _ in (0, 1):
            yield x
# 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6...

def transform_array():
    """Star of the show. Matches, folds and trims"""
    global print_me, primes, isprime

    time_it(2)
    # list comprehension to match PRINT_CHAR if prime, otherwise ' '
    time_it(3)
    print_me = [PRINT_CHAR if isprime[_] else ' ' for _ in range(len(primes))]
    time_it(3)

    # Pre-made list of what used to be distance(), named so for readability later, sorry!
    # should be 'distance_list'
    d_l = [x for x in range(1, int(sqrt(upto))+1) for y in (0, 1)]

    time_it(5)
    # fold matrix into the required shape ([[1],[2],[3, 4],[5, 6]...])
    # although print_me[X:Y] looks like a mess, the maths is simple:
    # X = sum(d_l[0:i] = WHAT HAS BEEN READ ALREADY
    # Y = sum(d_l[0:i]) + d_l[i] = HOW FAR NEEDS TO BE READ FROM X 
    # putting these two together, we can cobble together the required output
    temp_array = [print_me[(sum(d_l[0:i])) : sum(d_l[0:i]) + d_l[i]] \
                            for i in range(0, len(d_l))]
    time_it(5)

    # trim empty elements from array
    time_it(6)
    print_me = [_ for _ in temp_array if len(_) != 0]
    time_it(6)

    temp_array = []
    time_it(2)

def time_it(index):
    """Timing function, takes int for index,
       retrieve values from array run_times[n]"""
    if index in run_times: # number exists, stop timer
        run_times[index] = (pf() - run_times[index]) * 1000
        return run_times[index] # return milliseconds

    else: # index does not exist
        if (0 > index) or (index > 10): # value error
            return "Enter value 1-10."
        else: # start timer
            run_times[index]=pf()

def draw_spiral():
    """Draw the spiral on screen"""
    text_x = w // 2; text_y = h // 2;

    time_it(7)
    for _, c, coords in zip(range(len(print_me)), distance(), direction()):
        delta_x, delta_y = coords[0][0], coords[0][1] 
        offset_x = ((len(print_me[_]) * delta_x) / 0.75)
        offset_y = ((len(print_me[_]) * delta_y) / 0.75)

        text_x += delta_x + offset_x
        text_y += delta_y + offset_y
        # this expression works for int array, DO NOT DELETE
        # ct(text_x, text_y, fill="white", text=(str(print_me[_])[1:-1]),\
        #                         font=(text_font, text_size), angle = coords[1])
        # this expression works for str arrays, DO NOT DELETE
        ct(text_x, text_y, fill="white", text=(' '.join(print_me[_])),\
            font=(text_font, text_size), angle = coords[1], justify=constants.CENTER)
        
        text_x += delta_x + offset_x
        text_y += delta_y + offset_y

        root.update_idletasks() # used to update canvas in realtime
        canvas.pack()
        sleep(ANIMATION_DELAY) # recom: (upto / (upto * 20)) i.e 0.05
    time_it(7)

    # canvas.pack()
    # canvas.update()
    # canvas.postscript(file="ulam.ps", colormode='color')
    root.mainloop()

def print_stats():
    """Print time stats on console"""
    ANIMATION_TIME = (len(print_me) * (ANIMATION_DELAY * 1000))

    print(f"\nTimes for {len(primes)+1:,} numbers;\n\t  {(len(primes[isprime])):,} primes:")
    # str(primes[isprime][-1:])[1:-1] is a ridiculous convolution,
    # to print the value without brackets, wrapped in int() to comma separate
    print(f"[1] primes  : {(run_times[1] * 1000):.2f}µs (max: {int(str(primes[isprime][-1:])[1:-1]):,})")
    print(f"[2] xform   : {run_times[2]:.2f}ms")
    print(f"[3]  --match: {run_times[3]:.2f}ms")
    print(f"[4]  --list : n/a") # {run_times[4] * 1000:.2f}µs")
    print(f"[5]  --fold : {run_times[5]:.2f}ms")
    print(f"[6]  --trim : {run_times[6]:.2f}ms")
    print(f"[7]  draw   : {(run_times[7] - ANIMATION_TIME):,.2f}ms (+{(run_times[7]/1000):.2f}s animation)")
    print(f"    TOTAL   : {(run_times[1] + run_times[2] + run_times[7]) - ANIMATION_TIME:,.2f}ms\n")

def main():
    prime6()
    transform_array()
    draw_spiral()

    ## Stats:
    # if foo:
    print_stats()

if __name__ == "__main__":
    main()

########################
##### DOWN & DIRTY #####
########################
## Records (50K, delay=0)
## v1.0-
# primes: 295.13µs
#  xform: 11840.98ms    80%
#   --match: 4702.20ms  --40%
#   -- fold: 6112.60ms  --52%
#   -- trim: 624.96ms
#   draw: 2.87s         20%
#  total: 14.71s
# ------------------------------
## v1.1- 207x faster
# [1] primes  : 270.85µs
# [2] xform   : 4.59ms      2574x
# [3]  --match: 2.91ms      1621x
# [4]  -- list: 14.25µs
# [5]  -- fold: 1.56ms      3918x
# [6]  -- trim: 0.09ms      6933x
# [7]  draw   : 66.30ms     43x (not even optimised yet)
#        TOTAL: 71.16ms     207x
# ------------------------------
## v1.1- a real challenge (upto=100M, delay=0)
# [1] primes  : 1,267,025.34µs
# [2] xform   : 8,951.02ms
# [3]  --match: 5,496.00ms
# [4]  -- list: 514.88µs
# [5]  -- fold: 3,298.45ms
# [6]  -- trim: 155.93ms
# [7]  draw   : 8,631.62ms
#     TOTAL   : 18,849.67ms
# -------------------------------

ULAM.py

Draw large Ulam spirals using NumPy and tkinter optimisations

My take on the Ulam spiral. The Ulam spiral is a graphical respresentation of
a set of prime numbers. The spiral proceeds from the inside out, in a square
counter clockwise direction.

The spiral reveals a striking pattern of many diagonal, horizontal and lines.
In this 200x200 represenation of Ulam spiral, a high density
of primes is easily visible, vs a spiral with random odd numbers. Ulam spiral
is connected to problems in number theory, such as Landau's problems.

---

The two main parameters that can be adjusted in code:

• upto: determines the total number of points that will be drawn
• ANIMATION_DELAY: determines the animation delay

Running the Python script will produce a drawing window and some print
stats to your terminal after the window is closed.

v1.0 utilises tkinter canvas for drawing the spiral. This is suboptimal but
was kept for the sake of the challenge. Next version will utilise matplotlib
instead, which is much more appropriate for the task.

v1.1 brings an incredible performance gain of 207x and much smaller
memory footprint due to use of computed values, see Records section for
more details. Despite not being optimised, draw_spiral() also saw a large
boost in performance, therefore there is no need to switch to matplotlib().
This function yet remains to be optimised in v1.2, along with finding the
solution for Bloody 4. There are also some remains of matrix crossover.

v1.1.1 current is an incremental update, featuring small optimisations, aesthetic
adjustments and code clean up.

Note: This script requires NumPy and tkinter libraries, type pip install numpy tkinter in terminal to install.

ulam_final.mp4