From f059a1ae26ab89f0b47fbd01db4188c188d1e2e3 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Thu, 19 Mar 2009 14:06:12 +1030 Subject: [PATCH] Add Tim's mail. --- .../[ccan] Mathematics Module.mbox | 170 ++++++++++++++++++ 1 file changed, 170 insertions(+) create mode 100644 junkcode/tterribe@email.unc.edu-nmbrthry/[ccan] Mathematics Module.mbox diff --git a/junkcode/tterribe@email.unc.edu-nmbrthry/[ccan] Mathematics Module.mbox b/junkcode/tterribe@email.unc.edu-nmbrthry/[ccan] Mathematics Module.mbox new file mode 100644 index 00000000..c4a57b4e --- /dev/null +++ b/junkcode/tterribe@email.unc.edu-nmbrthry/[ccan] Mathematics Module.mbox @@ -0,0 +1,170 @@ +From tterribe@email.unc.edu Wed Mar 18 15:38:26 2009 +Return-Path: +X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on ozlabs.org +X-Spam-Level: +X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham + version=3.2.5 +X-Original-To: rusty@rustcorp.com.au +Delivered-To: rusty@ozlabs.org +Received: from ozlabs.org (localhost [127.0.0.1]) + by ozlabs.org (Postfix) with ESMTP id 5399ADDE0E + for ; Thu, 19 Mar 2009 09:38:11 +1100 (EST) +X-Original-To: ccan@ozlabs.org +Delivered-To: ccan@ozlabs.org +X-Greylist: delayed 2513 seconds by postgrey-1.31 at ozlabs; + Wed, 18 Mar 2009 16:50:38 EST +Received: from mxpm.isis.unc.edu (mxp3.isis.unc.edu [152.2.2.161]) + by ozlabs.org (Postfix) with ESMTP id 72C75DDEFA + for ; Wed, 18 Mar 2009 16:50:37 +1100 (EST) +Received: from smtp.unc.edu (smtpsrv3.isis.unc.edu [152.2.2.251]) + by mxp3.isis.unc.edu (8.14.3/8.14.3) with ESMTP id n2I58gVL008719 + for ; Wed, 18 Mar 2009 01:08:42 -0400 +Received: from [192.168.5.124] (pool-173-73-173-234.washdc.fios.verizon.net + [173.73.173.234]) (authenticated bits=0) + by smtp.unc.edu (8.14.3/8.14.3) with ESMTP id n2I58fex014904 + (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) + for ; Wed, 18 Mar 2009 01:08:42 -0400 (EDT) +Message-ID: <49C081CA.5040501@email.unc.edu> +Date: Wed, 18 Mar 2009 01:08:26 -0400 +From: "Timothy B. Terriberry" +User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; + rv:1.8.1.11) Gecko/20071216 SeaMonkey/1.1.7 +MIME-Version: 1.0 +To: ccan@ozlabs.org +References: + <200902040051.54761.rusty@rustcorp.com.au> + + <200903181452.14263.rusty@rustcorp.com.au> +In-Reply-To: <200903181452.14263.rusty@rustcorp.com.au> +Content-Type: multipart/mixed; + boundary="------------050107030903080507030408" +X-Proofpoint-Virus-Version: vendor=fsecure engine=1.12.7400:2.4.4, 1.2.40, + 4.0.166 definitions=2009-03-18_01:2009-03-13, 2009-03-18, + 2009-03-17 signatures=0 +X-Proofpoint-Spam-Details: rule=uncdefault_notspam policy=uncdefault score=0 + spamscore=0 ipscore=0 phishscore=0 bulkscore=0 adultscore=0 + classifier=spam adjust=0 reason=mlx engine=5.0.0-0811170000 + definitions=main-0903170259 +X-Mailman-Approved-At: Thu, 19 Mar 2009 09:38:09 +1100 +Subject: Re: [ccan] Mathematics Module +X-BeenThere: ccan@ozlabs.org +X-Mailman-Version: 2.1.11 +Precedence: list +List-Id: "If perl can, maybe ccan?" +List-Unsubscribe: , + +List-Archive: +List-Post: +List-Help: +List-Subscribe: , + +Sender: ccan-bounces+rusty=rustcorp.com.au@ozlabs.org +Errors-To: ccan-bounces+rusty=rustcorp.com.au@ozlabs.org +Status: R +X-Status: NT +X-KMail-EncryptionState: +X-KMail-SignatureState: +X-KMail-MDN-Sent: + +This is a multi-part message in MIME format. +--------------050107030903080507030408 +Content-Type: text/plain; charset=ISO-8859-1 +Content-Transfer-Encoding: 7bit + +Some of this stuff seems a little trivial to include, but if we're going +to do so... + +The result of nCr is guaranteed to be an integer after each iteration, +and so there's a) no reason to keep a separate numerator and denominator +and b) no reason to do a minimum of nine (9!) divisions every iteration. +Only a single gcd() is needed, and even that can often be skipped, +requiring only 2-3 divisions per iteration. This is illustrated in +choose.c (attached). You can easily add the check for the smaller r (_m +in this implementation), upgrade the types to long, etc., as desired. If +one really cared about speed, the divisions could be entirely replaced +by multiplications and a small lookup table, since m and n are known to +have a very limited range (or the result will overflow). + +Also included are a gcd() implementation without tail recursion and +egcd(), the "extended" gcd, as well as a nice illustration of the use of +egcd, a Chinese Remainder Theorem solver for systems of linear +congruences. I don't have time to format these into a nice module with +test cases right now, but feel free to take what you want and throw the +rest in "junk". The code is (C) 1998-2001, except crt.c, which is (C) +1999-2001, 2007. I'm releasing it here under the LGPLv2 license. + +--------------050107030903080507030408 +Content-Type: application/x-bzip; + name="nmbrthry.tar.bz2" +Content-Transfer-Encoding: base64 +Content-Disposition: inline; + filename="nmbrthry.tar.bz2" + +QlpoOTFBWSZTWdZHi4IAD0t/nv/QAEB7//+/u2e8i//v/+4AQAAIAAGEgAAIYA798qVUUAAX +YNLYVbSAAAKUAAKAAAAcGQaNAGTTENNBkGIYQNAaMTEaAAAaCjTEBIHqAADT1D1AAGgAAAAA +HBkGjQBk0xDTQZBiGEDQGjExGgAAEmpFNRlNT/RGVN5U2mptT2qabUNqBiAyAADI8o09Eaeo +cGQaNAGTTENNBkGIYQNAaMTEaAAAKkgggjQEZAQ0Mk0jU8U9Gmo0eU9TxpQZkaMjU2p9kDMf +V9wivZ4gOTqn7wGbkUSRyyEA29t22fDfGfQl4fTBxbWtte1ra3VtnHjpqhvvQpVKhSqEVIKR +LJUUqJKoTo/kUfaDk4lVemwZOWUGotQXUVLMhTZuP2LZrGWV8VUvVp+8vi9qmK+7B9lHCkb8 +yh+x2DE6DhzYZfIlH8CYGAmOI79GiqE3TyGgJLphSoomCpKsFYI2q9VcqgvgHEGoRkZPGHjJ +EPGFISTMkk5VIkWMIRGIiJBBA4Azk8QZLHw6jf1iIqr1V3v3GzlSqccvyMsyOsZOTBs8jevS +x14Jnzbf7BdiquJnDPRuUFDECxCenKDoOj2LHN2GS1m5RQvG5gwvTJRZSjGWtjotTKdCmkra +1zR2WMOLDZO/l1fN/gS6tPBoaZ/hjO+8WfuNsr1W1l+bHI8OsHGWE1GrTp1YJYREyyZy9c+9 +06L2EwM23ZlsZHez1GrkMsnNtTYp+I1dzbgd9+DetnZ19jswy4v49VuWeh1as99KWZVItzcv +4OHU2NU2UwpS/jfhl3FcWnucnCbFVw8TZ6Xm3aNODbUpG6zBTuMObVevJ4WdrfFbrMeJyWYM +u9exZ2vzPQaaDLzpeqbU6b9JqYdDXa15etqjbqnhs9Lg8vzYbvFpvbV4tF/fm+DusbKaWmzR +Z1s+FJlSYdZo61zc1UaX+7XL0rqYd7LUazNZ5utbmw5JRolpuWZxGNd9Noycmprj5ltmkd6y +yUp0KFa7vHl7GiaKb8d27rV62nG9lU4G63TDm0qlk1wzGb4XS5Te6rLP9NTLlMG11mGmsmJV +3FlePq4plnV6VOQ4ztVdxVS3FKU6+7orHFqp+lqxe1dP420bLOA4Ow0ceGzJS97t7WS/tVY6 +kpPiP5yVVZ7nZ1b4cztTr9nPkUPzsfHs+dfJrZ+e0zcx9vk6lzLNnE2qSXcH5l09cMAxOYN8 +stkO0dgpOUT+rWB14IblgbmNKNyIWNRDAccl0GhVDEVrnXMgqKsDDMgCpeGEQLTuHyqrF+lu +5p/Jn2p0Tsy4P6newwulHD4Kw7vExPXdop7DtX2eHx1bM8LrRTgUXlusfJ3vm7XRk6MuDfKe +Dzb697/Wn3fNwtanCca1Rx4Wy59HYcO/14e3+zUu7X9vG7V713oYasOCzlkr0rNVLtWz23q9 +6epbu4bM0qtbcWvRdsqcGLVTBq3bJJbw7PW5QLVahD52yLYc3q5QrQoqqlV12tdh3LOOmo/V +/0hvIlzY7JPmutRVxV37HvLzFKxUrK6ope0sNEidcP3dB0DT5bkDJA4z6YYpeBeBfOi1JmMU +xcQqqqGERAk5F7ANET46LJVgN7ZYWjeoHKZEtgiVB9NJzzDOnO0mjXWHNwcKZxfN22s4VFr7 +1rrr9bbZW3XZuzBnfbdeGkLbPbnbVhui+l7VritrYqaXb5q0mZo1cxfRto14cbcMWqG25qq3 +k73e+T7HoYMj26UWez6Gcfebb8frKx8/XqW46WybNaipIn1UGcEMDoozesCoanJMcM0gWdxy +MRrJYXMhdZtVcufBtl2dNWeVVzWtpni9fsiij+vi22w/a8el2WHh5AGLdgB2I2TRmskWLA4Z +rqYCndoy0AGfVM9pzCk2aR4ODHeyyaTMh4P5nu2lrwKGdIFoUdpLznlMS7C//pSyXgsfVlcv +aySqk20aLsLe/YiIgi8M5gcWMeTQbeutHWJOHeKDmAQRDu/a1bIZc9XMlbcKuHhAbNyJChhk +48K3zdvvriqqqrsdpRSl5NNtrXXve5VH59b3eP04uupUpScIeZL0onepLa0hVLGnpw4leWf/ +jS2M2y0s1kqqoqt6Fk9HsWjef7fX2z/y9SdHyWfPN3E+hY2SjAw/6rv0UkmVlvfKTJtCjFw/ +UVJio+M2H6tGEoZ4xyVKikor5R+uJwTmazsPA4Kh30i1IfP6vv3YorytYm8Re0loVP0HttPp +lSOpJHZzV61lnm+HfZShdqdT7ut56CmrVNZH5CgwUnxKm7fdwbNaj9dWqScrLnptHtrJT2Fm +aoqVVFi1L2VXp8sQwVJz5qUVULiriyhd5ZeXz2ybz9nX3p4JiOB+EsWKjhC2FzpcWdA6p/77 +fxdXuPfT4OKXovFpwMT0MNF7ZYq1o/Sz9OEY30XlypGpUl4stO1imMJxZLKZqqNFrDgzoviZ +SlKsJmh8IyqGLRs2Zi74MN12cLHzF2V1MReqil5O3Y63EfTxaFsYcrGLy9E4tZ3DRJiJvPV8 +fY973uKHBNfP3VVO1MqrsVNKSn/edS6YPJNLfr8WZP2mTl7TymVnkpW89bRJ/zoc5qeT1ihS +72XNrVKpeHJXrhkuYkruxlV9pOKlnNd6ptG3XJUKVI7xSUntOvRUTjmG57FAh5QSQoQWlQRJ +RSUEQnGB+YaNbpKTVRLzYxE3MJb3vcVLrlCr1Ve5T3VW5suh6jk2YsdFmk+07nhFUZrBKECx +Ko3aIMSeZJEQiCRGFJSiooqCqSlT8uLSXlHmqS0WSYlxdKYF7JkqGqup9T22WUs+3qWilxbu +qfj+3K+ivvbFi1F9ftuvUrl8eDVnSn5R87sr5ye4WOpTAu+g+o5yc6k+VVXF85xeSeL1KUUw +/k1jxqJz+uRnmmZg7BQ4zP3LWu28jxSyyUpZaftdnbYuvFFVVJHXJI417zeP45k5KqKoqlSH +dJpHM9RiGHepu8dEnFPom81qST3LaJ5OD+1SnxegcFKKpVKYPqT5cPwT4tJpqmF3UnFkeGBq +UpSZXcJLl9EsLDgh2MjdVivpKRSjwcZ10edfZ6vwZYZXtYqvx/VrWJmnBGqycJ5JSx1o65HV +DuJeYk/fWOW9/fTrVLVnMr3VeZkVSg3cFKkOKXsepcqyrFeD8ZdaqrTJdR0NLMFrMXkWXKWm +JaKlB50WYGy0XzE1nRZKWbSGCpF5eKMSli65iUNmyrCx+VN5QtKEMBwN0KKN0PR6P+5+rz9W +93ddauvRPkSQxgaUrslQ6dvbCWVJKVFSopaWQtJoixdPi9Z8UPO8o+r4sLVMv65JPrHBD2Ki +GELxH46UOUicJFIuZlKWRaH1w+Q+1TpPmdsPsScCdb/iPVJzcUpRntdWP+XZ3MUYI6lpD4LL ++qyGSp6YlTpLFLJVRFKMvqaOnqNDWa1FUopSo1iXnqt7P00s+/e1OFkm0jaTxTdfjwkkyXg5 +pbzk8YelmT0QrpCvQ4N2G9ouscJeWpPYqNdWVl2imlMMmcsVmxfweOl8LFkUosKa7sfzat1l +lPu09H3u/wpO/1cxUa81Op0VTRYstKU1OmYaNdYz0lTWrFklkwURu310KLpW0M/iRuaUXllI +3ZbMWpL0ReSpZKTxcdV2FehgWaV4KXSpmsVU0sWU405WVaLSzTp0vzorposnBrD11aOuRwQ2 +YRySn4Yp4nVqNpNHCRD8KklKhd/nHfeTKinVC0mpspUqU71lpTKyWqrWFq8Ki6koVFUqUmMw +nL3dFlRTJ0kkzGqd3uUnwWTxs4fr1xj0ecHKf8OiS52vAtPaPbQ7ke6c3wYlk81PyK5+uST3 +dQxP5w/pDrf0+iQ0DTzffT0Kemzzz540M+frmgo9tSSlQe06nkWvzaLSXzFUvwbLHfQnrko8 +Io/YU5q/o6/979nHjdrOZbZWy8Onro7O0qFuos+UqWfQs7Iau1FvsHCk93tOx950SxD/+LuS +KcKEhrI8XBA= +--------------050107030903080507030408 +Content-Type: text/plain; charset="us-ascii" +MIME-Version: 1.0 +Content-Transfer-Encoding: 7bit +Content-Disposition: inline + +_______________________________________________ +ccan mailing list +ccan@ozlabs.org +https://ozlabs.org/mailman/listinfo/ccan + +--------------050107030903080507030408-- -- 2.39.2