For those who need a programming challenge

arooaroo · 2007-01-01 02:01:37

Every now and again we see people positively begging for inspiration for programming tasks to improve programming skills/experience or merely curing boredom.

I've just seen an interesting site for the mathematically inclined - and let's face it, who isn't?

http://www.projecteuler.net/index.php?section=view

I haven't started myself but you have to register and then you can earn points on some sort of leader board. The above link is merely the list of challenges to see if it whets your appetite.

Dusty · 2007-01-01 17:18:31

arooaroo wrote:

I've just seen an interesting site for the mathematically inclined - and let's face it, who isn't?

Me. I'm definitely not mathematically inclined.

A similar site to your link that even allows you to make a little cash or get a job is topcoder.com.

Dusty

Basu · 2007-01-01 18:25:20

I've already been doing this for quite a while. Solved about ten of them coz I don't get much free time nowadays. Here's a tip for those who want to have a shot: Most of the prime no. problems become dead easy if you write a good prime no. generator/checker algorithm.

noriko · 2007-01-03 14:54:43

hmm i sux at maths but i think after 8 years i might start liking it again ..
i wrote this little python script to the prime numbers... it could be more effecient but....

the forum code tags are screwing ith it...
i uploaded it to http://lmu.j2k.cc/primen.py instead
think as a benchmark i might use it to generate 1 billion prime numbres heheh ....

Basu · 2007-01-03 15:16:50

Use the 6n+-1 optimization. Makes it faster, especially when you go up to higher numbers.

DeliQ · 2007-01-03 16:05:31

Basu wrote:

Use the 6n+-1 optimization. Makes it faster, especially when you go up to higher numbers.

Basu, I've never heard of this optimization, can you explain what you mean with it?

--Ronny

freigeist · 2007-01-03 16:16:11

DeliQ wrote:

Basu wrote:
Use the 6n+-1 optimization. Makes it faster, especially when you go up to higher numbers.
Basu, I've never heard of this optimization, can you explain what you mean with it?
--Ronny

I think he is talking about this
This should drastically reduce the numbers you have to check.

Basu · 2007-01-03 16:33:56

That's right. Of course, the important thing to remember is that not all 6n+-1 numbers are primes, so you still have to do an actual check.
Tip 2: you only have to check if the no. in question is divisible by nos upto it's square root.

noriko · 2007-01-03 19:38:11

yeah i originally thought about the +- theory.. except i thought of 2n+-1 instead ... guess i shouldn't have given up on it for being too slow..
as far as optimization goes, it would prolly not be much faster, as i am already only sending odd numbers...

i did some experiment on the +- theory and I've found that there is a sequence... if i am correct then i will be able to pretty much eliminate the +- theory all together while making it even faster.. i.e ( i may be wrong here ) but adding 2,4 or 6 is faster than *n+|- , and also appending a string is faster .. i just need to work out the frequency of false positives ... if that's possible then it will eliminate the need to even check the generated number...

FYI, all probable primes (what the *n+- generates),
(starting with 11) is +[2, 4, 2, 4, 4, 2, 2, 6, 4]
on my mention of appending strings.. the sequence is to
append[1, 3, 7, 9,| 3, 7, 9,| 1, 7]
fi.e 11, 13, 17, 19,| 23, 27, 29,| 31, 37 .. repeat
[EDIT]
prime numbers are of range (ending); [1, 3, 7, 9];
so no 2 as primes are always odd...or 5...
also, noticed that the first number of each group is a factor of every number in their group. so 1,2 .. but of course 1 doesn't count so we have to work out the odd numbers lol.. dunno where i'm going with this so i'll stop
[/EDIT]

i have to admit, numerology has ruled my life for the most part, but i never knew maths could be so interesting... lol

game[tce] time .. hope i see AqD so i can pwn him again hehe

noriko · 2007-01-05 00:35:47

i've done it. .. i think,

dunno if anyone is still interested but whatever ...
proc: athlon xp-m 2800 [hovering] 2.6-2.8 GHz

for a test on the original code with the 6n+-1 optim. i stopped at 50000th prime and that took about 18 minutes...

this algorythm primen.r2, generates and prints 100008 prime numbers in

..time /port/bin/primen.py 100008
...
100008: 1299827

real    1m19.249s
user    0m44.512s
sys     0m0.993s

if the code below is screwed ... it's uploaded > http://lmu.j2k.cc/primen.py

arooaroo · 2007-01-05 00:56:01

Can you explain this line?

q = l*.079

I believe you that it works, but I'm intrigued as to why!

noriko · 2007-01-05 09:52:35

well i needed a away to get a value to check against, to prevent going above sqrt(n) ... yes, u might say y not just use sqrt(n) .. well the simple answer is, i would be calculating that value on each loop, now when it gets to larger numbers, that starts being a problem...
so i decided to find a somewhat generic value that i can generate once this means at the start the generation isn't as good as it could be but it doesn't slow down too much as the numbers larger...

7.9% is as small as the value gets if we want to get correct primes < 1000 ... when i got some more time i will do some more testing, because as the the number gets larger that percentage drops ...

will make a revision now ... with my first ever attempt at commenting

Basu · 2007-01-05 10:49:47

Wow! That's smart. one more little trick to tuck up my sleeve. Hope you don't mind ;-)

noriko · 2007-01-05 11:13:20

ok, rev3 is done and tested ...i assume it's even faster, maybe not by much .. i have some jfs_dbug issues so cpu is a constant ++80% ..
will test it after reboot ...

http://lmu.j2k.cc all three rev. are there .. it's been commented,
hope it's readable and not over commented, it' literally the first time i've ever commented any code ... i 'll try to implement this in c next week if i got time ... i think it'd be interesting to see just how fast this thing can go hehe ....

[EDIT]
WOW!! well all i can say is .. wow, i did not expect it to be that fast ....

time /port/bin/primen.r3.py 100008
...
100008: 1299827

real    0m26.681s
user    0m13.067s
sys     0m0.652s

this is what primen.r2 was ..

..time /port/bin/primen.py 100008
...
100008: 1299827

real    1m19.249s
user    0m44.512s
sys     0m0.993s

u work out the difference ...

[/EDIt]

:twisted:

funny thing is, it can go even faster ... even in python...

noriko · 2007-01-05 11:45:23

Basu wrote:

Wow! That's smart. one more little trick to tuck up my sleeve. Hope you don't mind ;-)

not at all x) .. in fact i'm blushing, i never knew i was his smart i've been told so, but u know people say many things to make u feel bettr lol... hehe

beejayzed · 2007-01-05 12:13:00

noriko wrote:

i've done it. .. i think,
dunno if anyone is still interested but whatever ...
proc: athlon xp-m 2800 [hovering] 2.6-2.8 GHz
for a test on the original code with the 6n+-1 optim. i stopped at 50000th prime and that took about 18 minutes...
this algorythm primen.r2, generates and prints 100008 prime numbers in
..time /port/bin/primen.py 100008
...
100008: 1299827

real    1m19.249s
user    0m44.512s
sys     0m0.993s
if the code below is screwed ... it's uploaded > http://lmu.j2k.cc/primen.py

def prime(n): 
   global p,l,on,q 
   s = str(n) 
   z = int(s[len(s)-1]) 
    
   if (z <> 5 and z % 2 <> 0 ): 
      for o in on: 
         if (n % o == 0): return False 
      if ( on[len(on)-1] <= q ): on.append(n) 
      p += 1 
      print "%i: %i" % (p,n)

Wouldn't adding additional conditional checks just slow it down?
Try removing the whole last number check (including if check) section and just add 2,5 to the beginning of the list (so that they are checked first), leaving on = [2,5,3,7] when first intialised.
This speeds it up on my machine.
Making q an int should also help.
I found making q = int(l ** 0.5 * 4) works for numbers up to about 1 or 2 million and is quite a bit quicker.

def findprimeplace(numprime):
    count = 2
    number = 1    
    four = 1
    while count < numprime:
        if four:
            number += 4
            four = 0
        else: 
            number += 2
            four = 1
        numsqrt = int(number ** 0.5)
        divisor = 3
        while divisor <= numsqrt:
            if number % divisor == 0: break
            divisor += 2
        else: count += 1
    return number

The above is my prime number code, it returns a number at the given place. I did try hacking in a primelist checker (but different to yours in that it checked it against a sqrt) in the past, but I found plain number checking to be faster.
With regard to speed, the above is about the same as yours without the optimisations(excluding q = ) and a little slower with them for smaller numbers (about < 20000). Mine is faster for bigger numbers, I tested with 100000, but I think it holds true for 50000 +.
However, with the changed initial q value, the speed of your code is faster.

Putting this together has been great for helping me learn python. Last time I programmed was in qbasic... (and a bit of c)
My machine is a celeron, 900mhz

noriko · 2007-01-05 12:36:34

well i still have a few more ideas i wanna try .. including making it efficient above 100008 ...

tip: comment the line 46: #print "%i: %i" % (p,n) then add ... print "%i: %i" % (p,i) to the bottom of the file .... this generates the 100008th prime in 11 seconds .. because the print state also needs time to output to the screen ...

i tried q = int(l ** 0.5 * 4) .. it's slower, because then the check uses unnecessary values ...
i dunno if i misunderstood u but, (z <> 5 and z % 2 <> 0 ) eliminates multiples of 2 and five ... so the if ( on[len(on)-1] <= q ): on.append(n) then becomes necessary .. i did this because when it gets to large numbers, it's faster to eliminate some then check the rest, if that makes any sense .. basically, it's slower to check 100000 % 2; than it is to take the last char. '0' and 0 % 2 ....

i have some ideas to make it faster, one of which is .. to check the length of the latest prime, if it's in the rage 10000 for example we change q ... this will make it a lot faster, i assume, since we'd be using the optimal value of q for their respective range.. rather than wastng 10+ seconds generating 10000 primes when it could take 0m1.892s

once again it would make it a little slower at small numbers .. but once they get larger u'd prolly notice it not slowing much

-------------------------------------------------------------------------------------------------------

time /port/bin/primen.r3.1.py 100008
100008: 1299829

real    0m14.143s
user    0m13.139s
sys     0m0.069s
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
time /port/bin/findprimeplace.py 100008
1299827

real    0m33.911s
user    0m31.921s
sys     0m0.147s

time /port/bin/primen.r3.1.py 10000
10000: 104731

real    0m0.632s
user    0m0.580s
sys     0m0.010s
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 time /port/bin/findprimeplace.py 10000
104729

real    0m1.048s
user    0m0.973s
sys     0m0.007s

 time /port/bin/primen.r3.1.py 1000
1001: 7921 #fault of how the loop is done... will fix in r4

real    0m0.057s
user    0m0.045s
sys     0m0.008s
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 time /port/bin/findprimeplace.py 1000
7919

real    0m0.065s
user    0m0.048s
sys     0m0.006s

revision 3.1 is just the method of not printing every number, but rather the one requested...

[/code]

T-Dawg · 2007-01-05 17:08:58

noriko,
I've run both your scripts and they don't seem to be outputting the corrent prime numbers. Run it against the number 113 and compare it to wikipedia: http://en.wikipedia.org/wiki/Prime_number

Here is my attempt at it:

$time python prime.py 100008
....
....
total: 9593

real    0m25.204s
user    0m22.542s
sys     0m0.052s

#!/usr/bin/python

#
# generates a list of primes from a given range.
# written by Tyler Gates
#

import os, sys

start = 2
odd_nums = [1, 3, 5, 7, 9]
even_nums = [0, 2, 4, 6, 8]
base_primes = [2, 3, 5, 7]
odd_primes = [3, 5, 7]
even_primes = [2]

def last_digit(num):
    str_num = str(num)
    return int(str_num[len(str_num)-1])

def eval_num(num):
    last_d = last_digit(num)
    if last_d in odd_nums:
        global odd_primes
        for prime in odd_primes:
            if num%prime == 0.0:
                return 0
        odd_primes.append(num)
        return 1
    else:
        global even_primes
        for prime in even_primes:
            if num%prime == 0.0:
                return 0
        even_primes.append(num)
        return 1

if __name__ == '__main__':
    numbers = int(sys.argv[1])
    ct = start
    m = 0
    if numbers >= 10:
        for n in base_primes:
            print n
            m += 1
    elif numbers <= 10:
        ct2 = 0
        while ct2 <= numbers:
            if ct2 in base_primes:
                print ct2
                m += 1
            ct2 += 1
        print 'ntotal:' +str(m)
        sys.exit(0)
    
    while ct <= numbers:
        if eval_num(ct) == 1:
            print ct
            m += 1
        ct += 1
    print 'ntotal: ' + str(m)
    sys.exit(0)

T-Dawg · 2007-01-05 18:52:08

oh yeah, cut it in half:

$time python prime.py 100008
....
.... 
total: 9593

real    0m16.020s
user    0m10.504s
sys     0m0.042s
total: 9593

#!/usr/bin/python

#
# generates a list of primes from a given range.
# written by Tyler Gates
#

import os, sys

start = 2
odd_nums = [1, 3, 5, 7, 9]
even_nums = [0, 2, 4, 6, 8]
base_primes = [2, 3, 5, 7]
odd_primes = [3, 5, 7]
even_primes = [2]

first_even = even_primes[0]
first_odd = odd_primes[0]

def last_digit(num):
    str_num = str(num)
    return int(str_num[len(str_num)-1])

def eval_num(num):
    last_d = last_digit(num)
    if last_d in odd_nums:
        global odd_primes
        h = num/first_odd
        for prime in odd_primes:
            if prime > h: 
                odd_primes.append(num)
                return 1
            if num%prime == 0.0:
                return 0
        odd_primes.append(num)
        return 1
    else:
        global even_primes
        h = num/first_even
        for prime in even_primes:
            if prime > h: 
                even_primes.append(num)
                return 1
            if num%prime == 0.0:
                return 0
        even_primes.append(num)
        return 1

if __name__ == '__main__':
    numbers = int(sys.argv[1])
    ct = start
    m = 0

    if numbers <= 10:
        ct2 = 0
        while ct2 <= numbers:
            if ct2 in base_primes:
                print ct2
                m += 1
            ct2 += 1
        print 'ntotal:' +str(m)
        sys.exit(0)
    
    while ct <= numbers:
        if eval_num(ct) == 1:
            print ct
            m += 1
        ct += 1
    print 'ntotal: ' + str(m)
    sys.exit(0)

noriko · 2007-01-06 00:16:53

yeh .. it's a bug, i will try to fix it in r4, it basically fails on n`th prime smaller than about 200

i seem to have forgotten to correct the primen description.. it generates the n`th prime, not primes less than n ... so a correct comparison with ur script would be ...

time /port/bin/t-dawg.prime.py 100008
...
100003

total: 9593

real    0m39.259s
user    0m27.674s
sys     0m0.242s

time /port/bin/primen.r3.2.py 9593
...
9593: 100003

real    0m2.139s
user    0m1.005s
sys     0m0.079s

or

time /port/bin/primen.r3.2.py 9593 only
9593: 100003

real    0m0.845s
user    0m0.819s
sys     0m0.002s

#########################
changelog or primen.r3.2

fixed an issue with outputting the wrong prime (not the value, just the wrong one.. i.e p.3.1. 1000, outputted 10001th prime )

added extra param, 'only' it can be any value btw ... so primen.r3.2.py 100008 only, will output only the 100008th prime(1,299,827) as opposed to printing the hole list...

small speedup, by using a pre-generated list of bad values.. (0,2,4,5,6,8) instead of filtering against z` not 5 and z` % 2 == 0 (thx t-dawg ...)

so the new results are ...

time /port/bin/primen.r3.2.py 100008
...
100008: 1299827

real    0m23.749s
user    0m14.766s
sys     0m0.662s

yay three seconds faster.....

#######################add#=###############

@t-dawg ... ur script gets cripled on large numbers...
if i attempt to generate the first 100008 primes (up to 1299827)

time /port/bin/t-dawg.prime.py 1299827
...
343531
Traceback (most recent call last):
  File "/port/bin/t-dawg.prime.py", line 57, in ?
    if eval_num(ct) == 1:
  File "/port/bin/t-dawg.prime.py", line 26, in eval_num
    if num%prime == 0.0:
KeyboardInterrupt

real    4m56.832s
user    4m6.376s
sys     0m1.784s

beejayzed · 2007-01-06 00:31:20

noriko wrote:

i tried q = int(l ** 0.5 * 4) .. it's slower, because then the check uses unnecessary values ...
i dunno if i misunderstood u but, (z <> 5 and z % 2 <> 0 ) eliminates multiples of 2 and five ... so the if ( on[len(on)-1] <= q ): on.append(n) then becomes necessary .. i did this because when it gets to large numbers, it's faster to eliminate some then check the rest, if that makes any sense .. basically, it's slower to check 100000 % 2; than it is to take the last char. '0' and 0 % 2 ....

As an example, 100000.
The square root of the result, 1299709 is 1140.
With q as 0.079, the results check up to 7900.
With q as ** 0.5 * 4, the results check up to 1264.
So the prime list would be smaller.

For the second one, maybe the number filtering before checking operation is slower than just checking on a celeron? I'll post some of my tests.

This is with q = int(l * 0.079) and no number filtering before checking.
$ primen.py 100000
1299708
real    1m37.621s

These are all with q = int(l ** 0.5 * 4)

Number filtering:
$ primen.py 100000 
1299708
real    0m25.773s

Plain list checking (with the start list as 2,5,3,7):
$ primen.py 100000
1299708
real    0m20.671s

Tests with 10000 show the plain checking 0.3s faster.

I think, as you said, adjusting q as the required number increases would help, but what kind of overhead would the checking operation have?

T-Dawg · 2007-01-06 00:43:44

Ahh.. I see, I thought you were trying to do it the other way around. Well I'm glad at least you found some of my code useful..a whole 3 seconds faster. Yay! 8)

noriko · 2007-01-06 01:10:22

for the second point, yeh i think i get it now .. i will have to do some tests..

on the first ... u seem to have misread the code ... or the wrong rev.
i work only on the last ... http://lmu.j2k.cc >> r3.2
for me, on an athlon, a RISC processor, i get the 100008th in 23 seconds ... it will be different for u on a CISC processor.. but i dunno how much different ...

these are the correct number checks...
py
...

>>> 1000 ** 0.5 * 4
126.49110640673517
>>> 10000 ** 0.5 * 4
400.0
>>> 100000 ** 0.5 * 4
1264.9110640673518
>>> 
>>> 
>>> 
>>> 1000 * 0.079
79.0
>>> 10000 * 0.032
320.0
>>> 100000 * 0.012
1200.0

edit:
@t-dawg .. well it all counts hehe .. and i'm sure i'd never have thought about that bit lol ..

beejayzed · 2007-01-06 01:25:31

noriko wrote:

for the second point, yeh i think i get it now .. i will have to do some tests..
on the first ... u seem to have misread the code ... or the wrong rev.
i work only on the last ... http://lmu.j2k.cc >> r3.2
for me, on an athlon, a RISC processor, i get the 100008th in 23 seconds ... it will be different for u on a CISC processor.. but i dunno how much different ...
these are the correct number checks...
py
...
>>> 1000 ** 0.5 * 4
126.49110640673517
>>> 10000 ** 0.5 * 4
400.0
>>> 100000 ** 0.5 * 4
1264.9110640673518
>>> 
>>> 
>>> 
>>> 1000 * 0.079
79.0
>>> 10000 * 0.032
320.0
>>> 100000 * 0.012
1200.0
edit:
@t-dawg .. well it all counts hehe .. and i'm sure i'd never have thought about that bit lol ..

Ah yes I was using the version where q is always l * 0.079.

noriko · 2007-01-06 20:01:08

@beejayzed ... ur method of 2,5* is about the same speed on my athlon.. RISC, often slightly slower than the existing method .. however, now i see hte speed increase u reported on a celeron 2*Ghz .. i foudn it quite fscinating, i didn't know cisc and risc could vary s much in soem operations .. anyway, to benefit all procs.. afaik, i decided to use ur method .. all the python version of the algorithm is http://lmu.j2k.cc/primen.py/ ; r3.4 (possibly the last version bfore i fix te bug to get it to r4); uses this technique ...

i considerred it as fast as python was gonan take it so i switched to c++ .. i also implemented it in c, but the speed was about the same . and i find c++ nicer so i stuck with c++ ..
http://lmu.j2k.cc/primen+ | code (messy) and binary(i686: -O3)
here are some results

.....
~~~~~~~~
PrimeN+ r3.4
~~~~~~~~
.....
time primen+ 1000
...
1000: 7919

real    0m0.082s
user    0m0.004s
sys     0m0.009s
~~~~~~~~~~~~~~~~~~~~~
time primen+ 1000 only
...
1000: 7919

real    0m0.004s
user    0m0.002s
sys     0m0.002s

time primen+ 1000000 only
~~~~~~~~~~~~
PrimeN+ r3.4
~~~~~~~~~~~~
1000000: 15485863

real    0m45.990s
user    0m41.869s
sys     0m0.169s

changelog::r3.4::
added support for printing only 1 number .. to do this add a second command lien argument..'only',(btw it can be any value)

fixed issue with printing too many numbers...

now implemented in c++ and is a lot faster than python version..

Arch Linux

#1 2007-01-01 02:01:37

For those who need a programming challenge

#2 2007-01-01 17:18:31

Re: For those who need a programming challenge

#3 2007-01-01 18:25:20

Re: For those who need a programming challenge

#4 2007-01-03 14:54:43

Re: For those who need a programming challenge

#5 2007-01-03 15:16:50

Re: For those who need a programming challenge

#6 2007-01-03 16:05:31

Re: For those who need a programming challenge

#7 2007-01-03 16:16:11

Re: For those who need a programming challenge

#8 2007-01-03 16:33:56

Re: For those who need a programming challenge

#9 2007-01-03 19:38:11

Re: For those who need a programming challenge

#10 2007-01-05 00:35:47

Re: For those who need a programming challenge

#11 2007-01-05 00:56:01

Re: For those who need a programming challenge

#12 2007-01-05 09:52:35

Re: For those who need a programming challenge

#13 2007-01-05 10:49:47

Re: For those who need a programming challenge

#14 2007-01-05 11:13:20

Re: For those who need a programming challenge

#15 2007-01-05 11:45:23

Re: For those who need a programming challenge

#16 2007-01-05 12:13:00

Re: For those who need a programming challenge

#17 2007-01-05 12:36:34

Re: For those who need a programming challenge

#18 2007-01-05 17:08:58

Re: For those who need a programming challenge

#19 2007-01-05 18:52:08

Re: For those who need a programming challenge

#20 2007-01-06 00:16:53

Re: For those who need a programming challenge

#21 2007-01-06 00:31:20

Re: For those who need a programming challenge

#22 2007-01-06 00:43:44

Re: For those who need a programming challenge

#23 2007-01-06 01:10:22

Re: For those who need a programming challenge

#24 2007-01-06 01:25:31

Re: For those who need a programming challenge

#25 2007-01-06 20:01:08

Re: For those who need a programming challenge

Board footer