Talk:Sieve of Sundaram

From Wikipedia, the free encyclopedia

This article is within the scope of the following WikiProjects:

WikiProject India (Rated Stub-Class) This article is within the scope of WikiProject India, which aims to improve Wikipedia's coverage of India-related topics. If you would like to participate, please visit the project page. Stub This article has been rated as Stub-Class on the quality scale. (add comments) More information about this article... Mid This article has been rated as Mid-importance on the importance scale by the India project. WikiProject Mathematics     (Rated Stub-Class) Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics. Mathematics rating: Stub Class Mid Priority  Field: Number theory Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

[edit] Comments

This article has a number of problems. I have left the following note on the original author's talk page:

I see that you recently created a new article, Sieve of Sundaram. I think the article needs a bit more work. Problems with the current version are:

1. The Sundaram that you link to is a volleyball player. Is he really the inventor of the algorithm ?
2. The date "in 40th of XX century" needs to be completed and clarified.
3. The description of the algorithm is not clear. What does "Derived sequence consist of primary numbers p" mean ?
4. The article needs to include references to show that (i) the algorithm is not original research and (ii) the algorithm is notable.

Unless you (or someone else) can fix these problems in the article, it will fall short of Wikipedia's standards, and may be deleted. Gandalf61 11:14, 3 December 2007 (UTC)

Thanks for response Basicall article just translated from rusiian Wikipedia.

1. Changed. I don't really know who Sundaram is, half an houre googling don't help me to figure out it.
2. Date is all I got for now, I have not any paper sources so it's all I got.
3. will try to clarify, with this rough description I've made up a programm.
4. Algorithm just one of this type, it faster than Eratosphenes & easier than Atkins sieves, notably enough IMO. I'll try to figuire out sources/referencies and add them.

I'll appreciate any suggestions about improoving it more Any_Key 19:35, 3 December 2007 (UTC)

I don't think that this is any faster than the Sieve of Eratosthenes, though, I think just about anything is easier to understand than Atkin's. I did some simple tests in C and Haskell, my C version of this ran about 75% as fast as the unoptimized SOE. The haskell version ran half as fast, though I think my implementation of the latter is probably lacking.

A informal analysis tells me that this algorithm runs in linear time, since you have to generate a list of Z values, then generate a list of values that are no Z values, then map over that list the 2x + 1 function. I think that SOE runs in O(n), Atkin in O(n/log log n). So, it is my impression that this is no better than the SOE, except for possibly conciseness. Even in that regard, SOE is smaller than Sundaram in Haskell (at least in my implemenation) by about 25 characters (not including whitespace). Jfredett (talk) 09:12, 17 December 2007 (UTC)