(tye)Re: (Golf): Sieve of Eratosthenes

[tye]

in reply to (Golf): Sieve of Eratosthenes

Though I somehow doubt this is a winner, I think it might qualify for the "bonus marks". You'll note that no division (or modulus) is used, so I consider it to be using the sieve with no special cases or wasted operations (though it probably has plenty of wasted comparisons O-:). Though it might be more efficient to break out of the grep when a non-prime is found (or, if we had things in a sorted order, to stop once $_*$_ passes $n) and compensate for that by incrementing $p{$_} in an extra loop (rather than incrementing it, at most, one time per prime candidate), but I'm not even sure if that would be a net win (without resorting to sorting).

sub sieve {
my%p=(2,2);for my$n(3..pop){grep$n==($p{$_}+=$_*($p{$_}<$n)),keys%p
or$p{$n}=$n}keys%p
}

for( @ARGV ) {
    print "$_: ",join(" ",sort{$a<=>$b}sieve($_)),$/;
}

I count 86 characters for the part that counts. And, no, I don't think it'd be fair to add 13 characters for sorting since the original challange didn't say anything about returning the list in sorted order. q-:

Sample output:

1: 2
2: 2
3: 2 3
4: 2 3
5: 2 3 5
6: 2 3 5
50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
1000: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79
83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269
271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373
379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467
479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593
599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691
701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821
823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937
941 947 953 967 971 977 983 991 997

Update: BTW, this is strict compliant.

        - tye (but my friends call me "Tye")

[tye]

BTW, the above was based on solving the Sieve using functional programming techniques and then analysing what the computer ends up doing when that code is run and then reimplementing that in a procedural style. I find that technique often gives you interesting insights.

Anyway, I tried to reverse engineer what tilly's solution was from his description and came up with this:

sub sieve2 {
    grep{@_[map$a*$_,2..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop;
}

for( @ARGV ) {
    print "$_: ",join(" ",sieve2($_)),$/;
}

which is 54 characters. It is strict compliant "to the letter" but not "in spirit". But it is even more Sieve-like than my previous one (I just don't like algorithms where you give an upper bound and once you get there you have to start over if you want to go further).
        - tye (but my friends call me "Tye")

[MeowChow]

53 characters:

sub sieve2 {
    grep{@_[map$a*$_,2..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop
}

All your t-shirts are belong to me! j/k :-)

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print

[tye]

tilly's comment about things being "nearly linear" threw me for a bit. Then I realized that the quadratic nature is countered by the outer loop only needing to run to sqrt(N) and the inner loop being somewhat similarly restricted.

Which made me realize that my solution was suboptimal. Here is a faster one at the same number of characters [ thanks to MeowChow noting that I'd stupidly left in a trailing semicolon in my previous one ;) ]:

sub sieve3 {
    grep{@_[map$a*$_,$_..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop
} #                  ^^

for( @ARGV ) {
    print "$_: ",join(" ",sieve3($_)),$/;
}

In playing with this and verifying that I didn't break it, I noticed something interesting and expanded on it. For how long of a stretch can you go without hitting any prime numbers? Well, stopping at 0.5million (because of memory limits), here are the results. "xN" means there were N ties before a new "winner" appeared:

2=5-3(x2)    # 3..5, 5..7
4=11-7(x3)   # 7..11, 13..17, 19..23
6=29-23(x7)
8=97-89
14=127-113(x3)
18=541-523
20=907-887
22=1151-1129
34=1361-1327(x2)
36=9587-9551(x3)
44=15727-15683
52=19661-19609(x2)
72=31469-31397
86=156007-155921(x2)
96=360749-360653
112=370373-370261
114=492227-492113

        - tye (but my friends call me "Tye")

[tilly]

In the Big-O analysis being able to stop the outer loop early turns out to be a red herring. Being able to stop the inner loop after 1/p operations is key, as is the density of the primes. It means that the work is O(n*(sum of 1/p)). The sum of 1/i scales like log(n), the density of the primes scales as 1/log(n), and between them they cancel out for O(n*log(log(n))).

log(log(n)) is essentially constant in the range of numbers I can test before hitting memory limitations. Also there is a theoretical log(n) that we are missing from the overhead of addressing and representing ever larger numbers. While we tend to call that constant, in reality it is not.

BTW if you are interested, longer tables of maximal gaps have been compiled...

[tilly]

And almost a decade later I was randomly looking at this, and realized that it could be made shorter still.

sub sieve3 {
    grep{@_[map$a*$_,2..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop
}

Never give up on that last optimization!