Skip to content

“hello world” seemed too boring

Lest you think that computers are powerful enough these days to churn through any inefficient algorithm in some reasonable amount of time…
my first python program:

#primebrute.py -- for when you want to know some silly things about prime numbers, and don't know how long it takes
def maxv(lst=[]):
     curmax = lst[0]
     for i in lst:
          if lst[i] > curmax:
               curmax = lst[i]
     return curmax

def sum(lst=[]):
     cursum = 0
     for i in lst:
          cursum = cursum + i
     return cursum

def avg(lst=[]):
     return sum(lst) / len(lst)

diffs = []
lastprime = 2;
for n in range(2, 10**6):
     for x in range(2, n):
          if n % x == 0:
               # we don't /really/ want to take up that much space...
               # print n, 'equals', x, '*', n/x
               break
          else:
               # loop fell through without finding a factor
               diff = n - lastprime
               diffs.append(diff)
               lastprime = n
               print n, 'is a prime number (diff:', diff, ')'
print

#so now diffs is filled with the differences between the first primes
# less than 1000000
#the goal, now, is to generate a separate list showing a rolling average of the differences
# between the primes

rollFactor = 5000
rolledavgs = []
for n in range(0,len(diffs),rollFactor/4):
     start = n - (rollFactor / 2)
     if start < 0:
          start = 0
     end = n + (rollFactor / 2)
     if end > len(diffs):
          end = len(diffs)
     rolledavgs.append(avg(diffs[start:end]))
     print 'avg. of diff',n,' +- ',rollFactor/2,':',rolledavgs[len(rolledavgs)-1]
print

#now, it's simple: we just need to make a little histogram of our list of rolled averages
m = maxv(rolledavgs)
scalefactor = 34 / m
for i in rolledavgs:
     print i,
     for j in range(i*scalefactor):
          print '*',
     print

O(n^3) takes a long time where n= 1,000,000 no matter what your processor is*

I’ve been hearing good things about Python for a while, and I figured it was time to give it a shot. It seems interesting; I particularly like what they’ve done with for loops. I don’t know how well I’ll like it after getting to know it more, but my first impression is positive.


* The benefit of quantum processing is that it reduces the processing time of most algorithms to O(1); if you have an algorithm which is O(n^3) on your quantum processor, it’ll take about as long to run on your machine as it will on mine (assuming that on my machine the processing time is still O(n^3) and hasn’t inflated to something ludicrous like O(n^n^n), in which case it would effectively never finish on my machine)

RSS feed

Comments

No comments yet.

Sorry, the comment form is closed at this time.