tag:blogger.com,1999:blog-3722233.post4320211905596298905..comments2020-04-08T16:36:36.701-04:00Comments on Computational Complexity: When a+b is harder than b+aLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-5916712370266593702012-03-24T15:32:59.174-04:002012-03-24T15:32:59.174-04:00This is a great post!
A related discussion appear...This is a great post! <br />A related discussion appeared over n-category cafe<br />here http://golem.ph.utexas.edu/category/2006/10/knowledge_of_the_reasoned_fact.htmlGil Kalaihttp://gilkalai.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1414778148631470402012-03-23T12:09:05.731-04:002012-03-23T12:09:05.731-04:00Hal, you could also note that addition and multipl...Hal, you could also note that addition and multiplication are not associative on floating points numbers, and it's possible to get accuracy improvements by reordering the operands. http://en.wikipedia.org/wiki/Floating_point#Accuracy_problemsQuentinhttps://www.blogger.com/profile/08920982786290915183noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46783897022272151292012-03-22T17:20:47.610-04:002012-03-22T17:20:47.610-04:00This is a great post!
This completely brings up a...This is a great post!<br /><br />This completely brings up an interesting concept. The non-commutative nature of algorithms. Even though 1+4 - 4+1 = 0 is commutative, this demonstrates that it is possible that the algorithm to solve the equation may not be commutative or rather Algorithm(1+4) != Algorithm(4+1). <br /><br />So even though the results are the same, the ordering of the inputs will impact the speed of getting to the results. One way to think about it is to imagine adding a lot of data to small that is open versus adding a little data to a large file that is open. The operation of reallocating memory might be dependent on the change in the size of the file. So adding a lot of new memory might take longer than adding a small amount of memory. This gets to a great point of efficiency in processes.<br /><br />Absolutely great post to think about!Hal Swyershttps://www.facebook.com/hal.swyersnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71771523575613834022012-03-10T06:53:48.256-05:002012-03-10T06:53:48.256-05:00Gasarsch, sometimes i am amazed by why u r so amaz...Gasarsch, sometimes i am amazed by why u r so amazed. It's kinda a little retarded if u allow me say to be so amazed.<br /><br />why is 1+5 more difficult than 5+1 ?<br /><br />u mean by difficult , why does it take more time for the kiddo to respond to ur question. please correct me if i misunderstood u on this point.<br /><br />well, for one, it depends, how u count time. assume there to be a correct way that u employed.<br /><br />then isn't it obvious that a kiddo would naturally be surprised to be hearing, how much is 1+5 ???<br /> and now how much is 5+1 ???<br />it would enter the loop of testing, wait a minute, this 110 year old (!) grandpa called Billy, is asking me the same question ... but he reversed the order ? why would he wanna do this ? Is this a trick question ? That trick question does not work because these two statements are equivalent. maybe he suffers from alzheimer ? Don't u think it's weird he is posing this ? Does my dad know that grandpa has alzheimer ?<br /><br />By having naturally undergone this thought process, the kid has spent an additional 3 seconds. <br /><br />QED.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82273353478709082162012-03-09T01:30:37.418-05:002012-03-09T01:30:37.418-05:001+\omega<\omega+11+\omega<\omega+1Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68071593322329721572012-03-08T13:16:59.646-05:002012-03-08T13:16:59.646-05:00Bill - children's mathematical reasoning and t...Bill - children's mathematical reasoning and the inherent number sense of humans (and animals for that matter) have been widely studied (Dehaene was mentioned earlier). The late Robbie Case has a nice developmental theory you might want to look at http://www.psych.ualberta.ca/GCPWS/Case/Biography/Case_bio2.html. These theories are being implemented in teacher education research, for example, in Deborah Ball's research at the University of Michigan http://www-personal.umich.edu/~dball/ . Your research with your niece confirms what's been known for a long time.John Cherniavskynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54214619537638676652012-03-08T12:54:26.873-05:002012-03-08T12:54:26.873-05:00This area has been fairly well-documented in the m...This area has been fairly well-documented in the math ed literature as well as some of the child development/psychology literature. Karen Fuson did a lot of work laying out levels of students' counting and addition strategies such as counting all and counting on, which you mentioned. Arthur Baroody did some studies regarding children's use of the commutative property, and Robert Siegler has done some work on modeling students' strategies for solving addition problems. (http://www.psy.cmu.edu/~siegler/shragersiegler98.pdf)Laura Bofferdingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88801378024631169242012-03-08T10:40:18.057-05:002012-03-08T10:40:18.057-05:00Here’s what I know from Math Ed research:
Very e...Here’s what I know from Math Ed research: <br />Very early on, many kids will calculate a + b by counting out a, then counting out b objects, then counting them together, with each counting round starting from 1 (i.e. the number of steps is 2a +2b). The ability to subitize, that is, recognize automatically that, say, 4 chips are four in number without counting out 1, 2, 3, 4 develops eventually but should not be taken for granted. The ability to think about adding numbers without physical objects is also a cognitive leap. In fact, the “mentally counting on from a” strategy used by your daughter represents a significant achievement in addition skill. Other skills include, as you suggested, using the commutative property for efficiency; ideally this is used as a tool in subtraction as well as addition. (For example, calculating 21 – 17 by counting backwards: 20, 19, 18, 17, and stopping there to give an answer of 4, rather than counting back seventeen times 20, 19, 18, …. 4.) At a certain point, kids hopefully develop the skill to count in chunks larger than 1, and use known combinations and an understanding of place value for efficiency. For example, if 2 + 3 is a known fact from memory, then 22+3 can become a single step calculation. Memorized facts can be used together. For example, if I know that 8 + 8 =16, I can determine 8 + 5 by using my known fact followed by jumping back 3 in a single hop. (At this stage, students know that 5 is 3 less than 8 without thinking, and can calculate 16 – 3 without counting backwards by 1’s). Compensation/regrouping should be used strategically also. For example, 28 + 6 = (28 + 2)+ 4 = 34. Interestingly, many adults still don’t do this: If you ask them to add 997 + 505 without a calculator, many will balk or begin doing the standard algorithm with pencil and paper rather than take advantage of the nearness of 997 to 1000.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21332180762213980112012-03-08T06:51:56.101-05:002012-03-08T06:51:56.101-05:00Is there a natural model of computation, and a nat...Is there a natural model of computation, and a natural commutative operation '+', where computing a + b takes different time than computing b + a? (Of course, it would have to be a model where there is non-zero cost for swapping the order of arguments, or perhaps one in which it takes time to decide in the first place whether a + b or b + a is more efficient to compute.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78886938579216539262012-03-08T03:42:48.851-05:002012-03-08T03:42:48.851-05:00The computation time corresponds to a direct aplic...The computation time corresponds to a direct aplication of the definition of the addition operation via a+s(b):=s(a+b) and a+0:=a. <br /><br />Also that 1+4 is not confused with 4+1 (at least for smaller children) corresponds to my experience. And I think this is perfect. A proof that addition is commutative needs the principle of (mathematical) induction. If you remove this principle from the definition of numbers, you have the wanted model. I would say that most humans don't understand the idea of mathematical induction well nor that of a proof, but at some age they anyway start to use commutativity when adding. So they don't do this because of logical understanding, but because they're told that they can use it, or because of the experience they made after doing a lot of calculations (by inductive reasoning :).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5136972939992344792012-03-07T22:43:45.218-05:002012-03-07T22:43:45.218-05:00Nice experiment! My lay attempt at a theory -
I t...Nice experiment! My lay attempt at a theory - <br />I think our brain evolved to make estimates faster than computing the exact answer. So, when you say "4+1"<br />(a) 4 enters my brain. <br />(b) Some of my neurons "know" how large 4 is, in the same sense that logicians train themselves to "know" BB(n), aleph0, aleph1. 4 is a model of something in the world. <br />(c) 1 enters my brain and _immediately_ my brain makes a comparison i.e knows that the answer isn't very far off from its previous estimate of the real world object, 4.<br />(d) Addition is performed to verify (b),(c).<br /><br />When you say "1+4", steps (a),(b) happen the same way, but when (c) happens, instinctive comparison causes my mental estimate of the model to be completely thrown off charts. (d) is performed with no apriori estimate of the answer. New model of reality is created - this causes delay. <br /><br />When kids learn that addition is commutative, instinctive comparison happens before creating a solid model of the external object and kids start with the bigger number as their initial estimate. "I have 4 sheep and missing 1" is less alarming than "I have 1 sheep and missing 4".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66466303673897390412012-03-07T21:57:35.559-05:002012-03-07T21:57:35.559-05:00easy, when b is a limit ordinal and a is a smaller...easy, when b is a limit ordinal and a is a smaller ordinal.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50683303366562431882012-03-07T21:56:01.173-05:002012-03-07T21:56:01.173-05:00> The most interesting of these to me was that ...> The most interesting of these to me was that 1+4 took much<br />> longer than 4+1. Why is this?<br /><br />Or maybe she just got confused because you asked for the 5th time something she should answer with a 5. If she smiled or laughed, then I'm pretty sure her kid mind was thinking "what is this silly doing? hihi" :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63470377651541074332012-03-07T17:51:02.729-05:002012-03-07T17:51:02.729-05:00I am concerned that she didn't realize she alr...I am concerned that she didn't realize she already had the answer for 1+4 after giving an answer for 4+1 and that she didn't notice the answer is always 5.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75134640007605148562012-03-07T17:11:11.240-05:002012-03-07T17:11:11.240-05:00I also highly recommend Stanislas Dehaene's bo...I also highly recommend Stanislas Dehaene's book "Space, Time and Number in the Brain: Searching for the Foundations of Mathematical Thought".Unknownhttps://www.blogger.com/profile/02691243186365493963noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42806127821744353842012-03-07T13:23:19.803-05:002012-03-07T13:23:19.803-05:00The Problem-size Effect in Mental Addition: Dev...<a href="http://web.missouri.edu/~gearyd/GearyMathCog.pdf" rel="nofollow">The Problem-size Effect in Mental Addition: Developmental and Cross-national Trends</a>Martin Thomahttps://www.blogger.com/profile/13629221699214248094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57139581194938420262012-03-07T13:06:21.010-05:002012-03-07T13:06:21.010-05:00This corresponds exactly to my experiments with my...This corresponds exactly to my experiments with my 5 (and now 6) year old. And it's precisely for the reason you mention. In fact once he realized how to flip things around, he used one time unit to do the flip, and then did the +1, reducing the complexity to min(a,b)+1 :)Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7405043535358808282012-03-07T12:28:15.843-05:002012-03-07T12:28:15.843-05:00I seem to remember Stanislaus Dehaene's book, ...I seem to remember Stanislaus Dehaene's book, The Number Sense, describes timing tests for multiplication. They can infer up to what number people use table lookup, when they switch over to an algorithmic way to compute product, and which algorithm.Chris Polletthttp://www.cs.sjsu.edu/faculty/pollett/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84745978470102334792012-03-07T11:29:31.990-05:002012-03-07T11:29:31.990-05:00The phenomenon you described is called the Problem...The phenomenon you described is called the Problem Size effect, and is the subject of several cognitive models. Christian Lebiere's dissertation comes to mind, where the ACT-R cognitive architecture was used to model the time needed to calculate the answer. Like you suggested, iterative counting is one of the back-up strategies, leading to the increased time. This sort of hits the idea of complexity, but from more of a psychology angle than a complexity angle.Anonymoushttps://www.blogger.com/profile/05840410913748847862noreply@blogger.com