I Think I’m Crazy!

February 23, 2018

# prime number generator
 
# Global associative array _primegen stores the state of all active prime
# number generators. It is a two-dimensional array with an identifier (a
# positive integer) in its first dimension and an element of state in its
# second dimension, intended only for internal use by the prime number
# generator; it should not be modified by client code. The possibilities are:
#
#     _primegen[k, "init"] -- initial primes 2 and 3 to "prime" the pump (sorry!)
#     _primegen[k, "pgen"] -- the k-number of the internal prime number generator
#     _primegen[k, "c"]    -- the next candidate prime number
#     _primegen[k, "p"]    -- the current largest sieving prime
#     _primegen[k, p]      -- the stride associated with sieving prime p where
#                             p in (3, 5, 7, 11, ...); notice no stride for 2
#
# Global variable _primegen_counter is the largest currently-unused k; it is
# initially zero.
#
# Function primegen_init() creates a new prime number generator that returns
# primes starting from zero. It returns a state number (the k of  the _primegen
# array). Function primegen(k) returns the next prime number from prime number
# sequence k, and resets the _primegen[k] generator state for the next call to
# primegen(k).
 
function primegen_init(    k) {
    k = _primegen_counter++
    _primegen[k,"init"] = 2
    return k }
 
function primegen(k,    pgen,c,p,q,s,m) {
 
    # initial primes 2 and 3
    if ((k,"init") in _primegen) {
        if (_primegen[k,"init"] == 2) {
            _primegen[k,"init"] = 3
            return 2 }
        else {
            delete _primegen[k,"init"]
            return 3 } }
 
    # set up for remaining primes after 3
    if (! (k,"pgen") in _primegen) {
        pgen = primegen_init()
        _primegen[k,"pgen"] = pgen
        p = primegen(pgen)
        p = primegen(pgen)
        _primegen[k,"c"] = 3
        _primegen[k,"p"] = p
        _primegen[k,p] = p+p }
 
    # main prime generation routine
    pgen = _primegen[k,"pgen"]
    c = _primegen[k,"c"]
    p = _primegen[k,"p"]; q = p * p
    while (1) {
        c += 2
        if ((k,c) in _primegen) {
            s = _primegen[k,c]; m = c + s
            delete _primegen[k,c]
            while ((k,m) in _primegen) m += s
            _primegen[k,m] = s }
        else if (c < q) {
            _primegen[k,"c"] = c
            _primegen[k,"p"] = p
            return c }
        else {
            s = p + p; m = c + s
            while ((k,m) in _primegen) m += s
            _primegen[k,m] = s
            p = primegen(pgen); q = p * p } } }
 
BEGIN { ps = primegen_init()
        for (p = primegen(ps); p < 100; p = primegen(ps)) {
            pcount++; printf "%d ", p }
        printf "%d\n", pcount
        for (x in _primegen) print x, _primegen[x] }
Advertisements

Pages: 1 2

2 Responses to “I Think I’m Crazy!”

  1. Zack said

    Back in the pre-Julia era, when I was still a student, I created an encryption system using Quick Basic (QB). It was embarrassingly slow (though part of it was due to the computing power of the time). The algorithm was sound but it would take forever to run on a large file.

    Also, a few years later, still in the pre-Julia era, I created a new statistical framework using MATLAB. It worked well, but only for data up to 500 data points or so, making it quite impractical.

    I wouldn’t say that I was crazy to try out these things, but I was definitely ignorant!

  2. Sandy Roman said

    AWK! I am soo happy to see this mentioned here and used. I learned it while working in the Unix environment at a particle accelerator.

    We had dipoles to bend the beam around and of course we had syncrotron radiation from the acceleration required to bend the beam. So we imaged the syncrotron light and put it on a video monitor. The image had information about the beam’s physical bunch length. So I took a background image, then subtracted it from the beam image. Summing all pixels in the vertical gave us an intensity profile. That could be fit to a 5 degree of freedom hyperbola using Cramer’s rule. I did most of the video work in AWK. I might have used it for the fit as well, or done it longhand.

    It was proof of principle and it worked great. I liked AWK, because it is a compact language and you can keep the whole thing in your head. Programs are small and easy to get things done with, great for small projects, small datasets and one line programs.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: