tag:blogger.com,1999:blog-3722233.post4992994049965930699..comments2024-08-03T11:58:59.111-05:00Comments on Computational Complexity: What is Closed Form? The Horse Numbers are an illustrationLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger23125tag:blogger.com,1999:blog-3722233.post-15881346359938992942024-05-14T08:45:19.293-05:002024-05-14T08:45:19.293-05:00computational complexity is not the only valid per...computational complexity is not the only valid perspective. one can be interested on other aspects, e.g. functions that are well behaved in some manner, particularly in mathematical analysis; concepts from a set of well studied functions as in statistics (Gamma function is a core concept), etc.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52068139424573098642024-05-14T08:27:33.088-05:002024-05-14T08:27:33.088-05:00@Lance, this resonates with the margin definition ...@Lance, this resonates with the margin definition in Concrete Mathematics [GKP] on page 7. <br />@Bill, [GKP] also answers the relevant point about `n!' "The product of the first n integers, n!, has proved to be so important that we now consider it a basic operation. The formula `n!' is therefore in closed form." It also mentions that the recursive<br />formulation 1 . 2 . \dots . n is NOT a closed form. (citing Knuth!)<br />When in doubt, consult with the latest version/edition of [GKP] about what is accepted. <br />Evangelos Georgiadisnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88155529930577267612024-05-13T23:24:01.054-05:002024-05-13T23:24:01.054-05:00lol. let's not rely on wikipedia about math sp...lol. let's not rely on wikipedia about math specifics. just imagine had they included factorial!another anonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91254171982230381262024-05-13T17:56:29.847-05:002024-05-13T17:56:29.847-05:00I'm guessing the phrase "closed form"...I'm guessing the phrase "closed form" may have evolved as a way of saying "easy to compute", before the notion of "program" was as formalized?<br /><br />Also, although the "Horse Numbers" are defined by equations, it looks like at any point, only one case applies. So you could imagine writing it in Haskell or OCaml, with a "case" or "match" statement.<br /><br />It might not be very efficient, though. Back in the day, a gratuitously-inefficient definition of n! ("nfib") was a toy benchmark for parallel Haskell implementations...Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19733336414693466062024-05-13T08:28:10.678-05:002024-05-13T08:28:10.678-05:00https://en.wikipedia.org/wiki/Closed-form_expressi...https://en.wikipedia.org/wiki/Closed-form_expressionAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67093402227018565172024-05-13T08:20:20.572-05:002024-05-13T08:20:20.572-05:00What you can compute without loop in language depe...What you can compute without loop in language depends on your programming language, exponentiation is often implemented in programming languages with a loop. Ask a numerical analysis person about all that problems that once needs to deal with when computing exp.<br /><br />Often people in math take elementary functions as the definition of closed form.<br />https://en.wikipedia.org/wiki/Elementary_function<br /><br />Unless you do logic of course.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87311247331148320752024-05-13T08:00:01.158-05:002024-05-13T08:00:01.158-05:00To me closed form is a computational concept, a va...To me closed form is a computational concept, a value that can be computed without loops or recursion, for example the nth Fibonacci number is \(\frac{\phi^n - \psi^n}{\sqrt{5}}\) where \(\phi = \frac{1 + \sqrt{5}}{2}\) and \(\psi = \frac{1 - \sqrt{5}}{2}\)Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29669579013044365462024-05-12T21:43:04.471-05:002024-05-12T21:43:04.471-05:00Good topic, but the question is probably ill-posed...Good topic, but the question is probably ill-posed (or too context agnostic) and should be amended to `Under what notion or in what sense is it considered closed-form?' A well-formalized, algorithmically accessible, and accepted notion of `closed form' exists within the framework established by Bill Gosper and Doron Zeilberger. This provides more fruitful ground to constructively explore the question, along with other TCS related questions. For instance, in what sense or under what model of computation is a `closed-form' solution, if one exists in the Zeilberger/Gosper sense, more efficient. <br /><br />An equally essential must read is Don Knuth's April 1970s letter to John Riordan (Rockefeller) and May 1970s letter to Neil Sloane and c/o Ron Graham who were both at Bell Labs, about sequence A670 (Bill, your Horse Numbers. Knuth stumbled upon them in connection to computer sorting). Knuth euphorically remarks to Neil Sloane, his first success using a predecessor of OEIS. (Incidentally, this validates that the best startup ideas usually always come in form of pet projects. Bell Labs must have been one of these three good places!)Evangelos Georgiadisnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32845557438599834822024-05-12T13:14:51.042-05:002024-05-12T13:14:51.042-05:00Personally I would say the student is first right ...Personally I would say the student is first right (H(n) is not closed form) and then wrong, as n! is not a closed form expression.<br /><br />From https://en.wikipedia.org/wiki/Closed-form_expression :<br /><br />In mathematics, an expression is in closed form if it is formed with constants, variables and a finite set of basic functions connected by arithmetic operations (+, −, ×, /, and integer powers) and function composition. Commonly, the allowed functions are nth root, exponential function, logarithm, and trigonometric functions.<br /><br />It does not specify the factorial.<br />Robertnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43156474729796927432024-05-12T00:34:50.118-05:002024-05-12T00:34:50.118-05:00(Bill) My take is that I am enlightened and I than...(Bill) My take is that I am enlightened and I thank you for that!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24285640632802519272024-05-12T00:31:41.999-05:002024-05-12T00:31:41.999-05:00even if we consider dynamic program running in O(n...even if we consider dynamic program running in O(n^2) time, would O(sqrt(n)*log log(n)) not be substantially better?<br /><br />But here is an older result still running better.<br />"On the complexity of calculating factorials" by Peter Borwein Volume 6, Issue 3, September 1985. Time complexity O(n(log(n)*log*log(n))^2). What's the take now?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12330687965153466942024-05-12T00:18:19.857-05:002024-05-12T00:18:19.857-05:00(Bill) Thanks, fixed. (Bill) Thanks, fixed. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35978977123414881712024-05-12T00:07:51.844-05:002024-05-12T00:07:51.844-05:00The recurrence is off by one, I think. h(0) = 1, h...The recurrence is off by one, I think. h(0) = 1, h(1) = 1, h(2) = 3,… Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68063690734074435952024-05-11T23:57:07.664-05:002024-05-11T23:57:07.664-05:00(Bill) AH- when I said `recurrence' I meant `d...(Bill) AH- when I said `recurrence' I meant `dynamic program' which will compute the first n rows of Pascal's Triangle, each entry requiring one addition. For (n choose k) for any k this takes O(n^2) time. I don't know the current bounds on M(n log n) so I don't know if your technique is better than using Dyn prog or not. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78575198511774250762024-05-11T23:49:55.352-05:002024-05-11T23:49:55.352-05:00comrades, what am i missing?
the complexity of cal...comrades, what am i missing?<br />the complexity of calculation factorials is known O(log log n M (n log n)), where M(n) is the complexity of multiplying two n-digit numbers but time complexity of recurrence (n choose k) is in O(2^n)ish? <br /><br />anonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22385444540031258752024-05-11T21:51:54.604-05:002024-05-11T21:51:54.604-05:00writing a program to carefully look at n! and canc...writing a program to carefully look at n! and cancel it with terms in the denom sounds like it would be tricky. You would store n! as the tuple (1,2,3,...,n) and then look at the tuples in the num and denom and cancel. Seems complicated. More efficient then the recurrence? I didn't think so but I now see it as an interesting question. (OH- this is Bill)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19993871639718413652024-05-11T21:48:22.567-05:002024-05-11T21:48:22.567-05:00(Bill) (I thought I already posted this) The stude...(Bill) (I thought I already posted this) The student asking if there was a closed Form made me consider What is closed form? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12393774171400843312024-05-11T21:32:50.375-05:002024-05-11T21:32:50.375-05:00I would rather say closed from is not an absolute ...I would rather say closed from is not an absolute concept, it is relative to language you choose.<br /><br />Is it essentially asking if some function can be represented as a term in a language.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74973685287645264162024-05-11T21:30:23.841-05:002024-05-11T21:30:23.841-05:00 It would be helpful to know who or what instigate... It would be helpful to know who or what instigated this topic. H(n) is not strictly closed form, but you make 0 efforts in motivating what you mean by closed form. Finally, computing n!/.... instead of recursion could be more efficient for specific values, due to cancellations. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51672565917760680442024-05-11T20:51:19.276-05:002024-05-11T20:51:19.276-05:00ehh? when computing n!(n/2)!(n/2)! many terms canc...ehh? when computing n!(n/2)!(n/2)! many terms cancel out, resulting in fewer overall operations to computing both n! and (n/2)!<br />what happens when n is large and k is close to n/2 computing n!/...... is more efficient, no?chrisnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78104975181988336412024-05-11T20:17:14.240-05:002024-05-11T20:17:14.240-05:00(Bill) Are you saying that computing n!/(n/2)!(n/2...(Bill) Are you saying that computing n!/(n/2)!(n/2)! is more efficien then the recurrence (n choose k) = (n-1 choose k-1) + (n-1 choose k)? One issue with computing n!/... is that there will be HUGE intermediary numbers which are a problem. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40237266288005284532024-05-11T20:11:51.737-05:002024-05-11T20:11:51.737-05:00"Does that let you compute it easily? No.&quo..."Does that let you compute it easily? No." <br />I disagree, it is more computationally efficient, not just notation. Write out the number of steps a computer takes!chrisnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32484302259579194902024-05-11T19:56:27.083-05:002024-05-11T19:56:27.083-05:00Good line of inquiry, what or who prompted your c...Good line of inquiry, what or who prompted your curiosity and exploration? It's certainly useful to link idea of closed form to efficiency of computation. Therefore knowing if there is a closed form in some formalized sense is meaningful.Anonymousnoreply@blogger.com