Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.javascript > #21215 > unrolled thread
| Started by | jonas.thornvall@gmail.com |
|---|---|
| First post | 2013-09-08 19:09 -0700 |
| Last post | 2014-05-02 15:54 -0700 |
| Articles | 9 on this page of 49 — 6 participants |
Back to article view | Back to comp.lang.javascript
Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 19:09 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 05:57 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 21:22 -0700
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 21:50 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 13:45 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 06:33 -0700
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 06:41 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 18:37 +0200
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 19:54 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 12:46 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 23:25 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 14:58 -0700
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-11 10:39 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-11 02:54 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-11 12:59 +0200
Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-12 20:17 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 02:27 +0200
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-13 04:03 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-12 19:30 -0700
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 05:15 +0200
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-13 05:27 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 08:26 -0700
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 08:15 -0700
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 19:13 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 17:15 -0700
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 01:55 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 04:20 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 06:16 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 12:10 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 12:49 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 15:23 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 21:51 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-15 03:32 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 04:07 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-15 18:57 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 19:24 +0100
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-14 20:37 -0700
Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-14 19:38 +0100
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 22:26 -0700
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-10 22:48 +0100
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-11 00:36 -0700
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-11 14:47 +0100
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 22:33 -0700
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2013-09-09 21:08 -0700
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2013-09-10 08:52 -0700
Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-10 19:08 +0100
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-04-10 22:02 -0700
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-05-02 15:39 -0700
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-05-02 15:54 -0700
Page 3 of 3 — ← Prev page 1 2 [3]
| From | jonas.thornvall@gmail.com |
|---|---|
| Date | 2013-09-11 00:36 -0700 |
| Message-ID | <c8df65e0-e61f-4df8-a02f-96ad2f9dfbfd@googlegroups.com> |
| In reply to | #21255 |
Den tisdagen den 10:e september 2013 kl. 23:48:34 UTC+2 skrev Ben Bacarisse:
> jonas.thornvall@gmail.com writes:
>
>
>
> <snip>
>
> > So what is wrong with this code?
>
>
>
> It looks over-complex, and it's not a fast as the plain sieve, so I
>
> don't see the point of the complexity. Maybe it kicks in for much
>
> larger primes sets.
>
>
>
> <snip>
>
> > function sieve(max) {
>
> > var D = [], primes = [];
>
> > for (var q=2; q<max; q++) {
>
> > if (D[q]) {
>
> > for (var i=0; i<D[q].length; i++) {
>
> > var p = D[q][i];
>
> > if (D[p+q]) D[p+q].push(p);
>
> > else D[p+q]=[p];
>
> > }
>
> > delete D[q];
>
> > } else {
>
> > primes.push(q);
>
> > if (q*q<max) D[q*q]=[q];
>
> > }
>
> > }
>
> > return primes;
>
> > }
>
> <snip>
>
>
>
> The plain sieve of Eratosthenes goes like this:
>
>
>
> function sieve(max) {
>
> var comp = [], primes = [], cur_prime = 2;
>
> while (cur_prime < max) {
>
> primes.push(cur_prime);
>
> for (var mult = 2 * cur_prime; mult < max; mult += cur_prime)
>
> comp[mult] = true;
>
> while (comp[++cur_prime]);
>
> }
>
> return primes;
>
> }
>
>
>
> On my machine, this runs five times faster for primes up to 20,000,000.
>
>
>
> --
>
> Ben.
Hello Ben nice implementation, i do not know if i remember wrong but is this a new twist on Eratosthenes only storing the truth values? yours indeed was much faster then strawman, and i found an even faster implementation of Eratosthenes.
But i will try to match your speeds by setting just the index like you seem todo, i found your implementation a bit hard to understand could you explain?
Here is the timings from my computer yours, mine and Eratosthenes like i remembered it but it only uses index.
Barcaisse Timing=10779
Thörnvall Timing=29738
Ereastohenes Timing=6348
Code below.
<!DOCTYPE html>
<html>
<head></head>
<script type="text/javascript">
var MAX = 30000000;
function Eratosthenes()
{
// Eratosthenes algorithm to find all primes under n
var array = [], upperLimit = Math.sqrt(n), output = [];
// Make an array from 2 to (n - 1)
for (var i = 0; i < n; i ++ )
{
array.push(true);
}
// Remove multiples of primes starting from 2, 3, 5, ...
for (var i = 2; i <= upperLimit; i ++ )
{
if (array[i])
{
for (var j = i * i; j < n; j += i)
{
array[j] = false;
}
}
}
for (var i = 2; i < n; i ++ )
{
if(array[i])
{
output.push(i);
}
}
outE = output.toString();
}
function benB()
{
var comp = [], primes = [], cur_prime = 2;
while (cur_prime < MAX)
{
primes.push(cur_prime);
for (var mult = 2 * cur_prime; mult < MAX;
mult += cur_prime)
comp[mult] = true;
while (comp[ ++ cur_prime]);
}
outB = primes.toString();
return outB;
}
function jonasT()
{
var primes = [2];
n = 3;
while(n < MAX)
{
p = true;
k = 0;
test = Math.sqrt(n) + 1;
test = Math.round(test);
while (test >= primes[k])
{
if ((n % primes[k]) == 0)
{
p = false;
break;
document.write("break");
}
k ++ ;
}
if (p == true)
{
t = primes.length;
primes[t] = n;
}
n ++ ;
}
outJ = primes.toString();
return outJ;
}
var start = new Date().getTime();
benB();
var end = new Date().getTime();
var time = end - start;
outB=outB.substring(0,100);
document.write("Barcaisse=", outB, "<BR> Timing=", time, "<BR>");
var start = new Date().getTime();
jonasT();
var end = new Date().getTime();
var time = end - start;
outJ=outJ.substring(0,100);
document.write("<BR>Thörnvall=", outJ, "<BR> Timing=", time, "<BR>");
var start = new Date().getTime();
Eratosthenes(MAX);
var end = new Date().getTime();
var time = end - start;
outE=outE.substring(0,100);
document.write("<BR>Ereastohenes=",outE,"<BR> Timing=", time, "<BR>");
</script>
<body>
</body>
</html>
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2013-09-11 14:47 +0100 |
| Message-ID | <0.f56f47af16523795dd40.20130911144711BST.87fvtb31y8.fsf@bsb.me.uk> |
| In reply to | #21259 |
jonas.thornvall@gmail.com writes:
> Den tisdagen den 10:e september 2013 kl. 23:48:34 UTC+2 skrev Ben Bacarisse:
>> jonas.thornvall@gmail.com writes:
>>
>>
>>
>> <snip>
>>
>> > So what is wrong with this code?
>>
>>
>>
>> It looks over-complex, and it's not a fast as the plain sieve, so I
>>
>> don't see the point of the complexity. Maybe it kicks in for much
>>
>> larger primes sets.
>>
>>
>>
>> <snip>
>>
>> > function sieve(max) {
>>
>> > var D = [], primes = [];
>>
>> > for (var q=2; q<max; q++) {
>>
>> > if (D[q]) {
>>
>> > for (var i=0; i<D[q].length; i++) {
>>
>> > var p = D[q][i];
>>
>> > if (D[p+q]) D[p+q].push(p);
>>
>> > else D[p+q]=[p];
>>
>> > }
>>
>> > delete D[q];
>>
>> > } else {
>>
>> > primes.push(q);
>>
>> > if (q*q<max) D[q*q]=[q];
>>
>> > }
>>
>> > }
>>
>> > return primes;
>>
>> > }
>>
>> <snip>
>>
>>
>>
>> The plain sieve of Eratosthenes goes like this:
>>
>>
>>
>> function sieve(max) {
>>
>> var comp = [], primes = [], cur_prime = 2;
>>
>> while (cur_prime < max) {
>>
>> primes.push(cur_prime);
>>
>> for (var mult = 2 * cur_prime; mult < max; mult += cur_prime)
>>
>> comp[mult] = true;
>>
>> while (comp[++cur_prime]);
>>
>> }
>>
>> return primes;
>>
>> }
>>
>>
>>
>> On my machine, this runs five times faster for primes up to 20,000,000.
>>
>>
>>
>> --
>>
>> Ben.
>
> Hello Ben nice implementation, i do not know if i remember wrong but
> is this a new twist on Eratosthenes only storing the truth values?
No, it's just a bit faster to use the fact that an unset array element
will test false. This is you reverse the sense of the array, you don't
have to set the elements first. Do that to the sieve function you found
and it's yet more efficient.
> yours indeed was much faster then strawman, and i found an even faster
> implementation of Eratosthenes.
Yes, that one stops trying to sieve sooner and it starts the sieving at
the square of the current prime, rather than my naive double. A similar
modification to mine would looks like this:
function sieve(max) {
var comp = [], primes = [], cur_prime = 2;
var upperLimit = Math.sqrt(max);
while (cur_prime < upperLimit) {
primes.push(cur_prime);
for (var mult = cur_prime * cur_prime; mult < max; mult += cur_prime)
comp[mult] = true;
while (comp[++cur_prime]);
}
for (; cur_prime < max; cur_prime++)
if (!comp[cur_prime])
primes.push(cur_prime);
return primes;
}
> But i will try to match your speeds by setting just the index like you
> seem todo, i found your implementation a bit hard to understand could
> you explain?
Just (a) remove the loop that sets 'array' initially, (b) set array[j]
to true rather than false, and (c) flip the two tests from array[i] to
!array[i]. The result is faster still (on my machine).
<snip>
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | jonas.thornvall@gmail.com |
|---|---|
| Date | 2013-09-08 22:33 -0700 |
| Message-ID | <5837258c-4fbe-4c8d-a432-b7e8e5b59495@googlegroups.com> |
| In reply to | #21217 |
Den måndagen den 9:e september 2013 kl. 05:57:27 UTC+2 skrev Stefan Weiss:
> On 2013-09-09 04:09, jonas.thornvall@gmail.com wrote:
>
> > It writes all 1 270608 primes less then 20 000 004 into an array in
>
> > 17 seconds by comparing the natural with the value read into the array, but
>
> > bigger then 20 million there is to many primes to compare with and it
>
> > gets slow. I only compare the values in prime array upto square of the
>
> > natural.
>
>
>
> I didn't look very closely, but from what I can see, you're not using
>
> the sieve at all, you're just doing dumb trial division.
>
>
>
> Read this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
>
>
>
> Algorithms aside, is there a point to what you're doing, or is it just
>
> recreational? No disrespect, I also like mathematical puzzles and tasks,
>
> but if you actually need the prime numbers for something, you could just
>
> download them.
>
>
>
> - stefan
I am waiting for you to post a faster sieve of the primes upto 20 millions.
It is extrordinary that what you call trial division is faster the Eratosthenes.
Maybe i got hold of a bad implementation?
<!DOCTYPE html>
<html>
<head></head>
<script type="text/javascript">
function sieve(max) {
var D = [], primes = [];
for (var q=2; q<max; q++) {
if (D[q]) {
for (var i=0; i<D[q].length; i++) {
var p = D[q][i];
if (D[p+q]) D[p+q].push(p);
else D[p+q]=[p];
}
delete D[q];
} else {
primes.push(q);
if (q*q<max) D[q*q]=[q];
}
}
return primes;
}
var start = new Date().getTime();
sieve(20000000)
var end = new Date().getTime();
var time = end - start;
alert('Execution time: ' + time);
</script>
<body>
</body>
</html>
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <no@spam.invalid> |
|---|---|
| Date | 2013-09-09 21:08 -0700 |
| Message-ID | <l0m5vq$j4m$1@speranza.aioe.org> |
| In reply to | #21222 |
> wrote in message
> news:5837258c-4fbe-4c8d-a432-b7e8e5b59495@googlegroups.com...
> Den måndagen den 9:e september 2013 kl. 05:57:27 UTC+2 skrev Stefan Weiss:
> > On 2013-09-09 04:09, jonas.thornvall@gmail.com wrote:
> >
> > > It writes all 1 270608 primes less then 20 000 004 into an array in
> >
> > > 17 seconds by comparing the natural with the value read into the
> > > array, but
> >
> > > bigger then 20 million there is to many primes to compare with and it
> >
> > > gets slow. I only compare the values in prime array upto square of the
> >
> > > natural.
[...]
> I am waiting for you to post a faster sieve of the primes upto 20
> millions.
> It is extrordinary that what you call trial division is faster the
> Eratosthenes.
[...]
FWIW, here is stupid simple code that finds 1,270,607 prime numbers out of
20,000,000 with average time of 12,500 milliseconds on my little notebook
using Firefox:
______________________________________________________________
<!DOCTYPE html>
<html>
<title>Primes</title>
<script type="text/javascript">
function is_prime(n)
{
if (isNaN(n) || ! isFinite(n) || n % 1 || n < 2)
return false;
if (! (n % 2)) return (n == 2);
if (! (n % 3)) return (n == 3);
var m = Math.sqrt(n);
for (var i = 5; i <= m; i += 6)
{
if (! (n % i) || ! (n % (i + 2)))
return false;
}
return true;
}
function count_prime(m)
{
var c = 0;
for (var n = 2; n < m; ++n)
if (is_prime(n)) ++c;
return c;
}
function main()
{
console.time("count_prime");
var c = count_prime(20000000);
console.timeEnd("count_prime");
alert("Found " + c + " Primes.");
}
</script>
<body onload="main();">
</body>
</html>
______________________________________________________________
I have no idea if this is anywhere near what you are looking for Jonas...
;^o
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <no@spam.invalid> |
|---|---|
| Date | 2013-09-10 08:52 -0700 |
| Message-ID | <l0nf7q$6sp$1@speranza.aioe.org> |
| In reply to | #21245 |
"Chris M. Thomasson" wrote in message
news:l0m5vq$j4m$1@speranza.aioe.org...
[...]
> FWIW, here is stupid simple code that finds 1,270,607 prime numbers out of
> 20,000,000 with average time of 12,500 milliseconds on my little notebook
> using Firefox:
> ______________________________________________________________
> [...]
> function count_prime(m)
> {
> var c = 0;
>
> for (var n = 2; n < m; ++n)
> if (is_prime(n)) ++c;
>
> return c;
> }
> [...]
> ______________________________________________________________
This tiny "optimization" of the function above shaves off a couple seconds
of runtime:
______________________________________________________________
function count_prime(m)
{
var c = 0;
for (var n = 2; n < m; ++n)
{
if (is_prime(n)) ++c;
if (n > 2) ++n;
}
return c;
}
______________________________________________________________
Might as well skip all of the even numbers greater than two...
;^)
Since no even numbers other than two will ever be passed to the `is_prime()'
function, you can remove one of mod operations. Actually, I don't know why
I used the mod in the first place when, in this case, bitwise AND will do
the
trick!
[toc] | [prev] | [next] | [standalone]
| From | Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> |
|---|---|
| Date | 2013-09-10 19:08 +0100 |
| Message-ID | <ypQ6Ba6eA2LSFwOn@invalid.uk.co.demon.merlyn.invalid> |
| In reply to | #21215 |
In comp.lang.javascript message <6e464d33-47e4-41b8-bfda-19511de92915@go oglegroups.com>, Sun, 8 Sep 2013 19:09:51, jonas.thornvall@gmail.com posted: >It writes all 1 270608 primes less then 20 000 004 into an array in 17 seconds by comparing the natural with the value read into the array, but >bigger then 20 million there is to many primes to compare with and it gets slow. I only compare the values in prime array upto square of the >natural. > ... (1) That 17 seconds is not very meaningful as you have not said what your browser is, what your OS is, or what your CPU is. (2) Have you checked your list of primes against a known-good list? (3) In Chrome 29, WinXP sp3, P4/3G, I find 1270608 primes in under 4.6 seconds, using straight Eratosthenes as previously cited. -- (c) John Stockton, near London. Mail ?.?.Stockton@physics.org Web <http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, and links.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <no@spam.invalid> |
|---|---|
| Date | 2014-04-10 22:02 -0700 |
| Message-ID | <li7t26$lgr$1@speranza.aioe.org> |
| In reply to | #21215 |
Hey Jonas, you might be interested in: https://plus.google.com/104956987891789686401/posts/fwkWtaQKYgY ?
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <no@spam.invalid> |
|---|---|
| Date | 2014-05-02 15:39 -0700 |
| Message-ID | <lk16rt$ur$1@speranza.aioe.org> |
| In reply to | #23845 |
> "Chris M. Thomasson" wrote in message > news:li7t26$lgr$1@speranza.aioe.org... Hey Jonas, you might be interested > in: > https://plus.google.com/104956987891789686401/posts/fwkWtaQKYgY FWIW, check the out as well: http://webpages.charter.net/appcore/prime/prime_map_p0.bmp (around a 2.86 mb 1000x1000 bmp) Each intersection between the red and blue lines are colored white and represent a point where both x and y are prime. x and y are unsigned integers. Lattice points are where the x and y coordinates are prime.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <no@spam.invalid> |
|---|---|
| Date | 2014-05-02 15:54 -0700 |
| Message-ID | <lk17o4$2ns$1@speranza.aioe.org> |
| In reply to | #24012 |
> "Chris M. Thomasson" wrote in message > news:lk16rt$ur$1@speranza.aioe.org... > > "Chris M. Thomasson" wrote in message > > news:li7t26$lgr$1@speranza.aioe.org... Hey Jonas, you might be > > interested in: > > https://plus.google.com/104956987891789686401/posts/fwkWtaQKYgY > FWIW, check the out as well: > http://webpages.charter.net/appcore/prime/prime_map_p0.bmp > (around a 2.86 mb 1000x1000 bmp) > Each intersection between the red and blue > lines are colored white and represent a point > where both x and y are prime. > x and y are unsigned integers. Lattice points > are where the x and y coordinates are prime. I wonder what would happen if I planted DLA seeds on the lattice points of the graph!? Humm... I bet it would be pretty! :^) Example of DLA planted in a spiral... https://plus.google.com/101799841244447089430/posts/Pmm7Qsh9W2t
[toc] | [prev] | [standalone]
Page 3 of 3 — ← Prev page 1 2 [3]
Back to top | Article view | comp.lang.javascript
csiph-web