| --- Log opened Wed Dec 12 00:00:36 2007 |
| 00:02 | <@ilovefire> | I'm... still confused ab it. |
| 00:03 | <@ToxicFrog> | In what way? |
| 00:04 | <@ilovefire> | mostly by how to code it--I KNOW what I want to do. |
| 00:05 | <@ToxicFrog> | Well. Consider the concept of is_prime(k): for each number n between 2 and k-1, checks to see if k is evenly divisible by n. |
| 00:06 | <@ToxicFrog> | If so, k is not prime. |
| 00:06 | <@ToxicFrog> | If it checks all these numbers without ever finding such an n, k is prime. |
| 00:06 | <@ToxicFrog> | Sensical? |
| 00:06 | | * ilovefire nods. |
| 00:06 | | You're now known as TheWatcher[T-2] |
| 00:06 | <@ToxicFrog> | So. How do you do the 'for each number n between 2 and k-1'? |
| 00:07 | <@ToxicFrog> | And how do you check to see if k is evenly divisible by n? |
| 00:07 | <@ToxicFrog> | You know both of these, and one you them you've already used today :P |
| 00:07 | <@ilovefire> | the first is xrange, the second is *goes to check his notes* the thing with the % symbol between two things? |
| 00:08 | <@ToxicFrog> | Yes. Remember, % (modulus) is informally the remainder operator. |
| 00:08 | <@ToxicFrog> | Ie, a % b is the remainder when a is divided by b. |
| 00:08 | <@ilovefire> | oh right. |
| 00:08 | <@ToxicFrog> | And if they're evenly divisble, the remainder is 0. |
| 00:08 | <@ToxicFrog> | So, try putting these together. |
| 00:10 | | You're now known as TheWatcher[zZzZ] |
| 00:16 | <@ilovefire> | Okay, I've got it where it's no longer giving me an error message, but now it just isn't working. |
| 00:16 | <@ilovefire> | http://rafb.net/p/slMikw86.html |
| 00:17 | <@ToxicFrog> | Ok, you have two problems here. |
| 00:17 | <@ilovefire> | Allright. |
| 00:17 | <@ToxicFrog> | First of all, think about the behavior of xrange. |
| 00:18 | | * ilovefire nods... |
| 00:18 | <@ToxicFrog> | xrange(a,b) gives you the numbers from a to b-1 inclusive. |
| 00:18 | <@ilovefire> | oh, right. Needs to just be n, okay |
| 00:18 | <@ToxicFrog> | Secondly, think about the circumstances under which you are returning true. |
| 00:18 | <@ToxicFrog> | is_prime is meant to return true if the number is prime, right? |
| 00:18 | <@ilovefire> | yes. |
| 00:19 | <@ilovefire> | ... d'oh. |
| 00:19 | | * ilovefire mutters, just can't seem to think of a good way to phrase it. |
| 00:19 | <@ToxicFrog> | ...er. And two other problems. |
| 00:19 | <@ToxicFrog> | What's evenly divisible by 1? |
| 00:20 | <@ilovefire> | one. |
| 00:20 | <@ToxicFrog> | ...and? |
| 00:20 | <@ilovefire> | zero? |
| 00:20 | <@ToxicFrog> | ......and? |
| 00:20 | <@ToxicFrog> | Think. What's 2/1? |
| 00:21 | <@ilovefire> | ... one. |
| 00:21 | <@ToxicFrog> | ...you're saying that 1 goes into 2, 1 time. |
| 00:21 | <@ilovefire> | wait. |
| 00:21 | | * ilovefire head-desk. |
| 00:21 | <@ToxicFrog> | That 2 divided into 1 piece is, in fact, 1. |
| 00:21 | <@ilovefire> | err, two into one is, umm, two? |
| 00:22 | <@ToxicFrog> | 2 into 1 is 1/2, which is one half. |
| 00:22 | <@ToxicFrog> | 1 into 2 is 2/1, which is 2. |
| 00:22 | <@ilovefire> | Oh. |
| 00:22 | | * ilovefire head-desk again. |
| 00:22 | <@ToxicFrog> | 2/1, 2 divided by 1, can be expressed as "2 divided into 1 piece" or as "the number of times that 1 goes into 2" |
| 00:23 | <@ToxicFrog> | So. What's evenly divisible by 1? |
| 00:24 | <@ilovefire> | Everything? |
| 00:24 | <@ToxicFrog> | Right. |
| 00:24 | <@ToxicFrog> | This is why primes are allowed to be divisible by 1. |
| 00:25 | <@ToxicFrog> | So, when testing what something is divisible by, what should the lower bound of your range be? |
| 00:25 | <@ilovefire> | 2. |
| 00:25 | <@ilovefire> | and then n for the uppermost range? |
| 00:25 | <@ToxicFrog> | Aah yes, about that. |
| 00:25 | <@ToxicFrog> | You are using n here, but k elsewhere. |
| 00:25 | <@ToxicFrog> | That is to say, you call is_prime(k) |
| 00:25 | <@ToxicFrog> | But inside is_prime, you call it n, |
| 00:25 | <@ToxicFrog> | This is legal, but confusing. |
| 00:26 | | * ilovefire saw, changed it around. |
| 00:26 | <@ToxicFrog> | Especially since you then turn around and use k to be the number you're testing it against! |
| 00:26 | | * ilovefire nods... |
| 00:27 | <@ToxicFrog> | Changed it as in the caller now uses n, or is_prime now uses k? |
| 00:27 | <@ToxicFrog> | I need to know so I can talk about this without being confusing. |
| 00:28 | <@ilovefire> | http://rafb.net/p/mwcfTr35.html it looks like this now |
| 00:29 | <@ToxicFrog> | Where's the rest of it? |
| 00:29 | <@ToxicFrog> | Remember, is_prime is only half the program. |
| 00:29 | <@ToxicFrog> | primes is what actually makes use of it. |
| 00:30 | <@ilovefire> | I know, I haven't made the other half yet. |
| 00:30 | <@ToxicFrog> | ... |
| 00:31 | <@ToxicFrog> | http://rafb.net/p/Wvvvi829.html <-- what's this thing you pasted earlier, then? |
| 00:31 | <@ilovefire> | that would be, well, the beginnings of it suppose. |
| 00:31 | <@ToxicFrog> | Replace "k is prime" with "is_prime(k)" and that's it. |
| 00:33 | <@ToxicFrog> | And this is what I mean by confusing names. |
| 00:33 | <@ToxicFrog> | Inside primes(), you use k to mean the number you're testing for primality. |
| 00:33 | <@ToxicFrog> | Inside is_prime(), you use n to mean the number you're testing for primality. |
| 00:33 | <@ilovefire> | ah. |
| 00:33 | <@ToxicFrog> | And then you turn around and re-use k for something totally different. |
| 00:33 | <@ToxicFrog> | This is legal, but it's bad form. |
| 00:34 | | * ilovefire nods, thinks it makes sense now, goes to test it... |
| 00:37 | <@ilovefire> | and, umm, nothing. |
| 00:38 | <@ToxicFrog> | Show the code? |
| 00:39 | <@ilovefire> | http://rafb.net/p/Q0IZIG30.html I probably made a glaringly obvious mistake. |
| 00:39 | <@ToxicFrog> | A few, of varying degrees of obviousness. |
| 00:40 | <@ToxicFrog> | First of all, true and false in python are True and False - case sensitive. |
| 00:40 | <@ilovefire> | Okay. |
| 00:40 | <@ToxicFrog> | Second - you're checking to see if k is evenly divisible by n, right? |
| 00:40 | | * ilovefire thought he was told all of python's keywords were lower case, but maybe it was 'most'. And yes, I think. |
| 00:40 | <@ToxicFrog> | So how do you write that, using %? |
| 00:40 | <@ilovefire> | ... k % n? |
| 00:41 | <@ToxicFrog> | That's "the remainder when k is divided by n", you're still missing something... |
| 00:42 | <@ilovefire> | == 0? |
| 00:42 | <@ToxicFrog> | Right. |
| 00:42 | <@ToxicFrog> | Now look at your if statement again. |
| 00:42 | <@ilovefire> | That's in the program, though... |
| 00:44 | <@ToxicFrog> | Not quite. |
| 00:44 | <@ToxicFrog> | How does line 3 differ from what you just said? |
| 00:44 | <@ilovefire> | well, it has n % k (or had, I just changed it) ==0: |
| 00:45 | <@ToxicFrog> | Changed it to k % n, I hope. |
| 00:45 | <@ToxicFrog> | That was the problem; / isn't commutative, and neither is %. |
| 00:45 | <@ToxicFrog> | So. One more issue. |
| 00:46 | <@ilovefire> | Okay. |
| 00:46 | <@ToxicFrog> | What's the contract of is_prime? That is to say, how is it meant to behave, without saying anything about how it actually works inside? |
| 00:47 | <@ilovefire> | It's meant to check if a number if prime by seeing if it's divisible by anyone number between 2 and x-1, inclusive. |
| 00:47 | <@ToxicFrog> | That's the purpose it fufills, but in what way does it do this? |
| 00:47 | <@ToxicFrog> | Does it output a message? Set a global variable? Return a value? |
| 00:48 | <@ilovefire> | it returns if the statement is true? |
| 00:49 | <@ToxicFrog> | Returns what? |
| 00:49 | <@ToxicFrog> | What you're looking for is "is_prime(k) returns True if k is prime, and False otherwise" |
| 00:49 | | * ilovefire nods... |
| 00:49 | <@ToxicFrog> | Now, look at your actual code. Under what circumstances will it return True? |
| 00:50 | <@ilovefire> | if n divides evenly into k, which isn't what I want... I want it to return False in that event, then? |
| 00:50 | <@ToxicFrog> | Bingo. |
| 00:51 | <@ToxicFrog> | If it's evenly divisible, that means it's not prime. |
| 00:51 | <@ilovefire> | allright, that seems to be fixed now. Anything else? |
| 00:51 | <@ToxicFrog> | And that just leaves how to get it to return True in the case that it is. |
| 00:51 | <@ToxicFrog> | Since as it stands, it'll return False if the number isn't prime, and nothing if it is. |
| 00:52 | | * ilovefire nods... |
| 00:52 | <@ToxicFrog> | So. How do you tell that you've run out of numbers to test it against, and thus know that it's prime? |
| 00:53 | <@ilovefire> | Umm... well, umm... |
| 00:56 | <@ilovefire> | have something that, if this returns false, returns true to primes? |
| 00:56 | <@ToxicFrog> | ...er? |
| 00:57 | <@ToxicFrog> | Look at your function. |
| 00:57 | | * ilovefire looks. |
| 00:57 | <@ToxicFrog> | What happens if you pass it 3? |
| 00:57 | <@ilovefire> | It would give me, umm.... nothing? |
| 00:58 | <@ToxicFrog> | Yes, but what happens inside the function? |
| 00:58 | <@ToxicFrog> | Follow the code. |
| 00:59 | <@ilovefire> | it checks to see if 3 is divisble by 2, and then, umm... ah, I need to insert a break, don't I? |
| 00:59 | <@ToxicFrog> | ...no |
| 00:59 | <@ilovefire> | ... Damnit. |
| 00:59 | <@ilovefire> | Well, it checks to see if 3 is divisible by 2, and seeing that it isn't, umm, goes no where? |
| 01:00 | <@ToxicFrog> | And by goes nowhere you mean...? |
| 01:01 | <@ilovefire> | Well, the program dosen't say what to do if k 5 n != 0. |
| 01:01 | <@ilovefire> | ... ah, elif time, isn't it? |
| 01:01 | <@ToxicFrog> | No. |
| 01:01 | <@ilovefire> | *k % n |
| 01:01 | <@ToxicFrog> | If k % n != 0, there's no elif, so it doesn't hit that; and there's no else, so it doesn't hit that. |
| 01:01 | <@ToxicFrog> | What it does is it just skips the if and keeps going. |
| 01:02 | <@ToxicFrog> | In this case, there's nothing after the if. |
| 01:02 | <@ToxicFrog> | So it goes back to the top of the loop for another go with a different n, until it runs out of values for n. |
| 01:02 | <@ilovefire> | Okay... |
| 01:02 | <@ToxicFrog> | Actually, tracing this with larger numbers may be more instructive. |
| 01:02 | <@ToxicFrog> | Say you call is_prime(9) |
| 01:02 | <@ToxicFrog> | So, first time around the loop, n is 2. |
| 01:03 | <@ToxicFrog> | 9 % 2 is 1, so the if doesn't get executed. |
| 01:03 | <@ToxicFrog> | And it goes back to the top of the loop and does it again where n is 3. |
| 01:03 | | * ilovefire nods. |
| 01:03 | <@ToxicFrog> | And 9 % 3 is 0, so the if gets executed and the function returns False, indicating that 9 is not prime. |
| 01:04 | <@ToxicFrog> | Now, say you call is_prime(5) |
| 01:04 | <@ilovefire> | okay... |
| 01:04 | <@ToxicFrog> | The first time, n is 2, so the if doesn't get followed. |
| 01:04 | <@ToxicFrog> | The second time, it's 3. If still doesn't get followed. |
| 01:05 | <@ToxicFrog> | Then 4. And 5 % 4 is 1. So it still isn't followed. |
| 01:05 | <@ToxicFrog> | And now it's out of values for n, so it just falls off the end of the loop. |
| 01:05 | <@ToxicFrog> | But there's nothing after the loop, so it falls right out of the function and returns nothing. |
| 01:06 | <@ilovefire> | Ah. |
| 01:06 | <@McMartin> | One of the things I don't like about Python is that it doesn't warn you about that. |
| 01:07 | <@ilovefire> | That explains all the blank lifes after I try this. |
| 01:07 | <@ToxicFrog> | http://rafb.net/p/M55rd022.html -- here's a version that's noisy |
| 01:08 | <@ToxicFrog> | So try that with a few primes and non-primes. |
| 01:08 | <@ToxicFrog> | And consider that what you need is a "return True" somewhere in is_prime. |
| 01:08 | <@ToxicFrog> | Based on that you should be able to figure out where. |
| 01:10 | | SovietNinja is now known as gnolam |
| 01:12 | <@ilovefire> | can you do something like, say, 'if print "x": | return True"? |
| 01:12 | <@ToxicFrog> | .... |
| 01:12 | <@ToxicFrog> | What would that do, and why do you want it? |
| 01:13 | <@ilovefire> | Well, if it prints out k, "is prime", then I know that it's prime, so I want it to return True, that the number k, which we're testing for being prime, is prime. |
| 01:14 | <@ToxicFrog> | print isn't conditional. |
| 01:14 | <@ToxicFrog> | If it reaches that line of code, it will always display that message. |
| 01:14 | <@ilovefire> | ... oh. |
| 01:14 | <@McMartin> | In python, print also isn't an expression. |
| 01:15 | <@ilovefire> | Err. |
| 01:15 | <@ilovefire> | Man, I have a long, long way to go before I'll ever be decent at this. |
| 01:20 | | * ilovefire tries to figure this out. |
| 01:21 | <@ToxicFrog> | I find that the lack of explicit endmarkers in python makes this sort of thing harder than it should be, for newbies >.< |
| 01:21 | <@McMartin> | Hmm. |
| 01:21 | <@McMartin> | TF, Spoiler question inc in /msg |
| 01:22 | <@ilovefire> | Okay, I think I can declare myself officially, lost. |
| 01:24 | | * McMartin pokes TF |
| 01:25 | <@McMartin> | OK, having consulted. |
| 01:25 | <@McMartin> | Hint 1: You realize that, as a result of an if statement, you can do more than one thing, right? |
| 01:26 | <@McMartin> | (I was checking to make sure that was on the list of topics covered) |
| 01:26 | <@ilovefire> | ... I don't... think I realized that... before. |
| 01:27 | <@McMartin> | ... OK, maybe it wasn't. |
| 01:27 | <@McMartin> | So. |
| 01:27 | <@McMartin> | if (condition): |
| 01:27 | <@McMartin> | statement1 |
| 01:27 | <@McMartin> | statement2 |
| 01:27 | <@McMartin> | etc etc etc |
| 01:28 | <@ilovefire> | Okay... |
| 01:28 | <@McMartin> | other code |
| 01:28 | <@McMartin> | That etc etc etc needs another space |
| 01:28 | <@McMartin> | Basically, each statement that's indented after the colon will only run if the condition holds |
| 01:28 | <@McMartin> | Otherwise it skips the paragraph. |
| 01:28 | <@ilovefire> | Allright. |
| 01:29 | <@McMartin> | While it is legal, if there's only one statement, to do "if condition: statement" on one line, many Python programmers will give you the hairy eyeball for it. |
| 01:29 | <@ilovefire> | ... okay. |
| 01:29 | <@McMartin> | ... also, IIRC, the term is "stanza", not "paragraph". My mistake. |
| 01:33 | <@ilovefire> | So, I need to put in a seocnd if statement, then? |
| 01:33 | | * Vornicus returns |
| 01:34 | <@ilovefire> | Hi vorn! I'm working on it! |
| 01:34 | < Vornicus> | I see this. |
| 01:34 | | * Vornicus gives McM the hairy eyeball. |
| 01:35 | < Vornicus> | What are we doing, short version? |
| 01:36 | <@ToxicFrog> | Finding primes via test division using two functions, primes() and is_prime(k) |
| 01:36 | <@McMartin> | I actually only popped in late in the game, but there seemed be some confusion about the ability to do multiple things in response to a condition. |
| 01:36 | < Vornicus> | ...that's a term I wonder the origin of. |
| 01:36 | < Vornicus> | Ah, so. |
| 01:37 | <@ToxicFrog> | We got as far as http://rafb.net/p/2xb1tK29.html and are now stuck on getting it to return True when k is prime. |
| 01:37 | < Vornicus> | ILF: /every/ nestable statement - def, for, if, and the ones we haven't covered (try/except, class, while) - can have multiple things happen to respond to it. |
| 01:37 | < Vornicus> | Okay, looking at that. |
| 01:37 | < Vornicus> | When do we know it's prime? |
| 01:40 | <@ilovefire> | if for all values of n, k % n != 0 |
| 01:40 | < Vornicus> | Okay, so, we know when the for is done. |
| 01:41 | < Vornicus> | Where do we put a line of code so it gets executed when the for is done? |
| 01:43 | <@ilovefire> | on the line after the last thing needed in the for statement, indented one less? |
| 01:44 | < Vornicus> | Sounds sensical. Show me. |
| 01:45 | <@ilovefire> | http://rafb.net/p/haMcHi22.html the blank if statement. |
| 01:46 | < Vornicus> | Well, use a return, and don't put that if in there, but you've got it. |
| 01:48 | <@ilovefire> | so it should look more like this, say? http://rafb.net/p/pO4MG636.html |
| 01:51 | < Vornicus> | that print k, "is prime" is dead code. |
| 01:52 | <@ilovefire> | Vorn; Admittedly, yes. |
| 01:52 | | * ilovefire forgot to remove it. |
| 01:54 | <@McMartin> | And the "is not divisible" print is probably going to be cluttery too, for one's results... |
| 01:55 | < Vornicus> | Very. |
| 01:55 | | * ilovefire removes |
| 01:56 | < Vornicus> | (granted it /is/ useful when you're fiddling with it, but once it's done, take it out!) |
| 01:56 | < Vornicus> | (most of the time, you're doing thousands if not millions of executions of loops and functions.) |
| 01:57 | <@ilovefire> | Rihgt... |
| 01:57 | < Vornicus> | (so spamming your console with that stuff is a Bad Thing) |
| 01:57 | < Vornicus> | okay, run that thing, let's see your list of primes. |
| 01:58 | <@ilovefire> | is it supposed to just print '2 is prime' over and over and over again? |
| 01:58 | <@ilovefire> | I need to include a break, don't I. |
| 01:58 | < Vornicus> | Where are we now? |
| 01:59 | < Vornicus> | oh, heh. |
| 01:59 | < Vornicus> | This is because your variable names are wrong. Check x vs k in the primes() function. |
| 02:00 | <@ilovefire> | Ah. |
| 02:00 | <@ilovefire> | That was a simple, obvious mistake. |
| 02:00 | < Vornicus> | Been there, done that, bought the t-shirt, hat, socks, wallet, and boxer shorts. |
| 02:00 | < Vornicus> | and commemorative snowglobe. |
| 02:01 | | * McMartin swears mightily, starts digging through Really Old Backups |
| 02:01 | | * ilovefire fiddles a bit with the variables.. |
| 02:01 | <@ilovefire> | Got it! |
| 02:02 | <@ilovefire> | http://rafb.net/p/ntyuDi58.html here's the code. YOu want the list of results as well |
| 02:02 | <@ilovefire> | ? |
| 02:03 | < Vornicus> | No, that will do. |
| 02:04 | < Vornicus> | okay, now I want you to make an improvement: change primes() to primes(n), where it prints all the primes up to and including n. |
| 02:04 | < Vornicus> | (this should not be hard) |
| 02:05 | <@ilovefire> | http://rafb.net/p/MtJFHI96.html as so? |
| 02:05 | < Vornicus> | That won't include n if prime. Close though. |
| 02:06 | <@ilovefire> | ah, right, should be xrange(2,n+1) |
| 02:06 | < Vornicus> | All right then. |
| 02:07 | < Vornicus> | Now, give me a wild guess: if you put in primes(1000000), how much longer would it take than primes(1000)? |
| 02:08 | <@McMartin> | Ha HA, found it |
| 02:08 | <@ilovefire> | hmm, roughly three times as long, I'd say--likely wrong, though. Perhaps twice as long? |
| 02:08 | < Vornicus> | try a million times as long. |
| 02:09 | <@ilovefire> | ... |
| 02:09 | <@ilovefire> | Interesting. |
| 02:09 | < Vornicus> | (we're doing a thousand times as many things, and they're on average a thousand times as large) |
| 02:09 | <@ilovefire> | Ah. |
| 02:09 | <@McMartin> | You're counting from 2 to n, and inside that loop, you have another loop that's basically 2 to n. |
| 02:09 | | * ilovefire decides to test it. |
| 02:09 | < Vornicus> | hang on, you might want to instrument it. |
| 02:10 | <@McMartin> | This is pretending that printing results is instantaneous, and, uh, it's not. |
| 02:10 | <@McMartin> | It's entirely possible that the "scroll the output window" code will end up dominating both, so it will instead increase linearly with the number of primes. |
| 02:10 | <@McMartin> | In wall-clock time. |
| 02:10 | | * Vornicus writes you some instrumentation code, because he knows how it works. |
| 02:10 | <@ToxicFrog> | Hmm. When is the appropriate time to introduce a newbie to O(), ?() and ?()? |
| 02:11 | < Vornicus> | Well, I'm doing something with it right now. I want to get back to that crazy-ass number theory I was swinging around earlier. |
| 02:11 | <@McMartin> | TF: Well, Berkeley introduces it before teaching Java. |
| 02:12 | <@ToxicFrog> | I don't know when they start teaching Java, so. |
| 02:12 | <@McMartin> | Ah. Second course in the series. |
| 02:12 | <@ToxicFrog> | Are we talking "concurrent with first-year intro to programming", or "second semester", or "sometime before third year", or what? |
| 02:12 | <@McMartin> | O() and friends are in the first, which is taught in Scheme. |
| 02:12 | <@McMartin> | second semester. |
| 02:13 | | * ToxicFrog nods. |
| 02:13 | | mode/#code [+o Vornicus] by Vornicus |
| 02:13 | <@Vornicus> | http://rafb.net/p/gbf9pr92.html <--- replace primes() with the given function, and put that import at the top of your file. |
| 02:13 | <@ToxicFrog> | Is that full on algorithmic analysis, or just "here they are, here's what they mean, here's how to use them"? |
| 02:13 | <@Vornicus> | Now it will give you time taken, and average time per number tried. |
| 02:14 | <@McMartin> | The latter for anything non-polynomial, analysis for polynomial. |
| 02:14 | | * ToxicFrog nods |
| 02:14 | <@McMartin> | You were expected to distinguish between linear/quadratic/cubic, but the logarithmic and exponential cases weren't covered except with handwaves. |
| 02:14 | <@Vornicus> | Note that McM is probably right and the printing and scrolling will probably take up more time. |
| 02:14 | <@ilovefire> | Okay... |
| 02:14 | <@McMartin> | To get just computation time, remove the print statement. |
| 02:15 | <@Vornicus> | remove the print statement that prints k, that is. |
| 02:15 | <@ToxicFrog> | Similar to here, then. |
| 02:15 | <@McMartin> | Er, the "print k" statement, replacing it with, say "total = total+1". |
| 02:15 | <@McMartin> | and a total = 0 before the for block. |
| 02:15 | <@ToxicFrog> | Except polynomial is also deferred to third semester (analysis of algorithms). |
| 02:16 | <@ilovefire> | so, umm, I just put import time at the top and replace my primes() with the function vorn gave me, or do I do something else? I sort of got lost in the speaking above. |
| 02:16 | <@Vornicus> | That's what you do. |
| 02:17 | <@Vornicus> | http://rafb.net/p/SH9KDT72.html <--- here's a better primes() |
| 02:17 | <@Vornicus> | ((this one won't get bogged down in printing, and covers the improvements McM showed to give you a better idea of the time taken by the calculations) |
| 02:18 | <@ilovefire> | okay, now I run it? |
| 02:18 | <@Vornicus> | Run it with primes(1000) and primes(1000000) |
| 02:18 | <@Vornicus> | Don't do primes(1000000000), we'll be here all week. |
| 02:19 | <@ilovefire> | strange... |
| 02:19 | <@ilovefire> | primes(1000000) dosne't give me, well, anything. |
| 02:20 | <@Vornicus> | It's working. |
| 02:20 | <@Vornicus> | What's the line for primes(1000)? |
| 02:20 | <@ToxicFrog> | Remember, it takes a million times as long as primes(1000). |
| 02:20 | <@ilovefire> | 168 0.0159997940063 1.60158098162e-005 |
| 02:20 | <@Vornicus> | 15999.794006300001 seconds. |
| 02:21 | <@ToxicFrog> | If I'm reading this right, we'll be here for - yes. |
| 02:21 | <@Vornicus> | It'd take a few hours. |
| 02:21 | <@ToxicFrog> | Four and a half hours, give or take. |
| 02:21 | <@McMartin> | To demonstrate quadraticness, the usual plan is to show that doubling the problem quadruples the time. |
| 02:21 | <@ToxicFrog> | try primes(10000), which should only take a hundred times as long or so. |
| 02:22 | <@ilovefire> | 1229 1.64100003242 0.000164116414884 |
| 02:22 | <@Vornicus> | See? about a hundred times as long. |
| 02:22 | <@Vornicus> | This obviously sucks. Can we improve it? |
| 02:23 | <@ToxicFrog> | (at least it's not EXPTIME~) |
| 02:23 | <@ilovefire> | Umm, probably... |
| 02:23 | <@Vornicus> | Do me a favor. |
| 02:23 | <@Vornicus> | Figure out the factors of 24. |
| 02:23 | <@Vornicus> | Pair them up, so you can which goes with which. |
| 02:25 | <@ilovefire> | well, 24 factors out to (2*2)*(2*3) |
| 02:25 | <@Vornicus> | right, so what numbers can you divide 24 by evenly? |
| 02:26 | <@ilovefire> | 2, 3, 4, and 6. |
| 02:26 | <@Vornicus> | There are at least two more. |
| 02:27 | <@Vornicus> | and, remember: pair them up. I want to see how they go together. |
| 02:27 | <@ilovefire> | well, 12 and 24 too. |
| 02:27 | | * ilovefire nods. |
| 02:27 | <@Vornicus> | Still missing one, and if you've got 24 in there, you'remissing two. |
| 02:27 | < C_tiger> | Nicely done, ilf for getting the first iteration of primes() working. |
| 02:27 | <@ilovefire> | ah right, 8. |
| 02:28 | <@ilovefire> | 2 and 12, 3 and 8, 4 adn 6, and 24 and 1? |
| 02:28 | <@Vornicus> | Okay. |
| 02:28 | <@ilovefire> | C: Well, I had a hell of a lot of help. |
| 02:28 | <@Vornicus> | Notice how each one has a high number, and a low number? |
| 02:29 | | * ilovefire nods. |
| 02:29 | < C_tiger> | Help is important when you're starting out. |
| 02:31 | <@ilovefire> | Vorn: Yeah. |
| 02:32 | <@Vornicus> | well, is there a break-even point? |
| 02:32 | <@Vornicus> | A point at which every possible divisor above that point is already covered by a divisor below that point? |
| 02:35 | <@ilovefire> | Hmm, looking at it--yes. |
| 02:35 | <@Vornicus> | Okay. |
| 02:36 | <@ilovefire> | Anything above 3 can be covered by some combination of 2 and 3. |
| 02:36 | <@Vornicus> | Do the same for 36 that you did for 24. |
| 02:36 | | * ilovefire nods. |
| 02:36 | <@Vornicus> | (for the record 36 is 2*2*3*3) |
| 02:37 | | * ilovefire nods, can do prime factorization. |
| 02:37 | <@ilovefire> | I get 4 and 9, 2 and 18, 6 adn 6, and 3 adn 12. And, of course, 36 adn 1. |
| 02:37 | <@Vornicus> | Good. |
| 02:38 | <@Vornicus> | See the break-even point? |
| 02:39 | | * ilovefire nods |
| 02:39 | <@Vornicus> | What is it? |
| 02:41 | <@ilovefire> | if it's four or above, it can be factored out to some form of 2, 3, or both. |
| 02:41 | <@Vornicus> | nnot what I'm aiming at. |
| 02:41 | <@ilovefire> | Gorramit. |
| 02:41 | <@ilovefire> | Umm. |
| 02:42 | <@Vornicus> | I am aiming at a number k such that, if you have a number above it, you need to multiply it by another number below it to get the number n. |
| 02:42 | <@ilovefire> | Ah. |
| 02:44 | <@Vornicus> | For n = 36, k should be obvious. |
| 02:45 | <@ilovefire> | Right... |
| 02:46 | <@Vornicus> | (hint, look for something strange in the factor pairs you listed) |
| 02:46 | < C_tiger> | The takeaway lesson here is twofold 1) even though computers are fast, some calculations take a LONG time 2) Thus you should optimize and often it takes a little math knowledge to figure out how best to optimize a given piece of code. |
| 02:47 | <@ilovefire> | Umm... well, there's not alot of odd numbers... uhh, uhh, uhh. |
| 02:47 | <@Vornicus> | There is a specific factor pair that needs noticing. |
| 02:47 | <@ilovefire> | the number itself and one? umm... something? |
| 02:47 | <@Vornicus> | It's /not/ in 24. |
| 02:48 | <@Vornicus> | in the factor pairs for 24. |
| 02:48 | <@Vornicus> | that is. |
| 02:48 | < C_tiger> | Hmm... Ok ilf, here's another way of thinking about it. |
| 02:49 | < C_tiger> | List each factor of 36. |
| 02:49 | < C_tiger> | In order. |
| 02:49 | < C_tiger> | (don't worry about its pair just yet) |
| 02:51 | <@Vornicus> | Do this on a piece of paper, or in notepad, and give each factor its own line. |
| 02:52 | <@ilovefire> | okay, in order of... lowest number? |
| 02:52 | < C_tiger> | (Vorn is crazy psychic and can see exactly where I'm going with this before I even say it.) |
| 02:52 | < C_tiger> | Just the factors. |
| 02:52 | <@Vornicus> | Not the pairs. |
| 02:52 | <@Vornicus> | Just the factors. |
| 02:53 | < C_tiger> | I'll get you started: |
| 02:53 | < C_tiger> | 1 |
| 02:53 | < C_tiger> | 2 |
| 02:53 | < C_tiger> | 3 |
| 02:54 | <@ilovefire> | Ah. |
| 02:55 | <@ilovefire> | 1, 2, 3, 4, 6, 9, 12, 18. |
| 02:55 | <@Vornicus> | one more. |
| 02:55 | <@ilovefire> | oh right, 26. |
| 02:55 | <@ilovefire> | ... 36 |
| 02:55 | <@Vornicus> | Okay. |
| 02:56 | <@Vornicus> | Now, put the numbers they pair with next to them. 1 36, 2 18... |
| 02:57 | <@Kyrre> | So 6 is your breakeven point? |
| 02:57 | <@ilovefire> | after 6 and 6, they start repeating--it breaks even. |
| 02:57 | | * Vornicus beats Kyrre for going faster than everyone else. |
| 02:57 | <@Kyrre> | Oh, right. |
| 02:57 | <@Vornicus> | Right. So what's 6 to 36. |
| 02:57 | | * Kyrre dies a horrible, bloody, and very messy death. |
| 02:58 | <@ilovefire> | The square root, but also some form of median, yes? |
| 02:59 | <@Vornicus> | The square root. |
| 02:59 | <@Vornicus> | So go look at 24. what's the square root of 24? |
| 02:59 | < C_tiger> | (You can use a calculator for this) |
| 02:59 | <@Kyrre> | it's silly. |
| 03:00 | < C_tiger> | What is? |
| 03:00 | <@ilovefire> | a very silly square root that appears to be an irrational number, but then my calculator only displays 10 digits. |
| 03:00 | < C_tiger> | It's about 4.9 |
| 03:00 | <@ilovefire> | or so, yeah. |
| 03:00 | < C_tiger> | Now list the factors of 24. |
| 03:01 | <@Kyrre> | $sqrt(24) = 4.898979 |
| 03:02 | <@ilovefire> | just the factors gives 1, 2, 3, 4, 6, 8, 12, and 24. The pairs are 1 and 24, 2 and 12, 3 and 8, 4 and 6, 6 and 4, 8 and 3, 12 and 2, and 24 and 1. |
| 03:03 | < C_tiger> | So where's your breakeven point where you start repeating yourself? |
| 03:04 | <@ilovefire> | between 6 and 4. |
| 03:04 | < C_tiger> | And where is the square root of 24? |
| 03:05 | <@ilovefire> | between four and six. |
| 03:05 | <@Vornicus> | See what we're getting at? |
| 03:06 | < C_tiger> | So. In is_prime(), how far do you have to test numbers before you start repeating yourself? |
| 03:06 | <@Kyrre> | I don't. But then again.... |
| 03:06 | <@Vornicus> | Kyrre needs to pay more attention. |
| 03:06 | <@Kyrre> | Or read the backlog, I reckon that'd help. |
| 03:07 | <@ilovefire> | C: up to the square root of the number I'm testing. |
| 03:07 | < C_tiger> | Bingo! |
| 03:08 | <@ilovefire> | ... wait, I actually got something right the first time I answered it? |
| 03:09 | | * Kyrre dances with ilovefire. |
| 03:09 | < C_tiger> | Go dance! |
| 03:09 | | Vornicus [~vorn@ServicesOp.Nightstar.Net] has quit [Ping Timeout] |
| 03:09 | | * ilovefire dances with Kyrre, whoo! |
| 03:09 | <@ToxicFrog> | Kyrre: we're teaching ilovefire python in specific and programming in general. |
| 03:09 | < C_tiger> | Then try it out, and run your original program and then the modified program. |
| 03:09 | | Vornotron [~vorn@Admin.Nightstar.Net] has joined #code |
| 03:09 | <@Kyrre> | But it's full of snækes! |
| 03:10 | | gnolam [lenin@Nightstar-10613.8.5.253.static.se.wasadata.net] has quit [Quit: Z?] |
| 03:10 | < Vornotron> | koay, where were we? |
| 03:10 | | Vornotron is now known as Vornicus |
| 03:10 | < C_tiger> | He's doing awesomely. |
| 03:10 | < Vornicus> | Good. |
| 03:10 | < Vornicus> | How awesomely is he doing? |
| 03:10 | < C_tiger> | And about to try his newly modified program and compare it to his unoptimized one. |
| 03:11 | < Vornicus> | So you showed him how to go get sqrt? |
| 03:11 | <@Kyrre> | Nope. |
| 03:11 | < C_tiger> | Hey, he never asked. |
| 03:11 | <@ToxicFrog> | He knows **, he should be able to figure it out~ |
| 03:11 | < Vornicus> | a true thing. |
| 03:12 | <@ilovefire> | well, if x ** 2 is the square root of x, then, umm... |
| 03:12 | <@ilovefire> | Give me a moment. |
| 03:12 | <@ToxicFrog> | Remember - ** is the exponentiation operator. |
| 03:12 | <@ToxicFrog> | x ** 2 is x squared, x ** 3 is x cubed. |
| 03:12 | <@ilovefire> | I meant squared. |
| 03:12 | <@ilovefire> | I was thinking squared, don't know how the root crept in. |
| 03:13 | < Vornicus> | Also note that you /very need/ to make the top end of your range an integer, and there's a possibly tricky bit with making your range right. |
| 03:13 | < C_tiger> | Wait you do? |
| 03:13 | <@Kyrre> | ½ |
| 03:13 | < C_tiger> | Kyrre! No cookie. |
| 03:13 | | * ToxicFrog baps Serah |
| 03:13 | <@ToxicFrog> | We're trying to make him think here! |
| 03:13 | < Vornicus> | >>> xrange(1,2.5) |
| 03:13 | < Vornicus> | __main__:1: DeprecationWarning: integer argument expected, got float |
| 03:13 | < Vornicus> | xrange(1, 2) |
| 03:13 | <@Kyrre> | Bah, you all probably use UTF-8 anyway. |
| 03:14 | < C_tiger> | No, I don't. |
| 03:14 | < C_tiger> | Still, no cookie. |
| 03:14 | < Vornicus> | Failover. |
| 03:14 | <@ToxicFrog> | I do, but it falls back to latin-1 if it can't read something as UTF-8. |
| 03:14 | <@ToxicFrog> | So I saw that just fine, thank you. |
| 03:14 | <@Kyrre> | :p |
| 03:14 | < Vornicus> | As did everyone else. |
| 03:14 | | * Kyrre is writing in latin-2 ! |
| 03:15 | < Vornicus> | Anyway I don't think ilf actually /knows/ how exponentiation works like that. |
| 03:15 | <@Kyrre> | Meh, I'll just stop spoiling your efforts and go over in the corner. |
| 03:15 | < C_tiger> | personally, I think it'd be a better lesson in PROGRAMING if we introduce modules. |
| 03:15 | < C_tiger> | PROGRAMMING also. |
| 03:15 | < Vornicus> | oh, indeed. |
| 03:15 | < C_tiger> | But that's just me. |
| 03:15 | < Vornicus> | It was how I was going to do it. |
| 03:15 | < Vornicus> | Anyway, ilf. |
| 03:15 | <@ilovefire> | You're right, I have no idea how exponentation works like that. |
| 03:16 | <@ilovefire> | I figured taht 1/2 was just a mistell or something. |
| 03:16 | < Vornicus> | There is a function that given a number will give its square root. It's called sqrt. |
| 03:16 | < C_tiger> | Try it. |
| 03:16 | <@Kyrre> | Time is an illusion, lunchtime doubly so. |
| 03:16 | < C_tiger> | free time triply. |
| 03:17 | <@ToxicFrog> | And yeah, you should be using sqrt. |
| 03:17 | <@ilovefire> | NameError: name 'sqrt' is not defined |
| 03:17 | < Vornicus> | But, the problem is... it's not in the builtins, as you can see. |
| 03:17 | | * ilovefire nods |
| 03:17 | < Vornicus> | It's in the math library. |
| 03:17 | <@ToxicFrog> | But it's worth noting for future mathematical endeavours that, as Kyrre said, the square root of n is equal to n ** 1/2 |
| 03:18 | <@ToxicFrog> | And, indeed, the k'th root of n is n ** 1/k. |
| 03:18 | < Vornicus> | Except that tries integer math and you should make it right. |
| 03:18 | < Vornicus> | So, at the top of your file, put import math |
| 03:18 | <@ToxicFrog> | I mean mathematically, not in python |
| 03:18 | < Vornicus> | As I did with time. |
| 03:18 | <@ilovefire> | does it matter if it's above or below time? |
| 03:18 | < Vornicus> | Nope. |
| 03:19 | <@ilovefire> | okay. Done, saved, restarted shell, and.... |
| 03:19 | < C_tiger> | What that does is it brings in a library of functions that you don't have to write. |
| 03:19 | <@ilovefire> | still gives me that error when I try, say, sqrt(x), sqrt x, or sqrt (x). Well, sqrt x gives me an invalid syntax error, but. |
| 03:20 | < C_tiger> | Even inside your program? |
| 03:20 | < Vornicus> | Okay, good reason for that: sqrt is /in/ the math module. |
| 03:20 | <@ilovefire> | C: yes. |
| 03:20 | < C_tiger> | Ah. |
| 03:20 | < Vornicus> | So you have to tell it where to find it. |
| 03:20 | < C_tiger> | Oh, right, you... rught. |
| 03:21 | < C_tiger> | right. |
| 03:21 | < Vornicus> | See how I said time.time()? |
| 03:21 | <@ilovefire> | okay... |
| 03:21 | <@Kyrre> | Doesn't the machine just approximate the number? |
| 03:21 | < Vornicus> | That is a call to the time() function (which gives the current time), which it can find in the time module. |
| 03:21 | <@Kyrre> | By running it through n iterations of a guessing machine. |
| 03:22 | < Vornicus> | It actually uses a Price Is Right algorithm, I think. Well, not sure. It does get it as right as possible. |
| 03:22 | <@Kyrre> | Anyways, half past four, going to bed. |
| 03:22 | <@Kyrre> | Night people. |
| 03:22 | < C_tiger> | G'night Kyrre. |
| 03:22 | <@Kyrre> | Yeah, guesstimates it and checks if it's too high, too low, or just fine. |
| 03:23 | < Vornicus> | Doesn't guesstimate. It uses a very precise and bounded algorithm. |
| 03:23 | <@ToxicFrog> | Serah...we're still in the lies-to-children phase. He doesn't need to know about the internal implementation of the math library yet. |
| 03:23 | < Vornicus> | Anyway, back to ilf's thing. |
| 03:23 | <@Kyrre> | Hmmm... |
| 03:23 | | * Kyrre steals Ben. |
| 03:23 | < Vornicus> | (I still like the term Price Is Right algorithm) |
| 03:23 | <@ToxicFrog> | eep |
| 03:24 | | * ToxicFrog snuggles Serah to sleep |
| 03:24 | <@Kyrre> | Weee. |
| 03:24 | | * Kyrre does however wonder why that didn't highlight. |
| 03:24 | < Vornicus> | ANYWAY. |
| 03:24 | < Vornicus> | ILF: how do you think you ask for "sqrt, in the math module"? |
| 03:25 | <@ilovefire> | import math.math(sqrt)? |
| 03:25 | < Vornicus> | nope. |
| 03:26 | < C_tiger> | You've got import math, now we're looking at the place where you call the function. |
| 03:27 | <@ilovefire> | def sqrt: | math.math(sqrt) or something like that? |
| 03:27 | < C_tiger> | Nope (but good try.) |
| 03:27 | < Vornicus> | Do you know what I mean when I say "call a function"? |
| 03:28 | <@ilovefire> | No. |
| 03:29 | < Vornicus> | when you said primes(1000), you called primes. |
| 03:29 | < Vornicus> | when you said sqrt(n), you tried to call sqrt. |
| 03:30 | <@ilovefire> | Ah, okay. |
| 03:31 | < C_tiger> | so sqrt(n) is most of the way there. |
| 03:31 | < Vornicus> | but you need to tell it where to find it: in the math library. |
| 03:32 | < C_tiger> | Ok, backtrack a tiny little bit, if you're telling someone where to find a file on a computer, how would you do it? |
| 03:33 | <@ilovefire> | tell them the directory? |
| 03:33 | < C_tiger> | Right you'd say directory\filename |
| 03:33 | < C_tiger> | So, in python, you do the same but instead of \ you do . |
| 03:33 | <@ilovefire> | ah, okay... |
| 03:33 | < Vornicus> | (or directory/filename on unix, or directory:filename on oldschool mac) |
| 03:34 | < C_tiger> | He's on a windows machine, I'm pretty sure. |
| 03:34 | <@ilovefire> | yes, windows XP. |
| 03:34 | < C_tiger> | so how would you call sqrt then? |
| 03:35 | <@ilovefire> | math.sqrt (x)? |
| 03:35 | <@ToxicFrog> | Well, on any recent windows you'd use / too. |
| 03:35 | < C_tiger> | Yep. |
| 03:35 | < Vornicus> | Give the man a cigar. |
| 03:35 | < Vornicus> | Keep the lighter away from him though, you don't know what he might do with it. |
| 03:35 | < C_tiger> | So try that now. |
| 03:35 | < C_tiger> | (there will be problems, we will address them, but trial and error is a wonderful thing.) |
| 03:36 | <@ilovefire> | Bah! |
| 03:36 | <@ilovefire> | (at vorn's commenta bout the lighter) |
| 03:37 | <@ilovefire> | just as an example: math.sqrt(25) gives me 5.0 |
| 03:37 | < Vornicus> | Yep. |
| 03:37 | < C_tiger> | Ok, well, put it into your program and see what happens. |
| 03:38 | <@ilovefire> | not the one with time,r ight? the one that actually prints out the prime numbers? |
| 03:39 | < C_tiger> | Either. |
| 03:39 | <@McMartin> | If it breaks the code, you'll be able to tell because the number of detected primes should be different. |
| 03:39 | < Vornicus> | Either. The one with the time would actually be better, because the number of primes would be different for wrong code. |
| 03:40 | < C_tiger> | True and you don't have to read through all that output to figure it out. |
| 03:40 | | * McMartin kicks Windows in the FC.EXE |
| 03:40 | <@ToxicFrog> | FC.EXE? |
| 03:40 | <@McMartin> | Not quite diff |
| 03:40 | <@McMartin> | "File compare" |
| 03:41 | | * ilovefire tosses some waters in the eyes to drive out the sleep madness, goes to work. |
| 03:41 | <@ToxicFrog> | Aah. |
| 03:41 | <@ilovefire> | Okay, I can honestly admit I have no idea what I'm supposed to do here, umm. |
| 03:42 | < C_tiger> | Ok, why did we want to calculate the square root? |
| 03:42 | <@ilovefire> | to figure out where the, err, what was the term... breakeven point is. |
| 03:42 | <@ilovefire> | ... ah. |
| 03:42 | < C_tiger> | See? I didn't even have to say anything. |
| 03:43 | <@ilovefire> | Also, while I'm busy, am I a slow, fast, or just regular learner at this? |
| 03:43 | < C_tiger> | Oh gah, Microsoft, update tuesday. I'll be back in a bit. |
| 03:44 | <@ilovefire> | right, with the modifications I made to it (making the pastie now), I get this error: DeprecationWarning: integer argument expected, got float |
| 03:44 | < C_tiger> | Great. |
| 03:44 | <@ilovefire> | and a wrong number for the number of primes. |
| 03:44 | <@ilovefire> | on primes(1000) |
| 03:44 | < Vornicus> | ilf: we're going a hell of a lot faster than we would with a whole classroom of people; that said, we are slowing down because your mathematical knowledge is for all practical purposes nonexistent. |
| 03:44 | < Vornicus> | i know one you're missing. |
| 03:45 | < Vornicus> | try is_prime(25) |
| 03:45 | <@ilovefire> | http://rafb.net/p/dTkZrA62.html |
| 03:45 | <@ilovefire> | Vorn: gets me true. |
| 03:45 | < Vornicus> | is 25 actually prime? |
| 03:45 | <@ilovefire> | No. |
| 03:46 | < Vornicus> | okay, you know how earlier you asked it to tell you what numbers it was checking? by printing? |
| 03:46 | <@ilovefire> | yes. Do it again? |
| 03:47 | < Vornicus> | Yeah. And when you've put it back, do is_prime(25) again. |
| 03:47 | < C_tiger> | ilf if it makes you feel better, it took two weeks to get to function writing in my first CS class. Of course we did flow control (all flavors) first. |
| 03:48 | < C_tiger> | BRB, microsoft insists I restart. |
| 03:48 | | C_tiger [~c_wyz@Nightstar-5378.nycmny.east.verizon.net] has quit [Quit: Tuesday] |
| 03:48 | < Vornicus> | Function writing is imo really supposed to be taught third, after arithmetic and assignment. |
| 03:49 | <@ilovefire> | Vorn: prints out 2, 3, and 4. |
| 03:49 | < Vornicus> | All right. Why isn't it trying 5? |
| 03:49 | < Vornicus> | (hint: remember how xrange works!) |
| 03:49 | <@ilovefire> | ... Ah, wait, I see. |
| 03:50 | <@ilovefire> | It should be xrange(2,math.sqrt(k)+1), not xrange(2,math.sqrt(k)) |
| 03:50 | < Vornicus> | okay. |
| 03:50 | < Vornicus> | While we're in there, let's get rid of that Deprecation Warning. |
| 03:50 | < Vornicus> | in order to do that, we have to turn whatever we're throwing into xrange be an integer. |
| 03:51 | <@ilovefire> | okay... |
| 03:51 | < Vornicus> | so instead of xrange(2,math.sqrt(k)+1), xrange(2,int(math.sqrt(k))+1) |
| 03:51 | | * ilovefire nods. |
| 03:52 | <@ilovefire> | is_prime(25) gives me false! |
| 03:52 | < Vornicus> | int(k) is a function that turns the thing you put into it into an integer, usually by truncation: a number between two integers will get converted to the one nearer to 0. |
| 03:53 | < Vornicus> | Good. Now get that debug awfulosity out of there, and run primes(1000) and primes(10000) |
| 03:54 | < Vornicus> | (the print statement I had you put back in earlier is the debug awfulosity) |
| 03:54 | <@ilovefire> | primes(1000) gives me 168 0.0 0.0 |
| 03:55 | <@ilovefire> | primes(10000) gives me 1229 0.0620000362396 6.20062368633e-006 |
| 03:55 | <@McMartin> | An Infinity Percent Slowdown >_> |
| 03:55 | <@ToxicFrog> | I hate it when that happens~ |
| 03:56 | <@McMartin> | (Idly, I need to reboot, thus losing my clipboard. Unrelated to current problem set, but will come up later; grab and install http://www.pygame.org/ftp/pygame-1.7.1release.win32-py2.5.exe ) |
| 03:56 | < Vornicus> | Okay, this is obviously a vast improvement. |
| 03:57 | | * ilovefire nods. |
| 03:57 | <@ilovefire> | And probably a good place to end--my parents are calling for me to turn off 'taht damned computer' and go to bed. |
| 03:57 | < Vornicus> | It is indeed. |
| 03:59 | < Vornicus> | Right now instead of a doubling of the size of the question giving a quadrupling of the amount of thinking needed, you're getting a bit under a tripling. |
| 04:00 | | * ilovefire nods |
| 04:02 | | ilovefire [~santros_v@209.82.191.ns-11321] has quit [Quit: I'm going to be dreaming about python tonight, probably. Hooray.] |
| 04:03 | < Vornicus> | Now, instead of four and a half hours, getting all the primes up to 1000000 takes about a minute. |
| 04:03 | < Vornicus> | bah. |
| 04:03 | <@ToxicFrog> | Tasty. |
| 04:03 | <@ToxicFrog> | Mmm, genetic algorithm/hill-climber/expert system hybrids. |
| 04:04 | < Vornicus> | But! We Can Do Better! |
| 04:04 | <@ToxicFrog> | I'm studying this jet engine optimization software. A carefully programmed expert system managed to do about twice as well as hand-optimization in 1/7th the time. |
| 04:05 | < Vornicus> | (we can reduce the number of numbers to test against by about 80% near 1M) |
| 04:05 | <@ToxicFrog> | Combining that with a genetic algorithm took slightly longer but did three times as well. |
| 04:05 | < Vornicus> | Expert systems and genetic algorithms are scarily powerful. |
| 04:06 | <@ToxicFrog> | Actually, the GA alone did three times as well as hand-optimization. |
| 04:06 | <@ToxicFrog> | But combining it with the expert system hill-climber reduced the time it took by a factor of two. |
| 04:09 | <@ToxicFrog> | As for expert systems...eh. |
| 04:09 | <@ToxicFrog> | When programmed right, they can apply rules much faster and more precisely than their programmers, and in more directions at once. |
| 04:09 | <@ToxicFrog> | But they're very easy to program wrong and can't really generate anything new. |
| 04:14 | | C_tiger [~c_wyz@Nightstar-5378.nycmny.east.verizon.net] has joined #code |
| 04:15 | < C_tiger> | All done? |
| 04:16 | < Vornicus> | Yeah, ILF had to go. |
| 04:16 | < Vornicus> | The performance improvement, once we got the boundary problems out of the way (which he solved pretty much himself), was Dramatic. |
| 04:17 | < Vornicus> | [Tue 22:56:08] ilovefire primes(1000) gives me 168 0.0 0.0 |
| 04:17 | < C_tiger> | Nice. |
| 04:17 | < Vornicus> | [Tue 22:56:26] ilovefire primes(10000) gives me 1229 0.0620000362396 6.20062368633e-006 |
| 04:18 | < Vornicus> | Compared to the old: |
| 04:18 | < Vornicus> | [Tue 21:21:38] ilovefire 168 0.0159997940063 1.60158098162e-005 |
| 04:18 | < Vornicus> | [Tue 21:23:32] ilovefire 1229 1.64100003242 0.000164116414884 |
| 04:19 | < C_tiger> | Did you talk about O(N), O(N^2) and O(sqrt(N))? |
| 04:20 | < Vornicus> | No. |
| 04:22 | | * McMartin has been working out a progression of problems to cover the basics of OO. |
| 04:22 | < C_tiger> | IIRC a lot of them involve weird sorts or something. |
| 04:22 | <@McMartin> | Weird sorts tend to be O(n log n) |
| 04:23 | <@McMartin> | http://www.stanford.edu/~mcmartin/misc/qix.txt is my proposed progression. The end result is, essentially, the Mystify screensaver. |
| 04:26 | < C_tiger> | I vaguely feel like I did a problem like this in 106A. |
| 04:26 | <@McMartin> | That would not surprise me. |
| 04:27 | <@McMartin> | It's the simplest algorithm that produces something cool-looking. |
| 04:29 | < C_tiger> | Vorn, out of curiosity, what are we covering next in your python 101 class? |
| 04:29 | < Vornicus> | Next time we'll actually be bringing list manipulations into the question. |
| 04:29 | < C_tiger> | (Not that I couldn't just learn python on my own, but this is bizarrely fun and plus it sticks better if I have to help teach it at the same time.) |
| 04:30 | < C_tiger> | Whoa, starting basic data structures? |
| 04:30 | < Vornicus> | Specifically, we're going to make it so we throw around a list of known primes, and instead of going through everything, we just go through the primes we already know. |
| 04:31 | < Vornicus> | ...damn. the legendre's constant thing doesn't work for low numbers. |
| 04:33 | < C_tiger> | Man, before you know it, he'll be ready to do the 106A final project. That's scary. |
| 04:33 | < Vornicus> | (you can approximate the number of primes below a number n using n/ln(n + 1.08366), and for higher n it approximates from above. |
| 04:33 | < C_tiger> | And this is useful for ilf because? |
| 04:34 | < C_tiger> | Or are you getting caught up in the beauty of numbers again? |
| 04:34 | < Vornicus> | Well, if it was high for low n, you could use it to quickly cut off then umber of primes you have to test on. |
| 04:34 | < Vornicus> | Instead of checking each one to see if it's above the square root. |
| 04:35 | < Vornicus> | But you can't, because it doesn't go above for a while. |
| 04:35 | < C_tiger> | Ah. |
| 04:35 | < C_tiger> | I thought we'd do it by sieving once we have data structures. |
| 04:36 | < C_tiger> | I'm trying to reason which method is more efficient. |
| 04:36 | < Vornicus> | Trial division, filtering our divisions down to primes. |
| 04:36 | < C_tiger> | But sieving doesn't have any math. |
| 04:36 | < Vornicus> | Yes it does. |
| 04:37 | < C_tiger> | Really? |
| 04:37 | < C_tiger> | And you only have to test up to sqrt(N) |
| 04:37 | <@ToxicFrog> | Sieving has multiplication. |
| 04:37 | <@ToxicFrog> | And requires O(n) space. |
| 04:37 | < C_tiger> | wait, it does? |
| 04:37 | < C_tiger> | Space, I know. |
| 04:37 | < C_tiger> | but multiplication? |
| 04:38 | < Vornicus> | Sieving has either multiplication or addition, and does a lot more of it than trial division does. |
| 04:38 | < C_tiger> | Yes, lots of addition. |
| 04:38 | < C_tiger> | Ok, so I guess addition isn't free like we've all been told. |
| 04:38 | < Vornicus> | Also you need to do one set union for each prime below sqrt(n), minus one. |
| 04:39 | <@ToxicFrog> | And trial division isn't even division - it's integer modulus. |
| 04:39 | < Vornicus> | And then a set difference between that and {2..n} |
| 04:39 | <@ToxicFrog> | Not sure if that's consistently faster, though. |
| 04:39 | < C_tiger> | TF, yeah, I was going to say the same thing. |
| 04:39 | < Vornicus> | They're the same hting. |
| 04:39 | < Vornicus> | Seiving is slower mainly because it has a lot of space manipulations. |
| 04:39 | <@ToxicFrog> | There's bound to be some architecture where they're different execution paths~ |
| 04:40 | < C_tiger> | Ok, yeah, I see your point about space manipulations. |
| 04:40 | < Vornicus> | Most archs do them in one path, because doing one gets you the other for free. |
| 04:40 | < Vornicus> | and I mean literally /for free/. |
| 04:40 | < C_tiger> | Yes. Magic like that. |
| 04:41 | <@ToxicFrog> | Well, doing div gets you mod; is the converse true? Is it possible to implement mod without div? |
| 04:41 | < C_tiger> | Actually, maybe. |
| 04:41 | < Vornicus> | Technically, yes. |
| 04:41 | <@ToxicFrog> | Is it faster? |
| 04:42 | < Vornicus> | Div you keep two parallel accumulators, one holding an upshifted denominator, and one holding 1 upshifted the same amount. |
| 04:42 | <@ToxicFrog> | (and remember, x86 is CISC, it has all kinds of wacky problem- and optimization- and compiler-specific paths and instructions and notations and constraints. I wouldn't put anything past those lunatics.) |
| 04:42 | < Vornicus> | And then you test, subtract your denominator from your numerator, and bitor the 1 with your quotient accumulator |
| 04:43 | < Vornicus> | well, you do the subtract and bitor if the test (denominator < numerator) succeeds. |
| 04:43 | < Vornicus> | And then you shift down, rinse, repeat. |
| 04:43 | < C_tiger> | Wait, there's no faster way to do binary division? Why did I think there was with some sort of shift-your digits approach. |
| 04:43 | < C_tiger> | Oh, maybe this was it. |
| 04:45 | < Vornicus> | This is the shift-your-digits approach. |
| 04:45 | < C_tiger> | Right. |
| 04:46 | < Vornicus> | I love the way to do multiplication with shift and add. |
| 04:46 | < C_tiger> | (don't mind me, we never covered this stuff in CS and damned if I was going to take any more complicated classes what with my major already killing me) |
| 04:47 | <@ToxicFrog> | (typically this stuff is covered in digital engineering or an equivalent CS elective) |
| 04:48 | < Vornicus> | it's just... shockingly graceful. |
| 04:48 | < C_tiger> | I assure you we didn't cover it in heat transfer or reactor design theory. |
| 04:48 | < C_tiger> | Which sadly I barely recall any of anyhow. |
| 04:49 | | mode/#code [+o Vornicus] by Vornicus |
| 04:49 | <@Vornicus> | http://rafb.net/p/nat2tX43.html |
| 04:51 | | * C_tiger tries to think of something equally geeky |
| 04:52 | < C_tiger> | Except I can no longer recall standardized solutions to Navier Stokes equations off the top of my head. |
| 04:52 | | Vornotron [~vorn@64.252.34.ns-3988] has joined #code |
| 04:53 | < C_tiger> | Oooh vornotron! |
| 04:53 | <@McMartin> | Whee, got the framework working |
| 04:53 | | Vornicus [~vorn@ServicesOp.Nightstar.Net] has quit [Ping Timeout] |
| 04:54 | | Vornotron is now known as Vornicus |
| 04:55 | < Vornicus> | So did my paste get through? |
| 04:55 | < C_tiger> | It did. |
| 04:55 | < C_tiger> | But you totally missed my reply... sadness. |
| 04:55 | < C_tiger> | I FAIL at outgeeking Vornotron. |
| 04:56 | < Vornicus> | I did miss your reply. |
| 04:57 | < C_tiger> | I fail. |
| 04:57 | < Vornicus> | I'm sorry. |
| 04:57 | < Vornicus> | No, actually, I'm not. But you see how it works. |
| 04:58 | < C_tiger> | I was going to say... |
| 05:03 | < Vornicus> | you were going to say...? |
| 05:03 | < C_tiger> | Are you really sorry? |
| 05:04 | < Vornicus> | :P |
| 05:13 | | mode/#code [+o Vornicus] by Vornicus |
| 05:13 | <@Vornicus> | http://rafb.net/p/fJ1VVn44.html <-- div and mod. If you really only want mod, you can get rid of bit and result and all the manipulations thereon. |
| 05:13 | <@Vornicus> | Actually no, you can't |
| 05:14 | <@Vornicus> | You can get rid of /result/, but you need bit because b might be even, and that would be bad. |
| 05:23 | | Vornicus is now known as Darius |
| 06:09 | | Darius is now known as Vornicus |
| 07:22 | <@McMartin> | Whee, it works! |
| 07:22 | <@McMartin> | http://www.stanford.edu/~mcmartin/misc/qixstart.png |
| 07:23 | <@Vornicus> | wootsauce. |
| 07:23 | <@ToxicFrog> | I may want to steal that lesson plan at some point. |
| 07:24 | <@McMartin> | Yeah, so I define a module "simpleanim" that has methods like line and fillbox |
| 07:24 | <@ToxicFrog> | Yeah, noticed. |
| 07:24 | <@McMartin> | And a class "App" that you subclass to handle frames and the like. |
| 07:24 | <@ToxicFrog> | I'd implement that for whatever language I was teaching, as appropriate. |
| 07:24 | | * McMartin also had one that imitated the EGA palette, but, well, reimplementing the BASIC graphics prims should really only go so far~ |
| 07:25 | <@McMartin> | simpleanim uses RGB args. |
| 07:25 | <@ToxicFrog> | As it should. |
| 07:25 | <@ToxicFrog> | Pallettized colorspaces can DIAF. |
| 07:25 | <@McMartin> | Well, I needed it for the CCA, since if you have up to 16 states, they're a good 16 colors to use. |
| 07:26 | <@ToxicFrog> | CCA? |
| 07:26 | | * Vornicus still likes his proposed color-scheme setup. |
| 07:26 | <@ToxicFrog> | Also, you can fake pallette with RGB, but not the converse~ |
| 07:26 | <@McMartin> | Cyclic Cellular Automaton. |
| 07:26 | <@Reiver> | Vorn: ? |
| 07:26 | <@McMartin> | Yeah. basicgraphics.py fakes it by indexing into the EGAPalette array. |
| 07:26 | | * Vornicus hunts it down. |
| 07:27 | <@Vornicus> | I don't think I ever properly wrote it up, but there's images around here somewhere. |
| 07:27 | <@ToxicFrog> | Using palettes I have no issue with, it's when the actual device colorspace is palettized - or, conversely, when the device is continuous but the software only lets you use a palette - that the pain sets in. |
| 07:27 | <@ToxicFrog> | Although I may be a bit more sensitive to this than usual because I've been hacking on System Shock graphics formats, which are all 8-bit palettized. |
| 07:28 | <@Vornicus> | okay, you start with: http://vorn.dyndns.org/~vorn/mooclone/sample_true.png and http://vorn.dyndns.org/~vorn/mooclone/sample_scheme.png |
| 07:28 | <@ToxicFrog> | And it has at least three different palettes plus the SVGA builtin, some of which are mutable. |
| 07:28 | <@Vornicus> | Where sample_true is your world colored with the three "scheme" colors as black. |
| 07:29 | <@Vornicus> | and sample_scheme is your world with everything else as black, and your three "scheme" colors as red, green, and blue. |
| 07:29 | <@Vornicus> | then you take sample_scheme, and replace red, green, and blue with your actual scheme colors, in this case grey, light blue, and black: http://vorn.dyndns.org/~vorn/mooclone/sample_colors.png |
| 07:30 | <@Vornicus> | and then you take /that/, and you add it to sample_true, to get: http://vorn.dyndns.org/~vorn/mooclone/sample_final.png |
| 07:32 | <@Vornicus> | (you can of course do this with more scheme colors, making more images to handle extra channels.) |
| 07:32 | <@Vornicus> | man, QIX. that game rocked. |
| 07:47 | | Vornotron [~vorn@64.252.37.ns-11767] has joined #code |
| 07:48 | | Vornicus [~vorn@ServicesOp.Nightstar.Net] has quit [Ping Timeout] |
| 07:56 | | Forj [~Forj@Nightstar-11713.ue.woosh.co.nz] has joined #code |
| 07:56 | | mode/#code [+o Forj] by ChanServ |
| 08:06 | | Vornotron is now known as Vornicus-Latens |
| 08:43 | | Vornicus-Latens [~vorn@Admin.Nightstar.Net] has quit [Ping Timeout] |
| 08:50 | | Vornicus-Latens [~vorn@64.252.37.ns-11767] has joined #code |
| 08:52 | | You're now known as TheWatcher |
| 09:34 | | AnnoDomini [AnnoDomini@Nightstar-29173.neoplus.adsl.tpnet.pl] has quit [Ping Timeout] |
| 09:41 | | AnnoDomini [AnnoDomini@Nightstar-29104.neoplus.adsl.tpnet.pl] has joined #Code |
| 09:41 | | mode/#code [+o AnnoDomini] by ChanServ |
| 09:43 | | gnolam [lenin@Nightstar-10613.8.5.253.static.se.wasadata.net] has joined #Code |
| 09:43 | | mode/#code [+o gnolam] by ChanServ |
| 10:11 | | Forj [~Forj@Nightstar-11713.ue.woosh.co.nz] has quit [Quit: Gone] |
| 11:02 | | Thaqui [~Thaqui@219.89.45.ns-13582] has left #code [Leaving] |
| 15:27 | | KarmaBot [~fark.off@87.72.35.ns-26506] has quit [Connection reset by peer] |
| 15:28 | | KarmaBot [~fark.off@87.72.35.ns-26506] has joined #Code |
| 15:28 | | mode/#code [+v KarmaBot] by ChanServ |
| 16:38 | | NSGuest-3333 is now known as Pi |
| 16:38 | | Pi is now known as NSGuest-3360 |
| 16:38 | | NSGuest-3360 [~sysop@67.183.91.ns-3660] has quit [Quit: There is no justice. There is only me.] |
| 16:39 | | Pi-2 [~sysop@67.183.91.ns-3660] has joined #code |
| 17:09 | | You're now known as TheWatcher[afk] |
| 17:21 | | gnolam is now known as Dieter |
| 17:57 | | Vornicus-Latens is now known as Vornicus |
| 17:58 | | Vornicus is now known as NSGuest-3361 |
| 17:59 | | NSGuest-3361 is now known as Vornicus |
| 18:07 | | AnnoDomini is now known as Lavos |
| 18:07 | | Lavos is now known as AnnoDomini |
| 18:28 | | You're now known as TheWatcher |
| 18:40 | | Xiphias [Ameroth@82.68.15.ns-4527] has joined #code |
| 19:43 | | Xiphias [Ameroth@82.68.15.ns-4527] has quit [Quit: I was never gone] |
| 20:36 | | Vornicus [~vorn@ServicesOp.Nightstar.Net] has quit [Quit: Leaving] |
| 20:39 | | Vornicus [~vorn@Admin.Nightstar.Net] has joined #code |
| 20:39 | | mode/#code [+o Vornicus] by ChanServ |
| 22:11 | | EvilDarkLord [~jjlehto3@130.233.228.ns-13022] has quit [Ping Timeout] |
| 22:12 | | EvilDarkLord [~jjlehto3@Nightstar-2194.vipunen.hut.fi] has joined #code |
| 22:13 | | EvilDarkLord is now known as NSGuest-3363 |
| 22:26 | | Dieter [lenin@Nightstar-10613.8.5.253.static.se.wasadata.net] has quit [Quit: Z?] |
| 22:31 | | ilovefire [~santros_v@209.82.191.ns-11321] has joined #code |
| 22:46 | <@Vornicus> | Ah, ilf |
| 22:46 | <@Vornicus> | I want you to do something for me, with the code you made yesterday. |
| 22:46 | <@Vornicus> | try running primes(1000000). it should take a minute or two. |
| 22:51 | < ilovefire> | allright. |
| 22:53 | <@Vornicus> | (also if you could repaste it, that would be nice) |
| 22:57 | <@Vornicus> | is it done? |
| 22:58 | < ilovefire> | Yes |
| 22:58 | < ilovefire> | 78498 22.5779998302 2.25780224083e-005 |
| 22:58 | <@Vornicus> | that's actually even faster than I thought it would be. |
| 22:58 | < C_tiger> | That's what I was going to say. |
| 22:59 | <@Vornicus> | (after you left we did some estimating, figured it would take about a minute) |
| 23:00 | < C_tiger> | Hey ilf, I have a math puzzle I was wondering if you could help code... |
| 23:00 | < ilovefire> | ... *whimper* |
| 23:00 | < C_tiger> | (Ok, I kid, I kid, before Vorn bites my head off...) |
| 23:00 | <@Vornicus> | If it's the "weigh" thing, dude, even /I/ don't know how to code that. |
| 23:00 | <@Vornicus> | Anyway. |
| 23:00 | < C_tiger> | It is. |
| 23:00 | < ilovefire> | Hmm, voice please? |
| 23:01 | | mode/#code [+ooooo Attilla C_tiger ilovefire NSGuest-3363 Pi-2] by Vornicus |
| 23:01 | <@C_tiger> | Woo! |
| 23:01 | <@Vornicus> | No, I won't give you voice. :P |
| 23:01 | <@ilovefire> | http://rafb.net/p/PoWy0c68.html here's the paste of the code for the primes thing. |
| 23:03 | <@Vornicus> | Anyway. |
| 23:04 | <@AnnoDomini> | import this |
| 23:04 | <@AnnoDomini> | ;p |
| 23:04 | | * ilovefire types in import the_force, chokes AD |
| 23:04 | <@Vornicus> | Remember how a couple days ago, I beat my head against the wall trying to show you something interesting about how you can skip numbers for testing? |
| 23:05 | <@C_tiger> | Don't we all :P |
| 23:05 | | * AnnoDomini has the choking function be done in Java, runs while it ponderously compiles and runs. |
| 23:06 | <@ilovefire> | Vorn: Err, sort of. |
| 23:06 | <@Vornicus> | So you remember the upshot of it? Specifically, what numbers we can't skip? |
| 23:07 | | * Reiver oooh, ooh! |
| 23:07 | <@Vornicus> | s/So/Do/ |
| 23:07 | | * ilovefire thinks. "umm, no... I, umm, don't think I do..." |
| 23:07 | | * Reiver has a guess! |
| 23:08 | <@Vornicus> | Well, okay. The upshot, in the end, was this: you have to test prime numbers. Everything else, once you get down to it, you don't have to test. |
| 23:08 | <@Reiver> | You can skip everything but primes-- damn you vorn |
| 23:08 | <@Vornicus> | (because if a number n is divisible by a composite number k, it's also divisible by a smaller prime number p) |
| 23:09 | <@Reiver> | (At least I'm right in the end.) |
| 23:09 | | Thaqui [~Thaqui@Nightstar-262.dialup.xtra.co.nz] has joined #code |
| 23:09 | | mode/#code [+o Thaqui] by ChanServ |
| 23:09 | | * ilovefire nods. "Ah right, I remmeber now." |
| 23:09 | <@Reiver> | eg: If you can divide it by 4 or 6, it can /also/ be divided by 2. |
| 23:09 | <@Reiver> | Anything divisable by 9 is also divisable by 3. |
| 23:09 | <@Reiver> | Etc. |
| 23:09 | <@Vornicus> | So, remember how many prime numbers there are below 1000? |
| 23:11 | <@ilovefire> | 168. |
| 23:11 | <@C_tiger> | Hey smart people in this room who want to help me figure out a really hard question for the heck of it... #math |
| 23:11 | <@Vornicus> | Right. So if we try to get the prime numbers below 1000000, how many numbers do we actually have to test against? |
| 23:12 | <@Vornicus> | (currently we test against 999 numbers, from 2 to 1000 inclusive) |
| 23:12 | <@C_tiger> | Hint, 1000000 is 1000^2 |
| 23:12 | <@Vornicus> | ** |
| 23:12 | <@Vornicus> | not ^ |
| 23:12 | <@C_tiger> | erm, right. |
| 23:12 | <@C_tiger> | I always forget that in this channel we use ** |
| 23:13 | <@Reiver> | !roll 1000**2 |
| 23:13 | <+KarmaBot> | [Reiver] 1000**2 = 0. |
| 23:13 | <@ilovefire> | 168 ** 2? which is, umm, 28224? |
| 23:13 | <@Reiver> | !roll 1000^2 |
| 23:13 | <+KarmaBot> | [Reiver] 1000^2 = 1000000. |
| 23:13 | <@Reiver> | Hah |
| 23:13 | <@Vornicus> | ilf: nope. |
| 23:13 | <@Vornicus> | But you're thinking in the right direction. |
| 23:14 | <@Vornicus> | (hint: you thought too far) |
| 23:15 | <@ilovefire> | Umm... |
| 23:16 | <@Vornicus> | We only need to test up to 1000, right |
| 23:17 | <@ilovefire> | Okay... |
| 23:17 | <@Vornicus> | And we only need to test prime numbers, right |
| 23:17 | <@Vornicus> | So, how many numbers do we have to test? |
| 23:17 | <@ilovefire> | oh, umm, 168? or am I not thinking it through enough this time? |
| 23:18 | <@Vornicus> | You've got it. |
| 23:18 | <@Vornicus> | Now, the only thing is... we need to know what numbers to test. |
| 23:18 | <@C_tiger> | So how do you find the prime numbers? |
| 23:18 | | * ilovefire nods. |
| 23:19 | <@ilovefire> | C: Well, my script with a bit of a modification could probably do such a thing. |
| 23:19 | <@Vornicus> | Figuring out if a number is prime before testing to see if it divides another number is pain incarnate. |
| 23:19 | <@Vornicus> | (and would indeed defeat the purpose) |
| 23:20 | <@C_tiger> | ilf, yes you can do that... but that's like doing the work over and over again. |
| 23:20 | <@Vornicus> | But... we're already generating these primes, right? |
| 23:20 | <@C_tiger> | Think about how many times you'd have to check if 5 were prime before proceeding? |
| 23:20 | <@ilovefire> | Right.... |
| 23:20 | <@Vornicus> | So.... why don't we collect them, and feed them back into the is_prime function? |
| 23:21 | <@C_tiger> | If you're doing the work, the least you can do is save it for later. |
| 23:21 | <@ilovefire> | Okay... how's that done? |
| 23:21 | <@Vornicus> | Well, what if instead of just incrementing your count of primes, you actually stored them in a list? |
| 23:23 | | KarmaBot [~fark.off@87.72.35.ns-26506] has quit [Ping Timeout] |
| 23:24 | | Kyrre [~Z@87.72.35.ns-26506] has quit [Connection reset by peer] |
| 23:24 | | KarmaBot [~fark.off@87.72.35.ns-26506] has joined #Code |
| 23:24 | | mode/#code [+v KarmaBot] by ChanServ |
| 23:24 | | NSGuest-3363 [~jjlehto3@Nightstar-2194.vipunen.hut.fi] has quit [Ping Timeout] |
| 23:24 | | Kyrre [~Z@87.72.35.ns-26506] has joined #Code |
| 23:25 | | EvilDarkLord [~jjlehto3@Nightstar-2194.vipunen.hut.fi] has joined #code |
| 23:25 | <@Vornicus> | What this means is you need to 1. make an empty list early on in your primes() function, and then 2. add things to the list as you go. |
| 23:26 | <@C_tiger> | Perhaps now is a good time to explain what a list is. |
| 23:26 | <@ilovefire> | well, I know the basics of what a list is, but umm |
| 23:26 | <@C_tiger> | And to thank your lucky stars you're not learning in C or C++ where you'd have to allocate memory. |
| 23:26 | | EvilDarkLord is now known as NSGuest-3365 |
| 23:26 | <@McMartin> | C: Well, C++ will do half of it for you now. |
| 23:26 | <@Vornicus> | I covered both of these operations earlier, in a lesson C missed. |
| 23:27 | <@C_tiger> | Ah. |
| 23:27 | <@ilovefire> | let me go find the referance .txt |
| 23:27 | <@C_tiger> | Man, I feel like I learned to program in the dark ages. |
| 23:27 | <@ilovefire> | okay, a blank list is just [], yes? |
| 23:27 | <@Vornicus> | Yep. |
| 23:27 | <@C_tiger> | Back when we manipulated blocks of memory line by line. |
| 23:28 | <@McMartin> | (Bah, you kids and your malloc. In my day we had to partition BSS by hand.) (You had a BSS segment? We used addresses directly!) |
| 23:28 | <@ilovefire> | OKay, now how do I get it to add primes to the blank list? list.append() I know, but... just try things until it works? |
| 23:29 | <@Vornicus> | Essentially. This one should be obvious: you're already doing something when you find a prime. |
| 23:29 | <@Vornicus> | (this is in primes()) |
| 23:30 | <@ilovefire> | (of course.) |
| 23:31 | <@Vornicus> | Oh, also, make sure you are putting your empty list declaration inside of primes(); outside makes a mess that I don't want to deal with right now. |
| 23:31 | | * ilovefire nods |
| 23:32 | <@Vornicus> | (there are situations where you want variables outside of anything, but this is not one of them!) |
| 23:33 | <@ilovefire> | Hmm. |
| 23:33 | <@ilovefire> | TypeError: descriptor 'append' requires a 'list' object but received a 'int' this means what? |
| 23:33 | <@Vornicus> | Show me the line of code that it's yelling about. |
| 23:34 | <@C_tiger> | Ok, no more step-by-step instructions, write it exactly as you think you should and we'll deal with errors and problems later. |
| 23:34 | <@ilovefire> | list.append(n) |
| 23:34 | <@Vornicus> | (I've never seen that one, which means he's done something wacky) |
| 23:34 | <@ilovefire> | after a line that's just [] |
| 23:34 | <@Vornicus> | Okay, that's not how you do it. |
| 23:34 | <@ilovefire> | Ah, goody. |
| 23:35 | <@Vornicus> | First, you need to assign the [] to a variable. |
| 23:35 | <@ilovefire> | ah. |
| 23:35 | <@Vornicus> | Second, you need to call the append /that lives inside the list/. |
| 23:35 | <@ilovefire> | Oh. |
| 23:35 | <@C_tiger> | [] is a blank list, but how does it know what that list is called? It doesn't have a variable name. |
| 23:36 | <@ilovefire> | so it should be something like c = []? |
| 23:36 | <@Vornicus> | Sure, but I'd call it something like known_primes |
| 23:36 | <@C_tiger> | Descriptive variable names (we talked about this the first day) |
| 23:36 | <@ilovefire> | Right, right... |
| 23:40 | <@Vornicus> | and when that's done, print len(known_primes) down at the end, instead of total |
| 23:40 | <@C_tiger> | Anyhow, back to the action: you have three steps you have to add: making the empty list, adding a prime to that list and using that list. |
| 23:40 | <@Vornicus> | (or whatever the hell you called it) |
| 23:40 | <@Vornicus> | But before we do that last bit, we want to make sure: is our list getting put together right? |
| 23:41 | <@Vornicus> | (and, once you do that, you can get rid of total entirely) |
| 23:41 | | You're now known as TheWatcher[T-2] |
| 23:41 | <@C_tiger> | Before you continue, I strongly suggest 1) checking you have the first two steps right and 2) reading through your code to figure out WHERE to put each of those things. |
| 23:42 | <@Vornicus> | C? |
| 23:42 | <@Vornicus> | Chill. |
| 23:42 | <@C_tiger> | ? |
| 23:43 | <@Vornicus> | Let him make his own mistakes. |
| 23:44 | <@ilovefire> | okay, umm, using this code, http://rafb.net/p/ol1fy795.html, when I tried primes(1000), it jsut printed out 168 0.0 0.0 as normal, so I think I've got a mistake somewhere. |
| 23:45 | <@Vornicus> | Nope, you got it right the first time. |
| 23:45 | <@C_tiger> | Yeah, it looks fine. |
| 23:46 | <@Vornicus> | I would remove the total = 0 line, because you're not using total any more, but it's just fine. |
| 23:47 | <@Vornicus> | Now that this is done, we have to figure out how we're going to tell is_prime about the known primes. |
| 23:47 | <@ilovefire> | oh, okay. So I actually got it right, and it only took me, what, ten or so tries before I stopped getting errors? |
| 23:47 | <@McMartin> | Syntax takes awhile to internalize. |
| 23:47 | <@Vornicus> | ilf: you're doing wonderfully then. |
| 23:48 | <@C_tiger> | Ok, so now you have to use it to improve your code. Where do you think you need to access the list for it to work? |
| 23:48 | <@McMartin> | Syntax is also the least important part, since the Hard Part is formulating the problem precisely enough to make it solvable. |
| 23:48 | <@C_tiger> | Right. |
| 23:48 | | * ilovefire hmms. |
| 23:48 | <@Vornicus> | why does "tell is_prime about the known primes" sound like you're sending a missionary to the function? |
| 23:49 | <@C_tiger> | Or a hitman. |
| 23:50 | <@Vornicus> | ...that works too, but I think the missionary is funnier. |
| 23:50 | <@McMartin> | That's throwing an exceptionally fatal error at them. |
| 23:50 | | * AnnoDomini giggles. |
| 23:50 | <@Vornicus> | heh. |
| 23:50 | | You're now known as TheWatcher[zZzZ] |
| 23:51 | | * AnnoDomini yays at bookbaker, an improved clone of Dan Cotter's original GBA ebook program. |
| 23:51 | <@Vornicus> | ilf: think out loud on this one, because hammering at the code won't help much until you see what it is you actually need to do. |
| 23:52 | <@C_tiger> | Yeah. |
| 23:52 | <@ilovefire> | well, obviously I need some way to referance the known_primes list to is_prime. |
| 23:52 | <@ilovefire> | err... in. |
| 23:52 | <@ilovefire> | not to. |
| 23:52 | <@Vornicus> | okay. |
| 23:52 | <@Vornicus> | What things does a function know about? |
| 23:52 | <@ilovefire> | the things inside the function. |
| 23:53 | <@C_tiger> | And? |
| 23:53 | <@Vornicus> | that's one thing. How do you tell a function about things it should know? |
| 23:54 | <@ToxicFrog> | AnnoDomini: GBA homebrew for book reading? Sweet. |
| 23:55 | <@ilovefire> | using true/false returns from other functions? |
| 23:56 | <@C_tiger> | Not quite. |
| 23:56 | <@Vornicus> | Well, that's how you tell a function that's running things. How about telling a function that you're about to run? |
| 23:57 | <@Vornicus> | Or, with more precision: how do you tell is_prime what number you want to check? |
| 23:58 | <@ilovefire> | with the imput for is_prime. |
| 23:58 | <@Vornicus> | All right. |
| 23:58 | <@Vornicus> | So, how do you tell is_prime about the numbers you already know are prime? |
| 23:58 | <@C_tiger> | So how do we tell is_prime about the known_primes list? |
| 23:58 | <@C_tiger> | Vorn types faster than I. |
| 23:59 | <@ilovefire> | make a second set of imput for the is_prime function? |
| --- Log closed Thu Dec 13 00:00:42 2007 |