mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2010-04-10, 15:59   #56
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,343 Posts
Default

Quote:
Originally Posted by alexhiggins732 View Post
So being the crank I am, I did what any self-respecting crank would do, I rewrote it in VB.NET...
That's a pretty ambitious spur-of-the-moment undertaking. I have no idea if its possible (I don't know much VB.NET so I won't be of any use in helping you with your port).

As you've seen, pointers are used abundantly and I employ all sorts of C hacks like casting void pointers and adding pointer values. Not sure if equivalent code is possible in VB.

It may have been easier to package the existing C code as a .dll library for use in a VB program.
bsquared is offline   Reply With Quote
Old 2010-04-10, 16:25   #57
alexhiggins732
 
Mar 2010
Brick, NJ

67 Posts
Default

Quote:
Originally Posted by bsquared View Post
That's a pretty ambitious spur-of-the-moment undertaking. I have no idea if its possible (I don't know much VB.NET so I won't be of any use in helping you with your port).

As you've seen, pointers are used abundantly and I employ all sorts of C hacks like casting void pointers and adding pointer values. Not sure if equivalent code is possible in VB.

It may have been easier to package the existing C code as a .dll library for use in a VB program.
Yeah tell me about it. That is nothing like my "sliding window" sieve or even the seo. In fact Atkins and Euler have sieve named after them and and made only simple modifications.

YOUR SIEVE IS A BEAST I NOMINATE THE NAME THE SIEVE OF BUHROW


COM Interop on windows is quite a drag on performance. I current use a LIBGMP wrapper and just for i=0 to 100000000 takes several minutes.

Actually comparing c/c++/vb performance is quite comparable when dealing with 32 bit words. 16 and 64 may be slightly slower and perhaps the bounds checking performed under the hood would be another performance hit, but nothing compared to the cost of com calls.

Hopefully someone with VS will take a look and give it a shot. I can upload and entire project file. It would simply be a matter of stepping though each program. I mean their almost exact line for line.

FYI, tiny_soe works perfect but then again that is a pretty simple implementation. spSOE fails, first reporting 121 as prime.
alexhiggins732 is offline   Reply With Quote
Old 2010-04-10, 17:19   #58
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by alexhiggins732 View Post
Yeah tell me about it. That is nothing like my "sliding window" sieve or even the seo. In fact Atkins and Euler have sieve named after them and and made only simple modifications.
You think the Sieve of Atkin is a simple modification?
CRGreathouse is offline   Reply With Quote
Old 2010-04-10, 18:34   #59
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,343 Posts
Default

Quote:
Originally Posted by alexhiggins732 View Post
Yeah tell me about it. That is nothing like my "sliding window" sieve or even the seo. In fact Atkins and Euler have sieve named after them and and made only simple modifications.

YOUR SIEVE IS A BEAST I NOMINATE THE NAME THE SIEVE OF BUHROW
I'm flattered , but at the end of the day its just another sieve of Eratosthenes. The best that can be said about it is that it uses some optimizations that perhaps haven't been implemented before. Even so, in all but very special cases it isn't even the fastest SOE... ecprime fills those shoes.
bsquared is offline   Reply With Quote
Old 2010-04-10, 19:43   #60
alexhiggins732
 
Mar 2010
Brick, NJ

67 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
You think the Sieve of Atkin is a simple modification?
While it may be entirely more effecient for larger input and the theory behind it can be quite complex, it is indeed a relatively simple modification compared to the one implement in Yafu.

Compare this mutli-threaded sieve to the code in the previous thread
Code:
Private Shared Sub ParralleSieve(x as Integer)
 
        Dim xx = x * x
        For y As Integer = 1 To sqrt
            Dim yy = y * y
            Dim n = 4 * xx + yy
            If n <= max AndAlso (n Mod 12 = 1 OrElse n Mod 12 = 5)  Then
                isPrime(n) = Not isPrime(n)
            End If
            
            n = 3 * xx + yy
            If n <= max AndAlso n Mod 12 = 7 Then
                isPrime(n) = Not isPrime(n)
            End If
            
            n = 3 * xx - yy
            If x > y AndAlso n <= max AndAlso n Mod 12 = 11 Then
                isPrime(n) = Not isPrime(n)
            End If
        Next

End Sub
Private Shared Function SieveOfAtkins(ByVal max As Integer) As List(Of Integer)
    Dim isPrime = New BitArray(CInt(max) + 1, False)
    Dim sqrt = CInt(Math.Sqrt(max))
    
    Parallel.[For](1, sqrt, AddressOf ParrallelSieve)
    
    Dim primes = New List(Of Integer)()
    For n As Integer = 5 To sqrt
        If isPrime(n) Then
            primes.Add(n)
            Dim nn As Integer = n * n
            Dim k As Integer = nn
            While k <= max
                isPrime(k) = False
                k += nn
            End While
        End If
    Next
    
    For n As Integer = sqrt + 1 To max
        If isPrime(n) Then
            primes.Add(n)
        End If
    Next
    
    Return primes
End Function

Last fiddled with by alexhiggins732 on 2010-04-10 at 19:44 Reason: add code block
alexhiggins732 is offline   Reply With Quote
Old 2010-04-10, 20:19   #61
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by alexhiggins732 View Post
While it may be entirely more effecient for larger input and the theory behind it can be quite complex, it is indeed a relatively simple modification compared to the one implement in Yafu.
Quote:
Originally Posted by alexhiggins732 View Post
Compare this mutli-threaded sieve to the code in the previous thread
Code:
Private Shared Sub ParralleSieve(x as Integer)
 
        Dim xx = x * x
        For y As Integer = 1 To sqrt
            Dim yy = y * y
            Dim n = 4 * xx + yy
            If n <= max AndAlso (n Mod 12 = 1 OrElse n Mod 12 = 5)  Then
                isPrime(n) = Not isPrime(n)
            End If
            
            n = 3 * xx + yy
            If n <= max AndAlso n Mod 12 = 7 Then
                isPrime(n) = Not isPrime(n)
            End If
            
            n = 3 * xx - yy
            If x > y AndAlso n <= max AndAlso n Mod 12 = 11 Then
                isPrime(n) = Not isPrime(n)
            End If
        Next

End Sub
Private Shared Function SieveOfAtkins(ByVal max As Integer) As List(Of Integer)
    Dim isPrime = New BitArray(CInt(max) + 1, False)
    Dim sqrt = CInt(Math.Sqrt(max))
    
    Parallel.[For](1, sqrt, AddressOf ParrallelSieve)
    
    Dim primes = New List(Of Integer)()
    For n As Integer = 5 To sqrt
        If isPrime(n) Then
            primes.Add(n)
            Dim nn As Integer = n * n
            Dim k As Integer = nn
            While k <= max
                isPrime(k) = False
                k += nn
            End While
        End If
    Next
    
    For n As Integer = sqrt + 1 To max
        If isPrime(n) Then
            primes.Add(n)
        End If
    Next
    
    Return primes
End Function
As far as I can tell, this is wrong. But even if it works (I can't get it to give correct answers), it's not more than a pale reflection of the sieve. This takes at least n(\log n)^{1+\varepsilon} time, while the 'true' Sieve of Atkin takes only O(n/\log\log n) time. Similarly, yours takes about n bits of memory, while the real one takes n^{0.5+\varepsilon} bits.

The second is not difficult, but the first one takes real magic. By omitting that part you do a great disservice to the inventors of the sieve, Bernstein and Atkin.

But if you think that implementation tricks are what make the algorithm, then you should see Bernstein's implementation.

Also: the name is Atkin, not Atkins.
CRGreathouse is offline   Reply With Quote
Old 2010-04-10, 21:07   #62
alexhiggins732
 
Mar 2010
Brick, NJ

4316 Posts
Default

I concur, it is indeed a great sieve indeed and there are many implementations of it out there. For those interested here is the theory behind it and other sieves.

http://cr.yp.to/papers/primesieves.pdf
alexhiggins732 is offline   Reply With Quote
Old 2010-04-10, 21:38   #63
flouran
 
flouran's Avatar
 
Dec 2008

83010 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Also: the name is Atkin, not Atkins.
I guess Atkin is often mistaken for the diet
flouran is offline   Reply With Quote
Old 2010-04-12, 00:55   #64
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,343 Posts
Default

I've now completed the sum of each sequence (primes, prime squares, and prime cubes) up to 1e14, and found the 12th member of the cube sequence:

Code:
**** 1000000000000 divides prime cube sum up to 33777547344991, sum is 10532010356822624092227361649102207021134000000000000 ****
bsquared is offline   Reply With Quote
Old 2010-04-12, 15:02   #65
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default

Quote:
Originally Posted by flouran View Post
I guess Atkin is often mistaken for the diet
Well, the diet is a sieve, screening out certain types of calories, isn't it?
cheesehead is offline   Reply With Quote
Old 2010-04-12, 16:38   #66
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

I thought a calory was 4.2 Joule, but nutritionists use
the term to refer to a kilocalory.

I don't think there are different types for different foods.
Even the "type of energy" it measures is the same for
everything.

David
davieddy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Regarding Squares a1call Miscellaneous Math 42 2017-02-03 01:29
Basic Number Theory 12: sums of two squares Nick Number Theory Discussion Group 0 2016-12-11 11:30
Integers = sums of 2s and 3s. 3.14159 Miscellaneous Math 12 2010-07-21 11:47
Sums of three squares CRGreathouse Math 6 2009-11-06 19:20
squares or not squares m_f_h Puzzles 45 2007-06-15 17:46

All times are UTC. The time now is 09:01.

Mon Nov 30 09:01:40 UTC 2020 up 81 days, 6:12, 3 users, load averages: 1.77, 1.14, 1.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.