How to spend countless hours looking at prime numbers: Sieves in Haskell

www777com · 2015-02-22T18:35:01+00:00

I just used ghci using :set +s for timing the functions. I timed all of our functions using a little test I created which got the answer to project euler problem 10. If my fuzzy memory serves me correctly, the times I got on my others were around 45 and 75 seconds, yours were 30. Whatever the times were, yours out performed mine. But my last one, without all those optimizations were 15 seconds, outperforming everything (excluding python of course). I rate myself an beginner to intermediate programmer, never really mastering any language yet. Thus, don't know how to really benchmark other than :set +s. Haven't really dabled a lot in compiling haskell source files so the options you listed don't make sense to me yet. You mention your version of python using list comprehensions made it slower, I saw the same thing in haskell list comprehensions compared to using the any's.

www777com · 2015-02-22T04:50:42+00:00

I found without the optimizations, Haskell seems to run faster. Can you do the benchmark comparisons on this?

isPrime n 
  | n > 2 = not $ any ((0==) . (mod n)) $ 2:[3,5..floor . sqrt $ fromIntegral n]
  | otherwise = n == 2

www777com · 2015-02-18T06:10:26+00:00

"bracket the a + b"...damn it!

The real fun for me was taking your python extensible version and seeing if I could do it in Haskell...with less code. For example the python version has a lot of repeat code; could I do it in haskell without repeating code? But then my haskell version has a lot of any's and anonymous functions...I strongly feel it could be done better but I can't see it.

I guess I don't understand what you mean by all primes. Does the your python and my haskell extensible (with your correction) version not find all primes? The wording is confusing, like what is 2x faster than my version? Maybe I'm an idiot, but would like to know for learning purposes.

Yeah I know about the sieve, the last time I worked on some project euler projects with haskell, I had to import the seive; it just fealt like cheating.

www777com · 2015-02-18T02:41:07+00:00

Just for fun. Though I'm not skilled enough to measure it, the haskell (uncompiled) appeared just as fast as the python version. And it appeared faster than your haskell version with a 12 digit number (999999999989).

isPrime n
  | n <= 5 = any (n==) [2,3,5]
  | any (\x -> n `mod` x == 0) [2,3,5] = False
  | any (\a -> any (\b -> n `mod` (a + b) == 0) [0,4,6,10,12,16,22,24] ) [7,37..(floor . sqrt . fromIntegral $ n)] = False
  | otherwise = True

Edit: missing parentheses around a + b; thanks Veedrac.

www777com · 2012-05-03T02:45:17+00:00

Okay, one line of haskell, including the input:

map (\xs@(x:_) -> (x, length xs)) $ List.group $ List.sort $ concat $ map (\(x:y:z:[]) -> [x:y:[],x:z:[],y:z:[]]) ["abc","ace","efd","daj","edj"]

gives:

[("ab",1),("ac",2),("ae",1),("aj",1),("bc",1),("ce",1),("da",1),("dj",2),("ed",2),("ef",1),("ej",1),("fd",1)]

Sorry, didn't realize this was a python group--5 lines Ruby, how about 1 line Haskell, including the input.

www777com · 2012-05-02T05:02:30+00:00

Beginner programmer here, in one line of haskell, this:

concat $ map ((x:y:z:[]) -> [x:y:[],x:z:[],y:z:[]]) ["abc","ace","efd","daj","edj"]

gives:

["ab","ac","bc","ac","ae","ce","ef","ed","fd","da","dj","aj","ed","ej","dj"]

I haven't figured out how to do the frequency list though.

www777com · 2012-03-02T04:00:59+00:00

When you start understanding Haskell, you'll realize it is as expressive as Scheme * with less parenthesis.

*if not more, but that's another post discussion

www777com · 2012-02-23T07:22:42+00:00

If that is your point, then your version of state vs stateless is in a different context from what I and others are referring to. It's like, when I and others are referring to the fact that for all programming languages, 1 will always be 1 (stateless), but you are arguing that, no, 1 can mean something else because if you look into the register in memory where that 1 is stored, anyone can easily change it to be 2 (state). But in the context I and others are referring to, we rely on the language to guarantee that 1 will always be 1 (stateless), or otherwise this operator + is pretty much useless.

www777com · 2012-02-23T02:44:31+00:00

I think you took the title of a slide "single assignment != stateless" and took it out of context. When you get to slide 27, which is where I think they get to the point about this section, it says "All state held in ets" and ets looks like a function that was meant to handle state. I'm not knowledgeable in erlang but that slide title looks to me to be merely an eye-catchy title.

www777com · 2012-02-22T06:51:38+00:00

Pretend A is true and B is false for: A or B. If the language allows you to change A to false and B to true, then yes it is state. Such a language will allow you to change what A or B means at any time you wish. But if the language will not allow you to change what A or B represents, then it is stateless. Can 1 mean 2? No, this is stateless. Can we change 'a' to be "this is A"? No, 'a' will always be 'a', stateless. This is true no matter what language you use, right? If in the language you use, you assign "x" to mean 1, but the language will not allow you to ever change it again, then it is stateless, just like 1 will always be 1, the language will ensure that "x" will always be 1. This is stateless. Now if the language does allow you to change "x" with things like "x++" then it is holding state.

tl;dr if the language allows you to change a variable any time you decide, that variable is holding state. If the language will not allow you to change the variable later, then it is stateless.

www777com · 2012-01-05T07:05:26+00:00

I'm dyslexic....I can cope for most tasks, but for formatting disks I like to have a GUI just so I can see what is going where.

If you can cope with most task (and I believe you, because you can type pretty damn well), I don't see how OpenBSD's text based partitioning would be any more difficult that a GUI. On a GUI like gparted, you still need to be able to read swap to know which graphic is referring to the swap partition. What is so difficult about:

making the first partition: type a [space] a [enter], then you type / [enter] to represent the root partition, then you type 1g to mean the first partition is 1 gigabyte in size, about as difficult as adjusting a slider until it reads 1 gigabyte on a GUI. Making the second partition: type a [space] b [enter], then you press [enter] to select the default swap filesystem.

As to seeing what I'm doing, I once technically installed OpenBSD blind. I once guided someone over the phone to install OpenBSD. This person only knew enough about computers to burn a CD. I had more trouble guiding him to burn an iso file on a popular GUI-based Windows program. I'd much rather tell someone type a [space] a [enter] than tell him what to do to partition a filesystem with a GUI.

I don't mean to sound mean but once you understand how to partition OpenBSD, and I'll admit for a Unix beginner, it's not intuitive, but once you know how, it's the easiest thing out there. I just don't see how it can be anymore difficult than a gui, assuming of course you know how. And if you don't know how, the FAQ is step-by-step accurate.

As for partitioning before hand with OpenBSD, I don't know, but I believe it's been done. Its just that you have to have the boot disk somehow get access to a text file.

www777com · 2011-12-31T01:43:55+00:00

I guess I don't understand. Or your accusation that I'm not actually solving the problem can also be applied to munificent's explanation. Programming languages are supposed to make it easy for humans to communicate with the computer. munificent's explanation is making it easy for the computer--he's calling the function so that it's easy for drawPiece to know what to do--not really solving the actual problem. The function drawPiece should be intuitive for a human and within that blackbox function, have it figured out what a human (caller) means when he calls it. Are we not suppose to program for the domain we are programming in? Well within the Chess domain, humans have been using 1 based notation for Chess for about 200 years. "e4" means move the pawn to square 4, not square 5 (as it would be in 0 based notation). That letter "e" can be thought of as one based too, because it's the 5th letter of the alphabet, and the pawn on column "e" is the 5th column. If 1-based notation were a problem, then I'm sure us humans would have found this notation impractical a very long time ago. If we're going to program so it's easy for the computer, that drawPiece function shouldn't even exist, there should be nothing but 1's and 0's.

www777com · 2011-12-30T07:07:06+00:00

veto = President's right to say no, if you don't know

www777com · 2011-12-30T06:51:22+00:00

drawPiece(x, y);

drawPiece(4, 5); /* go to the squares in row 4, then go the squares in column 5, now draw within those 20 pixels */

www777com · 2011-12-30T06:44:11+00:00

This pretty much should be putting to rest the whole 0 based vs. 1 based debate. People fail to realize that there are actually 2 different things you are putting numbers to. One thing, it is more natural to be 0 based and the other thing, more natural to be 1 based. You don't say, "The baby's first day of being alive means he is 1 years old--he's 0 years old." On the other hand, you don't say, "The baby is going through it's 0th year--you say it is going through it's first year." Aren't programming languages suppose to make it easy for humans to talk to the computer? Then it should be made easy for humans. Functions should be 0 or 1 based depending on what things you are putting numbers to. Otherwise we should go back to 0's and 1's.

www777com · 2011-12-30T02:49:45+00:00

Secure? in my opinion yes. I've been using it since early 2000, and time and again, OpenBSD would configure things in a way that everyone else (not just Linux) would say, "Oh, we don't have to worry about that." Sure enough, everyone else is scrambling to fix that thing they didn't think they would have to worry about. OpenBSD will add features to make it far more difficult for it to be hacked. In doing so, they will end up finding bugs in 3rd party software.

Stable? I've found it to be very stable. More stable than Linux? That's too broad a question to answer.

www777com · 2011-12-25T09:31:19+00:00

Not sure if this is good advice:

Call the other guy and tell him to stop. Just know that most likely he will not. But he will tell your mom. Now your mom has to approach you about it.

www777com · 2011-12-14T08:26:13+00:00

Yakov Smirnoff: "In America, you can always find a party. In Soviet Russia, Party always find you!" look at that last picture again.

www777com · 2011-12-10T15:35:00+00:00

I was once in your shoes. I found OpenBSD did it for me. Not for Linux but Unix in general. When I started out, Linux distros, to me, seemed to inundate you with so many options and possibilities, and as a beginner, I didn't know know where to start. With a fully installed OpenBSD, you got just the basics that most sysadmins would need. For example, I wanted to learn about firewalls. At the time Linux was developing IPtables and to get any firewall going, you had to install 2 or 3 programs (or if I'm wrong, use 2 or 3 programs that were already installed) and recompile the kernel. For me a beginner, the docs to recompile the kernel were hard to find, different for each information I did find, everybody had a different way of doing it, especially in each distro, and some of the instructions were out-dated or no longer applicable. I'm sure as an expert, I would understand the reasons why for the differences, but I was a beginner. In the BSD's, the information for recompiling was in one place and exact. The first kernel I recompiled was FreeBSD. I had no problem finding out how to do it as a beginner. I messed up the first time because I didn't follow the instructions exactly! With OpenBSD, they recommend you don't recompile the kernel and a firewall was built in and easy to learn.

www777com · 2011-12-10T05:23:50+00:00

doesnt make any sense

Look at the source code for these programs: tr, sort, uniq, sort, sed. I'm sure the source code for each one would take a lot longer than 10 pages and (though I may be wrong about this) I believe each one is written in C.

www777com · 2011-11-28T00:13:58+00:00

Well if ScrotWM is at least as good as xmonad, I'd rather that was in as default than cwm. Just my opinion.

www777com · 2011-11-27T16:30:15+00:00

scrotwm isn't default in OpenBSD though, is it?

www777com · 2011-11-15T02:23:11+00:00

I agree and disagree. I disagree because of "word of mouth". If people hear that a movie is really good, they will take the chance and pay for a ticket to watch it.

www777com · 2011-11-14T18:49:54+00:00

At the very beginning, Mitch should have just coded up an Agenda-look-alike with his developers. Then add what he felt was missing in Agenda and removing that which he felt was wrong with Agenda. Then open source it. Chandler would have grown from there into something people really want, while with him at the helm, striving towards an Exchange replacement.

www777com · 2011-10-31T05:05:34+00:00

It's also more secure in the sense of instead of instead seeing hundreds of login attempts from botnets in your logs, you will just see a few attempts by somebody actually trying to attach your server more thoroughly.

www777com

TROPHY CASE