tag:blogger.com,1999:blog-264226589944705290.post8919588898459186275..comments2023-11-05T03:45:25.001-08:00Comments on God Plays Dice: A problem of Feynman on parallel computationMichael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-264226589944705290.post-88509335834001966292007-09-25T18:09:00.000-07:002007-09-25T18:09:00.000-07:00> returns a 0 if the two bits are different and a ...> returns a 0 if the two bits are different and a 1 if they're the same. (This is, of course, bitwise exclusive OR.)<BR/><BR/>I think you meant XNOR.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-21257754749371410112007-09-25T17:26:00.000-07:002007-09-25T17:26:00.000-07:00That's average case, because you can't guarantee t...That's average case, because you can't guarantee the proportions of easy to hard numbers across all possible inputs.<BR/><BR/>Imagine something like a resizable array, where each time the amount of space allocated to the array runs out we double the amount of space allocated. Then adding to the array is amortized O(1), since most of the time we just write into the available space (O(1)) and each time we run out of space we have to allocate more and copy all the old data over (O(n)).<BR/><BR/>Call the amount of space allocated the "size" of the array, and the number of items in it the "length". If the array starts with size 4 and length 0, adding the first four items take O(1) time. Adding the fifth item (n = 5) takes O(n) as we have to copy all 5 items across. The size is now 8, so adding the next three items (n = 6, 7, 8) takes O(1) time. Adding the ninth takes O(n). And so on.<BR/><BR/>Because we expand the size of the array by a constant proportion (multiply by two in this case), each doubling takes O(n) time but only happens 1/n as often (at n = 4, 8, 16, 32 ...) so *on average* this is an O(1) operation. Because this property has nothing to do with the nature of the inputs, it is amortized O(1) time.<BR/><BR/>See also http://en.wikipedia.org/wiki/Amortized_analysis and http://en.wikipedia.org/wiki/Dynamic_arrayAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-52526120581095275292007-09-25T11:48:00.000-07:002007-09-25T11:48:00.000-07:00Sorry, colin's right. As I said, it's been a long...Sorry, colin's right. As I said, it's been a long time...<BR/><BR/>But the two aren't wholly unrelated. Let's say you're given the task of adding up a big list of pairs of binary numbers. You can partition them into rough difficulty classes and say "these are easy, those are hard". Then you get a running time for easy sums and hard sums, and average over some probability distribution. Is this amortized or average-case?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-13104640613568766692007-09-25T10:40:00.000-07:002007-09-25T10:40:00.000-07:00You didn't mention the complexity of addition, but...You didn't mention the complexity of addition, but using O(n^3) clerks (assuming a clerk is a transistor) you can can add in worst case O(log n) time.augustsshttps://www.blogger.com/profile/07327620522294658036noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-5492554290612772262007-09-25T10:38:00.000-07:002007-09-25T10:38:00.000-07:00This comment has been removed by the author.augustsshttps://www.blogger.com/profile/07327620522294658036noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-50649751234948258942007-09-25T08:12:00.000-07:002007-09-25T08:12:00.000-07:00Amortized analysis is where you prove that aggrega...Amortized analysis is where you prove that aggregating a bunch of consecutive operations takes a given order of time (often less than the worst case for a single operation).<BR/><BR/>As you said, what you mentioned above is closer to average-case analysis.<BR/><BR/>Amortized analysis usually has some concept of which operations are "cheap" and which ones are "expensive", and then construct a proof that there are enough cheap operations to cancel out the expensive ones.cdevilbisshttps://www.blogger.com/profile/16698099083827512526noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-31198548756676586302007-09-25T07:32:00.000-07:002007-09-25T07:32:00.000-07:00I've heard of amortized analysis; I'm not sure if ...I've heard of amortized analysis; I'm not sure if that's exactly what I'm doing here, or if what I did here was what they call "average-case" analysis.Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-74759750529227495812007-09-25T07:09:00.000-07:002007-09-25T07:09:00.000-07:00But not always. Somebody could be deliberately fee...<I>But not always. Somebody could be deliberately feeding you numbers that are hard to add. Some sort of sadistic grade school teacher.</I><BR/><BR/>From what I remember of my halcyon computer-science days, this is the difference between "worst-time" analysis and "amortized" analysis.Anonymousnoreply@blogger.com