==== Log for ##SICP on irc.freenode.net
==== February 8th, 2009 from 10:00 PM to 12:25 AM. All times are GMT-0200.
==== Logged by nicou. http://nicou.org.
==== Feel free to repost.

(10:00:59 PM) meanburrito920_: so, we are starting here in a min?
(10:01:16 PM) Madars-: so it seems :)
(10:01:27 PM) chrisconley: yeah sounds good
(10:01:28 PM) meanburrito920_: the channel seems rather empty
(10:01:54 PM) chrisconley: is someone up for logging and posting the meeting?
(10:01:56 PM) inimino: everybody is trying to finish the Miller-Rabin test
(10:02:07 PM) ***inimino only just finished
(10:02:21 PM) chrisconley: hehe, i was just getting to that
(10:02:33 PM) inimino: hehe
(10:03:25 PM) inimino: I can put up a log if nicou doesn't want to volunteer again
(10:03:43 PM) nicou: no, it's fine, I'm already logging, don't worry
(10:03:54 PM) inimino: ok, great
(10:03:54 PM) chrisconley: cool thanks nicou
(10:03:58 PM) nicou: noprob
(10:04:09 PM) chrisconley: so should we get started? 1.9 is it?
(10:04:11 PM) inimino: so, shall we start?
(10:04:11 PM) nicou: so, shall we dive into 1.9?
(10:04:17 PM) inimino: hehe
(10:04:20 PM) inimino: let's
(10:05:04 PM) nicou: well, the first procedure evolves into a recursive process: O(n) time, O(n) space; the second into an iterative constant-space, linear time process.
(10:05:57 PM) inimino: yeah
(10:06:01 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.9
(10:06:04 PM) inimino: that's what I had
(10:06:18 PM) nicou: yeah, me too.
(10:06:36 PM) nicou: any questions?
(10:06:42 PM) paul_hfx: mine: http://github.com/paulgb/sicp-excersises/blob/17bfd435066f9a5969368365cabb8135b4b7aa18/chapter-1/exercise-1.09.txt
(10:06:43 PM) rudybot: (notice) http://tinyurl.com/cqo4vj
(10:06:49 PM) inimino: seems like a long time ago, looking back at these
(10:06:56 PM) chrisconley: yeah does seem like ages ago
(10:06:57 PM) DuClare: Oh, since when did you get the bot here?
(10:07:03 PM) chrisconley: i got the same
(10:07:18 PM) nicou: yes, those are fine to me, too
(10:07:33 PM) nicou: I don't know who set up the bot, it's great
(10:08:01 PM) nicou: 1.10?
(10:08:02 PM) inimino: yeah, those look fine
(10:08:16 PM) inimino: yes
(10:08:28 PM) chrisconley: http://github.com/chrisconley/sicp-exercises/blob/b5e5b6d6ca4b5eb7ecd54e9b975042d08592c824/chapter1/ex1-10.ss
(10:08:30 PM) rudybot: (notice) http://tinyurl.com/azzrdu
(10:08:34 PM) paul_hfx: http://github.com/paulgb/sicp-excersises/blob/17bfd435066f9a5969368365cabb8135b4b7aa18/chapter-1/exercise-1.10.sc
(10:08:36 PM) rudybot: (notice) http://tinyurl.com/dxyyfm
(10:08:41 PM) inimino: ah yes, I didn't finish this one
(10:08:46 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.10
(10:08:52 PM) jcoglan: agreed: http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L7-35
(10:08:54 PM) rudybot: (notice) http://tinyurl.com/cd4hmg
(10:08:54 PM) chrisconley: 1024, 65536, 65536
(10:09:16 PM) inimino: part of my answer contains "uh, this is wrong" but I never got back to it
(10:09:46 PM) inimino: hm, chrisconley I have 1024, 256, 65536
(10:09:50 PM) nicou: want to check?
(10:09:53 PM) jcoglan: 1.10 was pretty laborious, though after the first part you can re-use results so it's not so much work
(10:10:07 PM) jcoglan: http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L7-35
(10:10:09 PM) rudybot: (notice) http://tinyurl.com/cd4hmg
(10:10:11 PM) chrisconley: yeah (a 3 3) condenses to (a 2 4)
(10:10:23 PM) chrisconley: or at least that's what i got
(10:10:45 PM) jcoglan: yes it does
(10:11:15 PM) nicou: yes, the exercise also asks to find an easy way to express A(0,x), A(1,x) and A(2,x), which would be: 2*x, 2^x, and 2^^x (tetration), respectively, right?
(10:11:26 PM) jcoglan: the other pattern is that (A 1 x) expands to [(A 0 ]{x times} 2)
(10:11:28 PM) inimino: hm, I seem to have missed something in there, oh well
(10:11:34 PM) jcoglan: if that notation makes sense
(10:11:50 PM) aamar: h(n) = 2↑↑n
(10:11:50 PM) inimino: nicou: I thought it was tetration, but that seemed wrong, possibly because of my earlier error.
(10:12:06 PM) chrisconley: i got 2*n, 2^n, and 2^n^2
(10:12:10 PM) paul_hfx: I got the same numbers chrisconley did
(10:12:20 PM) meanburrito920_: chrisconley: thats what i got
(10:12:28 PM) paul_hfx: http://github.com/paulgb/sicp-excersises/blob/17bfd435066f9a5969368365cabb8135b4b7aa18/chapter-1/exercise-1.10.txt
(10:12:30 PM) rudybot: (notice) http://tinyurl.com/b6v4xw
(10:12:59 PM) paul_hfx: hmm, I think my last answer is wrong
(10:12:59 PM) chrisconley: aamar, nicou: does 2^n^n = 2^^n?
(10:13:01 PM) inimino: I got 2↑↑n as well
(10:13:11 PM) nicou: paul_hfx: yes, that's what I have
(10:13:13 PM) inimino: though I doubted it
(10:13:17 PM) meanburrito920_: chrisconley: yes
(10:13:23 PM) chrisconley: cool thanks
(10:13:24 PM) inimino: chrisconley: no
(10:13:29 PM) chrisconley: uhh, hehe
(10:13:30 PM) meanburrito920_: ?
(10:13:53 PM) nicou: 2^^n = 2^2^2^2 ... ^2 (n times 2)
(10:14:00 PM) meanburrito920_: oh
(10:14:01 PM) inimino: right
(10:14:07 PM) meanburrito920_: whoops
(10:14:21 PM) jcoglan: @chrisconley could you clarify your notation? I figure 2^n^n == (2^n)^n -- what about the other expression?
(10:14:40 PM) jcoglan: no worries, @nicou answered
(10:14:41 PM) aamar: right, I had, 2^2^2... (n times)
(10:14:44 PM) nicou: this links seems to think it's tetration as well: http://sicp.org.ua/sicp/Exercise1-10
(10:14:47 PM) inimino: jcoglan: the other notation is tetration
(10:14:54 PM) aamar: Which is different than 2^n^n or 2^n^2
(10:15:08 PM) aamar: http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation
(10:15:17 PM) jcoglan: thanks
(10:15:31 PM) chrisconley: thanks
(10:15:47 PM) inimino: I thought h(n) was tetration, but I had gotten the wrong answer earlier so that threw me.
(10:16:48 PM) nicou: oh, and A(3,x) = 2^^^x, or something like supertetration, so I suppose it follows a regular sequence
(10:17:06 PM) meanburrito920_: on h i got 2^(2^(n-1)) for some reason...
(10:17:18 PM) inimino: yeah
(10:17:56 PM) jcoglan: yep, (2^2)^2 is not (A 3 3)
(10:18:36 PM) inimino: meanburrito920_: I got that for a while to when I had 256 for (A 2 4)
(10:18:50 PM) inimino: jcoglan: that should be 2^(2^2) right?
(10:19:05 PM) jcoglan: but (A 2 x) would seem to be (2^x)^x
(10:19:17 PM) nicou: meanburrito920_: A(2,x) = A( 1, A(2,x-1) ), right? and since we've already proven that A(1,y) = 2^y, it follows a recursive sequence into 2^^x
(10:19:20 PM) meanburrito920_: inimino: 2^(2^2) is mathematically the same as (2^2)^2
(10:19:46 PM) inimino: meanburrito920_: well, not in general
(10:19:49 PM) nicou: meanburrito920_: yes, but only for the number 2
(10:19:55 PM) jcoglan: @inimino I don't think so -- not in general
(10:20:34 PM) meanburrito920_: nicou: ah, thanks
(10:21:11 PM) nicou: yes, we only have to check the base case where we calculate A(2, 1) = 2
(10:21:17 PM) ***inimino feels mildly confused
(10:22:25 PM) nicou: inimino: look, A(2, x) = A(1, A(2,x-1)), right? and since A(1, y) = 2^y, assuming in that case y=A(2, x-1), we can see that A(2,x) = 2^A(2,x-1)
(10:23:15 PM) inimino: nicou: yes, I'm with you so far
(10:23:30 PM) nicou: so we just keep applying 2^ over and over, until we reach the base case A(2,1) = 2, and we are left with a sequence of x 2's, in the following manner: 2^2^2^2..., which is defined as tetration: 2^^x
(10:23:46 PM) inimino: yes, that's what I had
(10:24:10 PM) inimino: h n = (A 2 n) = (A 1 (A 2 n-1)) = (A 1 (A 1 ... (A 2 1))) = (2 ^ (2 ^ (2 ^ ... (2))...)) for N 2s
(10:24:21 PM) nicou: yes, exactly
(10:24:33 PM) inimino: ok
(10:24:38 PM) chrisconley: nicou: thanks, makes sense now
(10:24:38 PM) nicou: 1.11?
(10:24:46 PM) inimino: yeah :-)
(10:24:47 PM) aamar: very good explanation;
(10:24:49 PM) aamar: 1.11
(10:25:08 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.11
(10:25:14 PM) paul_hfx: http://github.com/paulgb/sicp-excersises/blob/17bfd435066f9a5969368365cabb8135b4b7aa18/chapter-1/exercise-1.11.sc
(10:25:16 PM) rudybot: (notice) http://tinyurl.com/brsned
(10:25:27 PM) chrisconley: http://github.com/chrisconley/sicp-exercises/blob/b5e5b6d6ca4b5eb7ecd54e9b975042d08592c824/chapter1/ex1-11.ss
(10:25:28 PM) rudybot: (notice) http://tinyurl.com/dh4bdq
(10:25:31 PM) meanburrito920_: do we have a pastebin for this channel?
(10:25:40 PM) jcoglan: http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L99-125
(10:25:42 PM) rudybot: (notice) http://tinyurl.com/dxavn7
(10:26:11 PM) inimino: meanburrito920_: I don't think so.
(10:26:11 PM) nicou: inimino: I have exactly that
(10:26:36 PM) meanburrito920_: this one seemed pretty basic, just cond the given info
(10:27:13 PM) nicou: and chrisconley did the same,but with the arguments in a different order
(10:27:35 PM) jcoglan: I found SICP's conventions for this sort of thing a bit 'inside-out' -- once you get that the parameter list is walking along the list one step at a time it's fine, but the parameter order in SICP obfuscates this a little
(10:28:01 PM) inimino: nicou: yes, they all look like we found similar solutions
(10:28:08 PM) nicou: jcoglan: what do you mean?
(10:28:20 PM) chrisconley: inimino: i don't get the multiplication you have in there
(10:28:28 PM) jcoglan: finding it hard to articulate...
(10:29:06 PM) jcoglan: from what I remember, I ended up writing params for iterative loops in the reverse order to that used in SICP examples
(10:29:39 PM) jcoglan: so my params go (counter, f[n-3], f[n-2], f[n-1])
(10:30:01 PM) inimino: chrisconley: that's the 2 and 3 coefficients from the formula in the problem, unless I erred
(10:30:07 PM) jcoglan: so it's easier to think of it as reading along an iterative list from left to right
(10:30:07 PM) chrisconley: inimino: nevermind, seems i can't read the problem correctly :)
(10:31:02 PM) inimino: chrisconley: yeah it looks like you left out the multiplications but otherwise it's the same solution
(10:31:25 PM) nicou: jcoglan: yes, I suppose either way makes sense, whichever works for you. I did what you did, but with the counter last
(10:31:27 PM) inimino: jcoglan: yes, I noticed that you put the counter first
(10:31:43 PM) chrisconley: inimino: yeah gotcha, thanks
(10:31:56 PM) jcoglan: @nicou exactly -- people read maths all sorts of different ways
(10:32:02 PM) meanburrito920_: 1.12?
(10:32:08 PM) nicou: yeah.
(10:32:14 PM) inimino: sure
(10:32:30 PM) chrisconley: http://github.com/chrisconley/sicp-exercises/blob/b5e5b6d6ca4b5eb7ecd54e9b975042d08592c824/chapter1/ex1-12.ss
(10:32:31 PM) rudybot: (notice) http://tinyurl.com/agqbto
(10:32:41 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.12
(10:32:47 PM) paul_hfx: http://github.com/paulgb/sicp-excersises/blob/a7edb1606d3048f9b51af6f1b149d2189969fc46/chapter-1/exercise-1.12.sc
(10:32:47 PM) jcoglan: http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L128-137
(10:32:48 PM) rudybot: (notice) http://tinyurl.com/al789t
(10:32:50 PM) rudybot: (notice) http://tinyurl.com/accfgj
(10:33:15 PM) jcoglan: pretty simple, though if anyone anyone has a tail-recursive solution I'd like to see it
(10:33:36 PM) paul_hfx: is github crawling for anyone else?
(10:33:52 PM) nicou: http://pastebin.com/d612bd723
(10:33:54 PM) meanburrito920_: yep
(10:33:58 PM) nicou: yes, github is slow right now
(10:34:10 PM) aamar: http://mibbit.com/pb/SZ39ta
(10:34:17 PM) jcoglan: yeah, a little
(10:34:38 PM) jcoglan: surely they can't be swamped by a Scheme discussion...? :-P
(10:35:04 PM) nicou: we're an overly active community :P
(10:35:05 PM) paul_hfx: jcoglan, any ideas on where to start with a tail-recursive version? I'm wondering if it's even possible with this problem
(10:35:06 PM) inimino: jcoglan: yours looks very like mine
(10:35:12 PM) jcoglan: never mind slow, I just got the sad little octocat
(10:35:22 PM) jcoglan: yep, all look similar
(10:35:29 PM) inimino: yeah, github is ridiculously slow for me too
(10:35:36 PM) jcoglan: I tried to figure out a tail-recursive version but couldn't
(10:35:43 PM) nicou: paul_hfx: you can calculate one value without calculating the rest
(10:36:03 PM) inimino: did anybody else think this problem was really under-specified?
(10:36:15 PM) jcoglan: the problem is two-dimensional so making a simple linear loop is tricky
(10:36:26 PM) inimino: it didn't say what the inputs to the function or the output would be
(10:36:32 PM) jcoglan: and I'm not familiar with Scheme enough yet to know if it's even possible
(10:36:47 PM) chrisconley: inimino: yeah i had a little trouble getting started
(10:36:54 PM) nicou: paul_hfx: this gives a clear sense of direction: http://en.wikipedia.org/wiki/Pascal%27s_rule , you calculate a couple of factorials and divide and have the iterative solution
(10:36:58 PM) meanburrito920_: inimino: yeah, i found that confusing also
(10:37:07 PM) jcoglan: true, tricky to know what the inputs ought to be
(10:37:07 PM) chrisconley: wasn't sure what exactly we were supposed to calculate
(10:37:25 PM) inimino: I had to look at someone else's solution to see what the function signature was
(10:37:38 PM) aamar: Most of us wrote pascal(x,y) to return a number -- seems reasonable
(10:37:38 PM) jcoglan: it's basically a two-dimensional grid, just a triangular region of a grid
(10:37:39 PM) nicou: inimino: yes, you're right, probably it's supposed to be that way, so that you get creative or something
(10:37:52 PM) jcoglan: all the solutions seem to take a line number and left-offset
(10:37:54 PM) paul_hfx: nicou: cool, thanks
(10:38:10 PM) inimino: my initial thought was to output the entire triangle, to some given depth.
(10:38:40 PM) inimino: (or if this were Haskell... just the entire triangle)
(10:38:47 PM) nicou: inimino: yes, that's possible as well, using pascal(x,y) as an internal proc
(10:39:00 PM) inimino: yeah
(10:39:01 PM) aamar: @inimino: yes, but the book hadn't yet covered "output"
(10:39:08 PM) nicou: inimino: you can in scheme too, just wait till you get to 3.5, infinite streams ;)
(10:39:09 PM) inimino: aamar: right :-)
(10:39:26 PM) inimino: nicou: hehe ok :-)
(10:39:34 PM) meanburrito920_: 1.13? that one killed me
(10:39:36 PM) nicou: 1.13?
(10:39:39 PM) inimino: yeah
(10:39:59 PM) jcoglan: heh. (aside: I've been playing with implementing a lazy-evaluation Scheme, makes lambda calculus and combinators do weird things)
(10:40:00 PM) inimino: oh, this one
(10:40:03 PM) chrisconley: meanburrito920: me too until you helped me out with it-hehe
(10:40:04 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.13
(10:40:09 PM) inimino: I loved this one
(10:40:09 PM) nicou: the hint really helps
(10:40:16 PM) inimino: yes
(10:40:21 PM) jcoglan: yes, the hint was a big help
(10:40:35 PM) paul_hfx: my 1.13 is kinda long, http://github.com/paulgb/sicp-excersises/blob/a7edb1606d3048f9b51af6f1b149d2189969fc46/chapter-1/exercise-1.13.txt
(10:40:36 PM) rudybot: (notice) http://tinyurl.com/cn4vht
(10:40:51 PM) chrisconley: http://github.com/chrisconley/sicp-exercises/blob/b5e5b6d6ca4b5eb7ecd54e9b975042d08592c824/chapter1/ex1-13.ss
(10:40:53 PM) rudybot: (notice) http://tinyurl.com/c5twcq
(10:40:55 PM) aamar: http://mibbit.com/pb/poqinf
(10:40:58 PM) jcoglan: afraid mine's in dead tree format
(10:41:07 PM) aamar: Definitely took longer than any other exercise for me
(10:41:24 PM) jcoglan: longer than 1.14?
(10:42:27 PM) jcoglan: for a while I couldn't tidy the algebra up, then I noticed to of the expressions you end up with *happen* to have the same numeric value so they cancel out
(10:42:28 PM) aamar: 1.14 was close
(10:43:38 PM) inimino: I think I took a sligtly different approach from paul_hfx
(10:44:18 PM) paul_hfx: yeah inimino, i'm reading over yours now, looks like the same idea but slightly different way of going about it
(10:44:37 PM) progmanos [n=rashad@c-24-30-46-193.hsd1.ga.comcast.net] entered the room.
(10:44:44 PM) progmanos: hello
(10:45:12 PM) nicou: yes, my solution was similar to yours, but I had to clear it up a bit
(10:45:18 PM) paul_hfx: inimino, I prefer your way of doing it to mine, the abs(...) < 0.5 felt klunky
(10:45:53 PM) nicou: paul_hfx: yeah, I went that way first, then noticed that using phi should clear that mess
(10:46:00 PM) inimino: cool
(10:46:15 PM) jcoglan: I was a little confused by the instruction to show it's the "closest" integer
(10:46:29 PM) jcoglan: if you follow their hint it works out exactly using induction
(10:46:37 PM) nicou: jcoglan: exactly, actually it IS that integer, it confused me too
(10:46:55 PM) jcoglan: not just me then
(10:47:04 PM) paul_hfx: nicou, how do you mean it IS that integer?
(10:47:18 PM) paul_hfx: the result is a real number, right?
(10:47:23 PM) meanburrito920_: paul_hfx: it doesnt need rounding or such
(10:47:25 PM) nicou: paul_hfx: sorry, I mean the hint part, using the other value
(10:47:36 PM) jcoglan: no, Fib(n) is an integer for all n
(10:47:42 PM) paul_hfx: oh, i forgot what the hint is
(10:47:53 PM) inimino: it's only not the integer once you drop the ψ^n part
(10:48:25 PM) paul_hfx: yes, i misunderstood you
(10:48:40 PM) nicou: inimino: yes, and that converges to 0 for all positive integers
(10:48:49 PM) inimino: right
(10:49:19 PM) nicou: 1.14?
(10:49:36 PM) inimino: ok
(10:49:41 PM) aamar: ok
(10:49:52 PM) jcoglan: this was evil... http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L140-224
(10:49:54 PM) rudybot: (notice) http://tinyurl.com/bh3asf
(10:50:00 PM) meanburrito920_: it got HUGE
(10:50:28 PM) inimino: mine is split into two parts
(10:50:41 PM) inimino: the diagram: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.14.A
(10:51:24 PM) inimino: and the other part which $#!% Apache is serving with some wrong content-type...
(10:51:36 PM) inimino: one moment...
(10:51:40 PM) paul_hfx: mine doesn't look like the others, I might have misread the problem.. http://github.com/paulgb/sicp-excersises/blob/a7edb1606d3048f9b51af6f1b149d2189969fc46/chapter-1/exercise-1.14.png
(10:51:41 PM) rudybot: (notice) http://tinyurl.com/b6pa6q
(10:52:19 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.14.B.txt
(10:53:13 PM) paul_hfx: (the nodes in mine are the number of cents left)
(10:53:41 PM) inimino: paul_hfx: I think your's is right, but very simplified
(10:53:42 PM) nicou: this might be useful: http://sicp.org.ua/sicp/Exercise1-14?action=AttachFile&do=view&target=countingcoins.pdf
(10:53:44 PM) rudybot: (notice) http://tinyurl.com/cljlwb
(10:54:02 PM) nicou: yes, paul_hfx's seems to be the same
(10:54:24 PM) meanburrito920_: paul_hfx: yours just has the branches consolidated which are traversed multiple times
(10:55:12 PM) aamar: What did people get for time/space?
(10:55:41 PM) inimino: O(n^5) time
(10:55:46 PM) inimino: in O(n) space
(10:55:48 PM) inimino: for me
(10:55:56 PM) jcoglan: from my tree, looks like O(n) space
(10:56:15 PM) nicou: O(n^5), for 5 types of coins
(10:56:15 PM) inimino: that's in that 1.14.B.txt file but there's a bunch of my rambling thoughts in there also
(10:56:22 PM) jcoglan: possibly exponential time but I'm not sure
(10:56:25 PM) aamar: Agreed, space = O(n) -- linear
(10:56:38 PM) nicou: yeah, exponential for the number of coins
(10:56:44 PM) jcoglan: in time?
(10:56:48 PM) inimino: the time was a challenge
(10:57:01 PM) inimino: but someone gave me a hint to start with just pennies, and then it was easy
(10:57:20 PM) aamar: Time was difficult;
(10:57:25 PM) jcoglan: I'm mostly using intuition based on the look of the tree -- not sure how so prove complexity
(10:57:32 PM) inimino: for some reason the idea of reducing the problem from that end hadn't occurred to me.
(10:57:33 PM) aamar: Any disagreements with O(n^5) ?
(10:58:11 PM) nicou: nope, looks fine to me
(10:58:14 PM) aamar: I couldn't come up with a way to prove it either; will have to review @nicou's pdf later
(10:58:19 PM) jcoglan: could be polynomial
(10:58:31 PM) jcoglan: anyone really know their complexity proofs?
(10:58:38 PM) inimino: I didn't prove it but I believe I can
(10:59:24 PM) nicou: it gets hard apparently
(10:59:33 PM) inimino: I convinced myself of my answer with what seems like the sketch of a proof
(10:59:46 PM) inimino: I found this one hard, yeah
(11:00:37 PM) inimino: jcoglan: no, I don't feel like I really know how to do these kinds of things
(11:00:51 PM) meanburrito920_: yeah, I definitely had a lot more trouble with this section than the last
(11:01:20 PM) inimino: yes, it definitely is ramping up
(11:01:25 PM) inimino: feel the learn :-)
(11:01:30 PM) nicou: but it gets easier in the following sections
(11:01:37 PM) inimino: oh, ok
(11:01:47 PM) jcoglan: anyone got any reading material on complexity analysis? I don't think SICP really gave you enough to answer some of these questions without prior experience
(11:01:48 PM) inimino: who else has read ahead?
(11:01:54 PM) inimino: (I haven't)
(11:02:02 PM) jcoglan: I'm part-way through 1.3
(11:02:10 PM) inimino: jcoglan: there are some good Wikipedia articles
(11:02:11 PM) nicou: I'm in 3.4
(11:02:20 PM) chrisconley: that's good to hear it gets a bit easier
(11:02:30 PM) chrisconley: this section took me a while as well
(11:02:38 PM) inimino: yeah, me too
(11:02:54 PM) jcoglan: 1.2 is extremely mathsy, which I'm rusty at
(11:03:01 PM) inimino: I also didn't enjoy some of the ones about real-world performance
(11:03:18 PM) nicou: jcoglan: you're not going to enjoy matrix operations in 3.3
(11:03:26 PM) inimino: so I'm hoping there's not too much of that
(11:03:35 PM) meanburrito920_: nicou: ouch
(11:03:52 PM) nicou: inimino: just the section with the (runtime) procedure, as far as I know
(11:03:58 PM) nicou: so, 1.15?
(11:04:03 PM) inimino: (I mean the ones that require measuring run-time, not the complexity proofs)
(11:04:11 PM) inimino: nicou: ok, that's great
(11:04:16 PM) jcoglan: matrices I'm probably more familiar with
(11:04:16 PM) inimino: yeah, 1.15
(11:04:31 PM) nicou: so, it's logarithmic time and space
(11:04:32 PM) jcoglan: (my background is in physics)
(11:04:45 PM) paul_hfx: my 1.15: http://github.com/paulgb/sicp-excersises/raw/a7edb1606d3048f9b51af6f1b149d2189969fc46/chapter-1/exercise-1.15.txt
(11:04:46 PM) rudybot: (notice) http://tinyurl.com/cn2eq7
(11:04:50 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.15
(11:05:02 PM) nicou: jcoglan: then you're not going to like the derivative examples? I dunno
(11:05:35 PM) jcoglan: @nicou that sounds like fun -- I've tried using JavaScript to do calculus before
(11:05:43 PM) paul_hfx: inimino: looks good to me
(11:05:50 PM) aamar: http://mibbit.com/pb/YzXMV6
(11:05:54 PM) chrisconley: are you guys doing anything fancy to come up with orders of growth or just looking at a few cases?
(11:05:57 PM) jcoglan: it's just the comp-sci specific stuff I've not been exposed to before
(11:06:05 PM) meanburrito920_: how did you get b?
(11:06:13 PM) inimino: paul_hfx: yeah, yours looks right also
(11:06:24 PM) nicou: the thing that confused me a bit is that the in the mathematical description, sine is applied twice for each sine computation, so I thought it was raising the logarithmic space to constant space, but since the sine gets computed only once and then passed on to the p procedure, it's still logarithmic time
(11:06:47 PM) aamar: I'm just looking at several cases, then doing some reasoning about the problem after the fact to confirm it.
(11:06:53 PM) inimino: chrisconley: mostly trying to find a rule
(11:07:32 PM) inimino: I don't think I looked at more that one case on any of these, but I reasoned my way through some of the branches like on the count-change problem
(11:07:42 PM) nicou: meanburrito920_: the key is that the input size (in this case, x) for the sine procedure gets reduced by a constant (3) until it reaches a small enough number, so it's logarithmic
(11:07:57 PM) meanburrito920_: ah
(11:08:34 PM) nicou: if it was subtracted a constant, it would be linear
(11:08:34 PM) chrisconley: nicou: so if it was only reduced by 1 each time, it'd be linear?
(11:08:50 PM) chrisconley: by 1 or a constant, thanks
(11:09:10 PM) nicou: yeah, that sort of rule is very intuitive and really helps
(11:09:11 PM) paul_hfx: chrisconley: nothing fancy, but n has to increase by a factor of 3 in order to add another step, so the number of steps is proportional to log base 3 of n
(11:09:32 PM) nicou: paul_hfx: exactly
(11:09:40 PM) chrisconley: cool, thanks guys
(11:09:41 PM) inimino: paul_hfx: yes, that's a great way to put it
(11:10:07 PM) nicou: 1.16?
(11:10:09 PM) inimino: the "what has to happen to the input to add another step" is a really helpful way to look at these
(11:10:18 PM) inimino: ok, 1.16
(11:10:34 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.16
(11:10:39 PM) paul_hfx: http://github.com/paulgb/sicp-excersises/raw/a7edb1606d3048f9b51af6f1b149d2189969fc46/chapter-1/exercise-1.16.ss
(11:10:40 PM) rudybot: (notice) http://tinyurl.com/co6rfw
(11:10:47 PM) jcoglan: http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L227-244
(11:10:49 PM) rudybot: (notice) http://tinyurl.com/c4aamq
(11:11:09 PM) meanburrito920_: http://pastebin.com/m7e976b93
(11:11:29 PM) nicou: http://pastebin.com/m5cfd45d
(11:11:34 PM) chrisconley: http://pastie.org/383583
(11:11:36 PM) jcoglan: would have helped me if 1.17 came first, I found it easier to understand
(11:11:38 PM) aamar: http://mibbit.com/pb/F6JidW
(11:11:51 PM) chrisconley: 1.16 and 1.17 took me a good while
(11:12:19 PM) paul_hfx: jcoglan: I thought that too when I first saw 1.17, but I ended up finding it a bit harder
(11:12:38 PM) nicou: those all look similar
(11:12:57 PM) jcoglan: 1.17 is easier to see the constant: you double one arg and halve the other
(11:13:09 PM) meanburrito920_: 1.17 was definitely easier after 1.16
(11:13:13 PM) jcoglan: exponentiation using squaring is equivalent but not so obvious
(11:13:29 PM) meanburrito920_: 1.16 took a while
(11:13:30 PM) inimino: yeah, these all look good
(11:13:38 PM) meanburrito920_: 1.17?
(11:13:45 PM) nicou: ok
(11:14:03 PM) jcoglan: http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L247-266
(11:14:05 PM) rudybot: (notice) http://tinyurl.com/dd6qpy
(11:14:11 PM) meanburrito920_: http://pastebin.com/m317bce2f
(11:14:15 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.17
(11:14:19 PM) paul_hfx: http://github.com/paulgb/sicp-excersises/blob/a7edb1606d3048f9b51af6f1b149d2189969fc46/chapter-1/exercise-1.17.ss
(11:14:20 PM) rudybot: (notice) http://tinyurl.com/chxuoy
(11:14:26 PM) chrisconley: http://pastie.org/383584
(11:14:45 PM) meanburrito920_: i didnt use half at all
(11:14:47 PM) aamar: http://mibbit.com/pb/BMZIRD
(11:14:50 PM) jcoglan: thought it was interesting that (double) (halve) and (even?) are trivial low-level machine operations
(11:15:06 PM) jcoglan: indicates how you might implement arithmetic on bit registers
(11:15:39 PM) meanburrito920_: oh duh, i did use halve, but i didnt write a function for it
(11:15:41 PM) inimino: meanburrito920_: you used (/ _ 2)
(11:15:44 PM) aamar: @meanburrito920_: I think the premise would be that both multiplication nor division are unavailable
(11:15:53 PM) inimino: yeah
(11:16:04 PM) aamar: so you could just switch out that (/ _ 2) for (halve _)
(11:16:10 PM) meanburrito920_: yeah
(11:16:10 PM) inimino: jcoglan: interesting point
(11:16:39 PM) meanburrito920_: definitely
(11:16:44 PM) jcoglan: double = bit-shift left, halve = bit-shift right, even? = is the last bit zero?
(11:17:19 PM) inimino: looks like some others had a * or / slip in
(11:17:45 PM) meanburrito920_: jcoglan: yep
(11:17:55 PM) inimino: but everyone got the same solution apart from different notations
(11:17:56 PM) chrisconley: inimino: oh yeah, just noticed i did
(11:19:05 PM) inimino: 1.18?
(11:19:36 PM) inimino: any questions on 1.17?
(11:20:01 PM) meanburrito920_: 1.18: http://pastebin.com/m795aff0f
(11:20:22 PM) nicou: yeah, I found the key to solve 1.18 was to keep the invariant quantity (b*counter + a) on every step, until counter=0, so we return a
(11:20:41 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.18
(11:20:44 PM) paul_hfx: I accidentally solved 1.8 in 1.7, so I'll post it here again http://github.com/paulgb/sicp-excersises/blob/a7edb1606d3048f9b51af6f1b149d2189969fc46/chapter-1/exercise-1.17.ss
(11:20:48 PM) chrisconley: http://pastie.org/383588
(11:20:49 PM) rudybot: (notice) http://tinyurl.com/chxuoy
(11:20:57 PM) inimino: hehe, paul
(11:20:59 PM) jcoglan: http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L269-281
(11:21:01 PM) rudybot: (notice) http://tinyurl.com/ccu2az
(11:21:06 PM) inimino: overachiever :P
(11:21:14 PM) aamar: nicou: agreed
(11:21:15 PM) jcoglan: just a combination of 1.16 and 1.17 patterns
(11:22:05 PM) meanburrito920_: paul_hfx: whats with the brackets?
(11:22:13 PM) inimino: these all look very similar
(11:22:22 PM) nicou: yeah, all are fine to me
(11:22:36 PM) paul_hfx: it's a habit I picked up from a CS course that I haven't been able to break, they are just the same a regular ()
(11:22:45 PM) paul_hfx: (kinda..)
(11:22:55 PM) jcoglan: in R6RS [] == ()
(11:23:08 PM) jcoglan: in PLT they work like that anyway
(11:23:10 PM) nicou: paul_hfx: I particulary find them ugly, they wreck my parenthesis style :P
(11:23:26 PM) jcoglan: I find them useful for (let) and macros
(11:23:33 PM) paul_hfx: in PTL scheme, the interpreter only lets you use them in certain places, iirc (?)
(11:24:05 PM) inimino: only special forms, maybe?
(11:24:07 PM) jcoglan: really? odd. R6RS says to treat them as ()
(11:24:16 PM) paul_hfx: nicou: I know what you mean, it seems unlisplike, but I've been conditioned to not be able to stand conds without []
(11:24:19 PM) X-Scale left the room.
(11:24:29 PM) inimino: well they do reduce visual ambiguity
(11:24:30 PM) meanburrito920_: r6rs is not implemented on PLT yet
(11:24:35 PM) meanburrito920_: its still r5rs
(11:24:48 PM) nicou: paul_hfx: yeah, they are more readable, I have to admit
(11:25:08 PM) X-Scale [i=email@89-180-76-121.net.novis.pt] entered the room.
(11:25:23 PM) jcoglan: I thought there was a module for R6RS? anyway, I just typed "[+ 3 4]" into mzscheme and got 7
(11:26:03 PM) paul_hfx: jcoglan, hmm, you're right, maybe it's just a drscheme thing
(11:26:13 PM) jcoglan: could be -- I've not tried it
(11:26:39 PM) paul_hfx: heh, drscheme won't even let me type [ unless it's in a cond
(11:26:45 PM) paul_hfx: it replaces it with ( automatically
(11:27:01 PM) nicou: mm, which module are you using? r5rs?
(11:27:27 PM) paul_hfx: nicou, I'm using Pretty Big, but I think the drscheme behaviour is universal to all modules (maybe?)
(11:28:19 PM) nicou: paul_hfx: dunno, I stick to r5rs to avoid problems
(11:28:42 PM) jcoglan: man I can't stand history-less REPLs </rant>
(11:28:43 PM) paul_hfx: nicou, which interpreter? drscheme?
(11:29:00 PM) paul_hfx: jcoglan: which one?
(11:29:19 PM) nicou: paul_hfx: yeah, I always use drscheme but needed to use the CLI mzscheme some times
(11:29:33 PM) jcoglan: drscheme seems to have no up-arrow facility (though I've literally just fired it up for the first time)
(11:29:46 PM) paul_hfx: jcoglan: ctrl+up, although sometimes it seems to break
(11:29:56 PM) jcoglan: mzscheme has no history and doesn't even allow left/right cursor movement within an expression
(11:30:13 PM) nicou: jcoglan: AND it doesn't indent automatically
(11:30:23 PM) jcoglan: ah -- am slightly happier
(11:30:29 PM) jcoglan: drscheme looks quite nice
(11:30:30 PM) inimino: I used MIT/GNU Scheme, but for the problems until 1.21 I haven't used any interpreter
(11:30:51 PM) inimino: I'm guessing it will become more unavoidable as we go on
(11:31:02 PM) meanburrito920_: jcoglan: you know what that means right? it means its time to write your own implementation
(11:31:16 PM) jcoglan: I'm writing my own Scheme, need to improve REPL indentation for sure
(11:31:28 PM) inimino: hehe
(11:31:34 PM) inimino: jcoglan: in 48 hours?
(11:31:39 PM) jcoglan: not quite
(11:31:43 PM) meanburrito920_: jcoglan: I wrote my own CL implementation, but it needs work
(11:31:56 PM) jcoglan: about a month so far
(11:32:00 PM) meanburrito920_: same
(11:32:09 PM) nicou: fuck, pidgin just crashed! :P
(11:32:12 PM) inimino: wb nicou, remind me to send you the logs
(11:32:19 PM) nicou: which logs?
(11:32:28 PM) inimino: for the time you missed
(11:32:36 PM) meanburrito920_: nicou: how about upgrading to a 'real' irc client
(11:32:39 PM) meanburrito920_: :-)
(11:32:40 PM) nicou: oh, thank you, want my email?
(11:32:48 PM) inimino: sure
(11:33:01 PM) jcoglan: is this the point where *my* pidgin crashes too?
(11:33:05 PM) nicou: meanburrito920_: I'm used to pidgin, I could try xchat or something I suppose
(11:33:09 PM) meanburrito920_: xchat
(11:33:15 PM) meanburrito920_: is great
(11:33:17 PM) inimino: I reccomend weechat, FWIW
(11:33:24 PM) nicou: nicou at the best free email service dot com
(11:33:31 PM) nicou: nicou92 at the best free email service dot com, i mean
(11:33:33 PM) meanburrito920_: i used to use pidgin, but ever since i moved to xchat i havent looked back
(11:33:46 PM) inimino: and if you run it on a VPS over GNU screen you don't ever have to log out :-)
(11:33:49 PM) nicou: ok, I'll give it a try when we're done tonight
(11:33:55 PM) meanburrito920_: inimino: exactly
(11:34:10 PM) paul_hfx: i have to go, but before I do, does anyone have their p' and q' functions handy for ex1.19? i couldn't get mine to work
(11:34:23 PM) paul_hfx: here's what i had: http://github.com/paulgb/sicp-excersises/raw/a7edb1606d3048f9b51af6f1b149d2189969fc46/chapter-1/exercise-1.19.ss
(11:34:25 PM) nicou: I still a VPS though :/
(11:34:26 PM) rudybot: (notice) http://tinyurl.com/b9csss
(11:34:27 PM) meanburrito920_: inimino: do you run arch or something?
(11:34:28 PM) chrisconley: http://pastie.org/383590
(11:34:42 PM) meanburrito920_: I never got 1.19
(11:34:45 PM) inimino: meanburrito920_: Debian
(11:34:47 PM) chrisconley: (+ (sqr p) (sqr q))
(11:34:53 PM) chrisconley: (+ (* 2 p q) (sqr q))
(11:34:53 PM) inimino: paul_hfx: here's mine:
(11:34:57 PM) chrisconley: for p and q
(11:35:09 PM) paul_hfx: chrisconley, hmm, that's what I got, wonder why mine didn't work
(11:35:14 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.19
(11:35:21 PM) jcoglan: http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L284-330
(11:35:22 PM) rudybot: (notice) http://tinyurl.com/ag2r6n
(11:35:25 PM) inimino: I didn't test mine, no idea if it works
(11:35:28 PM) inimino: (or runs)
(11:35:36 PM) nicou: paul_hfx: T(T(p,q)) = T(p^2 + q^2, 2pq + q^2)
(11:35:46 PM) meanburrito920_: i looked up the solution, but I don't understand the math behind it
(11:36:41 PM) chrisconley: i finally found it's easier to solve bp' + aq' first
(11:36:51 PM) inimino:  think mine explains the math reasonably well, assuming I actually got everything right
(11:37:04 PM) chrisconley: subsutitute bq+ aq + ap for a
(11:37:16 PM) chrisconley: and bp+ aq for b
(11:37:24 PM) nicou: and reapply
(11:37:34 PM) paul_hfx: weird, at least my p' and q' look correct, must be some little detail in my code
(11:37:42 PM) chrisconley: yeah inimino's explanation looks pretty good
(11:37:46 PM) aamar: http://mibbit.com/pb/zpqNvm
(11:37:53 PM) aamar: Mine includes a derivation of p', q' as well
(11:38:11 PM) meanburrito920_: oh duh, just simple algebra
(11:38:27 PM) nicou: yeah, I did whan inimino did, but it took me ages, it's simple but long
(11:38:33 PM) paul_hfx: ah, found it... i copied the code from the example wrong (p instead of q)
(11:38:38 PM) chrisconley: took me forever too
(11:39:44 PM) nicou: 1.20?
(11:39:55 PM) paul_hfx: i have to go, but that's as far as I got this week anyway :-|, thanks to everyone though, see you next meeting
(11:40:04 PM) paul_hfx left the room (quit: "Ex-Chat").
(11:40:19 PM) jcoglan: was uncertain about 1.20
(11:40:30 PM) jcoglan: my guesses: http://github.com/jcoglan/heist/blob/36c47a7f5a1164f3f6fd064ab37917ec0abc9624/sicp/section-1-2.scm#L333-374
(11:40:32 PM) rudybot: (notice) http://tinyurl.com/cgnm74
(11:40:57 PM) nicou: jcoglan: I got the same
(11:41:38 PM) jcoglan: phew
(11:42:16 PM) nicou: and the big difference lies in that you don't have to recompute a value that's passed as an argument doesn't need to be recomputed, in applicative order
(11:42:55 PM) nicou: I screwed up the sentence there :P
(11:43:02 PM) aamar: http://mibbit.com/pb/h1ZD5L
(11:43:08 PM) aamar: I have the same as jcoglan
(11:43:11 PM) inimino: are we on 1.20 now?
(11:43:13 PM) inimino: ah
(11:43:24 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.20
(11:44:07 PM) aamar: Hm. that's 19 vs. 18.
(11:44:11 PM) aamar: Counting problem?
(11:44:28 PM) jcoglan: I'm going to take off, it's late here. where will the logs be posted?
(11:44:49 PM) inimino: yeah I somehow got 19, but other than that it looks the same
(11:45:05 PM) nicou: jcoglan: as soon as this is over: http://nicou.org/files/sicp-log-0802.txt
(11:45:49 PM) inimino: yeah it's the 7, which I miscounted as 8
(11:46:17 PM) nicou: oh, so we agree on 18 and 4.
(11:46:24 PM) inimino: everyone else's looks correct
(11:46:37 PM) jcoglan: @nicou thanks
(11:46:45 PM) nicou: np
(11:46:58 PM) nicou: ok, 1.21?
(11:47:00 PM) inimino: 1.21, then?
(11:47:02 PM) inimino: ok
(11:47:12 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.21
(11:47:23 PM) chrisconley: that's what i got too
(11:47:28 PM) jcoglan left the room.
(11:47:30 PM) nicou: yeah,that's fine
(11:47:32 PM) inimino: pretty short answer for once
(11:47:34 PM) inimino: ok
(11:47:48 PM) nicou: 1.22?
(11:47:50 PM) inimino: 1.22?
(11:48:01 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.22
(11:48:19 PM) inimino: ah, yes
(11:48:40 PM) inimino: I used #t and #f but I don't think those have really been introduced
(11:49:16 PM) inimino: I wasn't sure what the book was on about since the provided functions didn't return a value
(11:49:35 PM) aamar: You can also use "true" and "false"
(11:49:45 PM) nicou: they weren't necessary, the #f would've been returned anyway because there is no alternate clause, and report-prime returns a value that's implementation-dependent
(11:49:47 PM) inimino: aamar: ah
(11:50:07 PM) chrisconley: http://pastie.org/383604
(11:50:13 PM) aamar: But same problem as you, the text here wasn't entirely clear on what they wanted us to do.
(11:50:18 PM) inimino: nicou: I see
(11:50:42 PM) aamar: http://mibbit.com/pb/ZvHV2p
(11:50:55 PM) inimino: nicou: so (if (report-prime) would have worked?
(11:51:31 PM) nicou: inimino: let's see, report-prime would return the value of (display elapsed-time)
(11:51:56 PM) inimino: which is truthy?
(11:52:30 PM) nicou: inimino: which is implementation dependent, I suppose, but since you're not using the return value of report-prime for anything, you don't need to make sure it returns something adequate
(11:52:48 PM) inimino: sorry, I meant (if (start-prime-test
(11:53:36 PM) inimino: hm, all my function names now look wrong
(11:53:48 PM) ***inimino isn't sure how his solution ever ran anymore
(11:53:52 PM) nicou: yeah, start-prime-test would evaluate (report-prime (- (process-time-clock) start-time)) if true, and return false when false, in lack of an alternate clause
(11:54:06 PM) inimino: ok
(11:54:41 PM) inimino: did we all get reasonable timings and get the result we expected?
(11:54:49 PM) chrisconley: yeah
(11:54:59 PM) nicou: no :P
(11:55:15 PM) inimino: nicou: no?
(11:55:39 PM) nicou: probably because of the fast processor, or the uneven distributions of primes, they're a bit like what I expected but not quite, but that's understandable I guess
(11:55:56 PM) inimino: nicou, yeah I did have to use very large numbers
(11:56:09 PM) nicou: yeah, 10¹²
(11:56:11 PM) inimino: the examples in the book did not give me anything I could measure
(11:56:13 PM) inimino: yeah
(11:56:32 PM) nicou: well, so, ex. 1.23?
(11:56:37 PM) inimino: yeah
(11:57:00 PM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.23
(11:57:34 PM) inimino: this one seemed like it could have been answered in a number of ways.
(11:58:12 PM) nicou: I think it is kind of the half, but I'm not sure, again, timings are complicated
(11:58:23 PM) chrisconley: http://pastie.org/383606
(11:58:29 PM) inimino: I didn't actually do any timings
(11:58:32 PM) chrisconley: yeah it looked like half to me
(11:58:36 PM) aamar: http://mibbit.com/pb/VVnWh2
(11:58:41 PM) nicou: yeah, the questions were tricky :P
(11:58:46 PM) aamar: It went to about 2/3 for me.
(11:58:46 PM) seangrove left the room (quit: Connection reset by peer).
(11:58:54 PM) inimino: well maybe I was wrong :-)
(11:59:00 PM) aamar: I timed it with some very large numbers
(11:59:03 PM) seangrove [n=seangrov@adsl-76-237-13-159.dsl.lsan03.sbcglobal.net] entered the room.
(11:59:15 PM) aamar: But it turned out to be overhead from introducing a call to next.
(11:59:43 PM) inimino: yes, I assumed the overhead, and the fact that the 2 is checked first anyway...
(11:59:44 PM) aamar: If changed next to just be a +1 iterator, then I got 1/2 as well.
(12:00:12 AM) inimino: but it all depends on the performance characteristics of (remainder _) I guess
(12:00:20 AM) seangrove left the room (quit: Client Quit).
(12:00:25 AM) nicou: I see
(12:00:37 AM) inimino: if it's optimized in the remainder n 2 case, then it would probably not have any benefit
(12:01:24 AM) aamar: even then, it's going to recompute the entire remainder for 4,6,8,10 which isn't trivial.
(12:01:31 AM) aamar: even if remainder _ 2 is trivial
(12:01:33 AM) inimino: though, in bignum libraries... maybe it can't be optimized much better than O(log n)
(12:03:04 AM) nicou: hmm, 1.24?
(12:03:13 AM) inimino: aamar: ah...
(12:03:22 AM) inimino: that's it, thanks
(12:03:26 AM) inimino: sure 1.24
(12:03:55 AM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.24
(12:04:15 AM) inimino: again, I didn't find anything really surprising on this one
(12:04:22 AM) aamar: http://mibbit.com/pb/ts9wqL
(12:04:25 AM) chrisconley: yeah neither did i
(12:04:34 AM) aamar: Yes, straightforward, given previous exercises.
(12:05:03 AM) inimino: yeah
(12:05:06 AM) inimino: 1.25?
(12:05:13 AM) nicou: yeah
(12:05:25 AM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.25
(12:06:01 AM) inimino: I proved something which turns out to be just a special case of something that's given in a footnote which I read after
(12:06:14 AM) inimino: but it helped be understand why the function given actually gives the right result
(12:06:32 AM) nicou: oh, yeah, squaring a remainder instead of a big number will be faster, in practice
(12:06:45 AM) chrisconley: yeah the answer seemed to given in that footnote
(12:07:06 AM) inimino: I'm sure this is all trivial to anyone that studied modular arithmetic
(12:07:21 AM) inimino: (which I haven't)
(12:08:31 AM) inimino: alright, anything else on 1.25?
(12:08:56 AM) nicou: hm, I think that's it
(12:08:59 AM) nicou: 1.26?
(12:09:04 AM) inimino: alrgiht
(12:09:20 AM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.26
(12:09:21 AM) nicou: constant time?
(12:09:28 AM) nicou: I mean, linear
(12:09:30 AM) inimino: linear
(12:09:32 AM) inimino: yeah
(12:10:08 AM) chrisconley: i was thinking it was 2^n or something
(12:10:25 AM) nicou: yeah, because expmod calls itself O(2^n) times, but since it had O(log n) steps before the change, it will be some sort of log exp = linear
(12:10:29 AM) chrisconley: every call expmod creates two more calls to expmod
(12:10:37 AM) chrisconley: ahhh ok, thanks
(12:10:49 AM) inimino: yeah
(12:11:09 AM) inimino: since n is halved each time
(12:11:22 AM) inimino: 1.27?
(12:11:23 AM) chrisconley: right
(12:11:26 AM) nicou: so 1.27?
(12:11:27 AM) nicou: yeah
(12:11:48 AM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.27.scm
(12:11:52 AM) aamar: http://mibbit.com/pb/ymxjHs -- ugly but it works
(12:12:54 AM) aamar: actually, mine is not right
(12:13:20 AM) nicou: well, that was easy, the Carmichael numbers do fool the Fermat prime test
(12:13:24 AM) aamar: http://mibbit.com/pb/tp7YwJ -- fixed
(12:14:28 AM) inimino: aamar: yours looked right
(12:15:09 AM) chrisconley: i didn't get to these last two problems
(12:15:15 AM) inimino: (< a n 1) <-- what's that mean?
(12:15:38 AM) inimino: chrisconley: ok, I think a lot of people ran out of time on this section
(12:16:02 AM) chrisconley: yeah, it was definitely pretty lengthy
(12:16:14 AM) inimino: yeah, and mathy
(12:16:15 AM) nicou: I got really confused with 1.28 and gave up
(12:16:41 AM) inimino: I just finished 1.28 about 20 seconds before we started it
(12:16:48 AM) inimino: s/ it//
(12:17:05 AM) inimino: so I tested it on exactly one prime and one composite...
(12:17:09 AM) inimino: but it does seem to run
(12:17:12 AM) inimino: http://inimino.org/~inimino/projects/2009/SICP/chap_1/1.28.scm
(12:17:28 AM) nicou: hmm, section 1.3 introduces integrals, summations and roots of polynomials, it won't be any easier
(12:17:38 AM) aamar: (< a n) it should have been
(12:17:43 AM) chrisconley: awesome, just what i was looking for :)
(12:17:50 AM) inimino: did anybody else do 1.28?
(12:18:08 AM) nicou: I'll take another look at 1.28 some other time
(12:18:13 AM) chrisconley: i'm still planning on doing it while trying not to look at any solutions
(12:18:16 AM) inimino: ok
(12:18:20 AM) inimino: chrisconley: alright
(12:18:20 AM) chrisconley: maybe we can discuss next meeting?
(12:18:26 AM) aamar: Yes, concur.
(12:18:32 AM) inimino: yeah
(12:18:39 AM) nicou: you can check with http://sicp.org.ua/sicp/Exercise1-28, the last comment is probably right
(12:18:44 AM) nicou: two weeks is ok?
(12:18:55 AM) nicou: 17 exercises
(12:18:57 AM) chrisconley: nicou: was it you that said you're up to 3.4?
(12:19:02 AM) inimino: I'm wondering
(12:19:06 AM) nicou: yes, skipping a couple of exercises
(12:19:12 AM) inimino: given the length of today's meeting...
(12:19:19 AM) chrisconley: you think 2 weeks is good?
(12:19:21 AM) nicou: 2 hours
(12:19:34 AM) inimino: if we should either move te weekly meetings or possible slow down the pace?
(12:19:34 AM) nicou: I suppose so
(12:19:45 AM) chrisconley: i actually thought this meeting was gonna be 3-4 hours
(12:19:46 AM) hkBst left the room (quit: Read error: 104 (Connection reset by peer)).
(12:19:53 AM) inimino: oh, well, ok
(12:20:09 AM) nicou: mm I don't know
(12:20:15 AM) inimino: if everybody else is fine with the long meetings, I'm ok with it
(12:20:31 AM) chrisconley: i'm good with the pace, but i'm up for changing how we do meetings
(12:20:44 AM) nicou: yeah, probably, what's your idea?
(12:20:56 AM) chrisconley: i guess i'd prefer just one commitment every two weeks, even if it is longer
(12:21:12 AM) nicou: instead of checking solutions, trying to do them together?
(12:21:17 AM) aamar: Agreed, every other week is better.
(12:21:17 AM) inimino: chrisconley: yeah, I can relate to that
(12:21:18 AM) chrisconley: but if we want to change to weekly meetings, i'm up for that too
(12:21:44 AM) nicou: I guess what would be hard is to divide a section in halves in order to meet every week
(12:22:25 AM) inimino: well I feel considerably less fresh than I did at the start of the meeting, but I also was working on the exercises before we started, so...
(12:22:44 AM) inimino: nicou: yeah, that could be hard
(12:22:56 AM) inimino: I think biweekly is working well
(12:23:10 AM) inimino: as long as the sections don't get any longer
(12:23:18 AM) nicou: I believe that section 1.3 is not that hard if you're familiar with continuous functions and such, or if you've seen the lectures, those really do help
(12:23:20 AM) chrisconley: how about we stick with biweekly for the next meeting, but if it gets any longer, we
(12:23:26 AM) chrisconley: 'll look into changing that
(12:23:41 AM) aamar: chrisconley: +1
(12:23:42 AM) inimino: chrisconley: sounds like a plan
(12:23:46 AM) nicou: I think we have enough time in two weeks to get comfortable with section 1.3, and the exercises are not that many, so we'll be fine
(12:23:55 AM) inimino: nicou: alrgiht, cool
(12:23:56 AM) nicou: ok, so it's feb 22
(12:24:05 AM) nicou: whoever can change the topic, please do :)
(12:24:28 AM) inimino: same time same place Feb 22 :-)
(12:24:36 AM) chrisconley!n=chriscon@c-68-37-2-106.hsd1.de.comcast.net: chrisconley has changed the topic to: SICP book club | Next meeting Feb 22 @ 4PM PST - section 1.2 | Wiki http://hn-sicp.pbwiki.com | Mit Videos http://hn-book-club.jottit.com/ | SICP in PDF: http://therobert.org/stuff/sicp.pdf
(12:24:56 AM) inimino: change the section too
(12:24:57 AM) chrisconley!n=chriscon@c-68-37-2-106.hsd1.de.comcast.net: chrisconley has changed the topic to: SICP book club | Next meeting Feb 22 @ 4PM PST - section 1.3 | Wiki http://hn-sicp.pbwiki.com | Mit Videos http://hn-book-club.jottit.com/ | SICP in PDF: http://therobert.org/stuff/sicp.pdf
(12:24:58 AM) nicou: great, it's officially over, I'll post the logs in a minute, thanks all.
(12:25:08 AM) chrisconley: thanks
(12:25:11 AM) inimino: thanks everyone
(12:25:19 AM) chrisconley: thanks everyone, a big help
(12:25:26 AM) nicou: see ya