View mode: basic / threaded / horizontal-split · Log in · Help
May 16, 2012
Re: ProjectEuler problem 35
============
The number, 197, is called a circular prime because all rotations 
of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 
31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?
===========



On Wednesday, 16 May 2012 at 14:17:21 UTC, Andrea Fontana wrote:
> Probabily i miss the point. Are you looking for prime & 
> circular primes or for circular primes only?
>
> On Wednesday, 16 May 2012 at 14:14:15 UTC, Tiberiu Gal wrote:
>> "You'll skip 70% of checks..."
>> that's true for the Circular check ... but in the whole app, 
>> the most time is spent finding primes.
>>
May 16, 2012
Re: ProjectEuler problem 35
On 05/16/2012 07:14 AM, Tiberiu Gal wrote:
> "You'll skip 70% of checks..."
> that's true for the Circular check ... but in the whole app, the most
> time is spent finding primes.

A number that cannot be circular prime need not be checked whether 
regular prime.

Ali

-- 
D Programming Language Tutorial: http://ddili.org/ders/d.en/index.html
May 16, 2012
Re: ProjectEuler problem 35
On Wednesday, 16 May 2012 at 13:10:06 UTC, Tiberiu Gal wrote:
> The correct answer is 55
> Your versions of isCircularPrime just truncates the number ( 
> this is actually useful in a next problem though; )

 Hmm glancing at the original source I see what you mean. A 
slight modification to fill primes with bools primes beforehand 
and a slight re-write of the circular check code would do the 
trick.

 And after doing so I still end up with about the same speed, 
course the second run I was doing a foreach on bool[] primes, and 
not on prime_walk, but you get the idea... Unless you really need 
to see it I won't repost my changes here.


On Wednesday, 16 May 2012 at 14:14:15 UTC, Tiberiu Gal wrote:
>On Wednesday, 16 May 2012 at 14:01:19 UTC, Andrea Fontana wrote:
>> Not that big gain?
>
>> If you check for circulars numbers from 0 to 1.000.000 you can 
>> skip intervals from 200.000 to 299.999, from 400.000 to 
>> 699.999 and from 800.000 to 899.999 (and other sub-intervals, 
>> of course).
>
>> You'll skip 70% of checks...

 I went ahead and tried that.. It varied the execution speed, 
giving a slight speedup or a slight slowdown, but the checks are 
almost not worth it. In the circular check 99% of them fail on 
the first rotation. Guess it ends up as "which is cheaper?". 10 
compares? or 1 divide and 1 multiply and 1 lookup?

>
> that's true for the Circular check ... but in the whole app, 
> the most time is spent finding primes.

 Which is why I simplified the whole code in my example. 
prime_walk always returns the next prime, and using the primes 
array, we instantly know if the number checked is prime. Large 
portions of the code are rather wasteful in the original example, 
like checking for a prime and then a circular prime.

 Skipping the understanding of prime_walk, using the levels (for 
the most significant digit) should be fairly self explanatory, 
plus it is MUCH faster than convert to string and then convert 
back again.
May 16, 2012
Re: ProjectEuler problem 35
Original code in this thread run on my pc in ~400ms.
With my skipping method it takes just ~10ms.

But I think there're more improvement.

However using CTFE I guess time goes down to 0 ;)

On Wednesday, 16 May 2012 at 19:50:45 UTC, Era Scarecrow wrote:
>  On Wednesday, 16 May 2012 at 13:10:06 UTC, Tiberiu Gal wrote:
>> The correct answer is 55
>> Your versions of isCircularPrime just truncates the number ( 
>> this is actually useful in a next problem though; )
>
>  Hmm glancing at the original source I see what you mean. A 
> slight modification to fill primes with bools primes beforehand 
> and a slight re-write of the circular check code would do the 
> trick.
>
>  And after doing so I still end up with about the same speed, 
> course the second run I was doing a foreach on bool[] primes, 
> and not on prime_walk, but you get the idea... Unless you 
> really need to see it I won't repost my changes here.
>
>
> On Wednesday, 16 May 2012 at 14:14:15 UTC, Tiberiu Gal wrote:
>>On Wednesday, 16 May 2012 at 14:01:19 UTC, Andrea Fontana wrote:
>>> Not that big gain?
>>
>>> If you check for circulars numbers from 0 to 1.000.000 you 
>>> can skip intervals from 200.000 to 299.999, from 400.000 to 
>>> 699.999 and from 800.000 to 899.999 (and other sub-intervals, 
>>> of course).
>>
>>> You'll skip 70% of checks...
>
>  I went ahead and tried that.. It varied the execution speed, 
> giving a slight speedup or a slight slowdown, but the checks 
> are almost not worth it. In the circular check 99% of them fail 
> on the first rotation. Guess it ends up as "which is cheaper?". 
> 10 compares? or 1 divide and 1 multiply and 1 lookup?
>
>>
>> that's true for the Circular check ... but in the whole app, 
>> the most time is spent finding primes.
>
>  Which is why I simplified the whole code in my example. 
> prime_walk always returns the next prime, and using the primes 
> array, we instantly know if the number checked is prime. Large 
> portions of the code are rather wasteful in the original 
> example, like checking for a prime and then a circular prime.
>
>  Skipping the understanding of prime_walk, using the levels 
> (for the most significant digit) should be fairly self 
> explanatory, plus it is MUCH faster than convert to string and 
> then convert back again.
May 19, 2012
Re: ProjectEuler problem 35
On 16/05/2012 10:46, Dmitry Olshansky wrote:
<snip>
> Don't ever do that. I mean allocating memory in tight cycle.
> Instead use circular buffer. (just use the same array and wrap indexes)
<snip>

You might as well not use a string representation at all.  At the beginning of the loop, 
calculate the number of digits in n, then pow10 = 10 ^^ (digits - 1).  Then cycle with

    n = n / 10 + (n % 10) * pow10;

Stewart.
May 19, 2012
Re: ProjectEuler problem 35
A huge optimization could be made by storing and int array of already
found primes and test all primes smaller then half the to-test number.
this will speed up a lot.
Another huge improvement could be made with hardcoding everything up
to the prime 3 and then iterate with intervals of 2 instead of 1.
May 19, 2012
Re: ProjectEuler problem 35
On Wednesday, 16 May 2012 at 09:26:45 UTC, Tiberiu Gal wrote:
> hi
>
> many claim their code solves the problem in order of ms ( 
> c/pascal/haskell code)
>
>

I used the blockwise parallel sieve described here, and measured 
nice speed-ups as described in his blog.  It completes 
calculations within an L1 cache block before moving on.  Perhaps 
you can redesign you code to do the same...

http://create.stephan-brumme.com/eratosthenes/
May 19, 2012
Re: ProjectEuler problem 35
On Saturday, 19 May 2012 at 16:43:03 UTC, Jay Norwood wrote:
> On Wednesday, 16 May 2012 at 09:26:45 UTC, Tiberiu Gal wrote:
>> hi
>>
>> many claim their code solves the problem in order of ms ( 
>> c/pascal/haskell code)
>>
>
> I used the blockwise parallel sieve described here, and 
> measured nice speed-ups as described in his blog.  It completes 
> calculations within an L1 cache block before moving on.  
> Perhaps you can redesign you code to do the same...
>
> http://create.stephan-brumme.com/eratosthenes/

 Curiously I've done most of these (Although not exactly as 
written). The blockwise makes sense; I've seen a prime checker JS 
somewhere that uses those exact primes and if a number wasn't 
divisible by them it was 'probably prime'.

 All of this is good material to glance over and review though :)
May 20, 2012
Re: ProjectEuler problem 35
On 19/05/2012 16:13, maarten van damme wrote:
> A huge optimization could be made by storing and int array of already
> found primes and test all primes smaller then half the to-test number.
> this will speed up a lot.

Do you mean build an array of already-found primes and use them to test new primes?  You 
need only to try dividing by each prime up to the square root of the number being tested.

> Another huge improvement could be made with hardcoding everything up
> to the prime 3 and then iterate with intervals of 2 instead of 1.

Yes, that's a common optimisation.  Faster still would be to test 6k-1 and 6k+1 for each 
positive integer k.  Indeed, I've done more than this in my time: hard-coded all the 
primes up to 30 and the residues modulo 30 that can possibly be of primes above 30.

Stewart.
May 21, 2012
Re: ProjectEuler problem 35
On Sunday, 20 May 2012 at 15:48:31 UTC, Stewart Gordon wrote:
> On 19/05/2012 16:13, maarten van damme wrote:
> Yes, that's a common optimisation.  Faster still would be to 
> test 6k-1 and 6k+1 for each positive integer k.  Indeed, I've 
> done more than this in my time: hard-coded all the primes up to 
> 30 and the residues modulo 30 that can possibly be of primes 
> above 30.
>
> Stewart.

This person has done a number of optimizations.  He gets some 
speed-up by storing in bits rather than bytes.  It is also 
designed for segments that fir in the L1 cache.

http://code.google.com/p/primesieve/
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home