git.ozlabs.org Git - ccan/blob - junkcode/tterribe@email.unc.edu-nmbrthry/[ccan] Mathematics Module.mbox

   1 From tterribe@email.unc.edu Wed Mar 18 15:38:26 2009
   2 Return-Path: <ccan-bounces+rusty=rustcorp.com.au@ozlabs.org>
   3 X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on ozlabs.org
   4 X-Spam-Level:
   5 X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham
   6         version=3.2.5
   7 X-Original-To: rusty@rustcorp.com.au
   8 Delivered-To: rusty@ozlabs.org
   9 Received: from ozlabs.org (localhost [127.0.0.1])
  10         by ozlabs.org (Postfix) with ESMTP id 5399ADDE0E
  11         for <rusty@rustcorp.com.au>; Thu, 19 Mar 2009 09:38:11 +1100 (EST)
  12 X-Original-To: ccan@ozlabs.org
  13 Delivered-To: ccan@ozlabs.org
  14 X-Greylist: delayed 2513 seconds by postgrey-1.31 at ozlabs;
  15         Wed, 18 Mar 2009 16:50:38 EST
  16 Received: from mxpm.isis.unc.edu (mxp3.isis.unc.edu [152.2.2.161])
  17         by ozlabs.org (Postfix) with ESMTP id 72C75DDEFA
  18         for <ccan@ozlabs.org>; Wed, 18 Mar 2009 16:50:37 +1100 (EST)
  19 Received: from smtp.unc.edu (smtpsrv3.isis.unc.edu [152.2.2.251])
  20         by mxp3.isis.unc.edu (8.14.3/8.14.3) with ESMTP id n2I58gVL008719
  21         for <ccan@ozlabs.org>; Wed, 18 Mar 2009 01:08:42 -0400
  22 Received: from [192.168.5.124] (pool-173-73-173-234.washdc.fios.verizon.net
  23         [173.73.173.234]) (authenticated bits=0)
  24         by smtp.unc.edu (8.14.3/8.14.3) with ESMTP id n2I58fex014904
  25         (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT)
  26         for <ccan@ozlabs.org>; Wed, 18 Mar 2009 01:08:42 -0400 (EDT)
  27 Message-ID: <49C081CA.5040501@email.unc.edu>
  28 Date: Wed, 18 Mar 2009 01:08:26 -0400
  29 From: "Timothy B. Terriberry" <tterribe@email.unc.edu>
  30 User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US;
  31         rv:1.8.1.11) Gecko/20071216 SeaMonkey/1.1.7
  32 MIME-Version: 1.0
  33 To: ccan@ozlabs.org
  34 References: <c3cfaf5e0901190756x569da515s823fe4c7bd99c22a@mail.gmail.com>
  35         <200902040051.54761.rusty@rustcorp.com.au>
  36         <c3cfaf5e0902051926m6a2793e5pfdef62040becb4e7@mail.gmail.com>
  37         <200903181452.14263.rusty@rustcorp.com.au>
  38 In-Reply-To: <200903181452.14263.rusty@rustcorp.com.au>
  39 Content-Type: multipart/mixed;
  40   boundary="------------050107030903080507030408"
  41 X-Proofpoint-Virus-Version: vendor=fsecure engine=1.12.7400:2.4.4, 1.2.40,
  42         4.0.166 definitions=2009-03-18_01:2009-03-13, 2009-03-18,
  43         2009-03-17 signatures=0
  44 X-Proofpoint-Spam-Details: rule=uncdefault_notspam policy=uncdefault score=0
  45         spamscore=0 ipscore=0 phishscore=0 bulkscore=0 adultscore=0
  46         classifier=spam adjust=0 reason=mlx engine=5.0.0-0811170000
  47         definitions=main-0903170259
  48 X-Mailman-Approved-At: Thu, 19 Mar 2009 09:38:09 +1100
  49 Subject: Re: [ccan] Mathematics Module
  50 X-BeenThere: ccan@ozlabs.org
  51 X-Mailman-Version: 2.1.11
  52 Precedence: list
  53 List-Id: "If perl can, maybe ccan?" <ccan.ozlabs.org>
  54 List-Unsubscribe: <https://ozlabs.org/mailman/options/ccan>,
  55         <mailto:ccan-request@ozlabs.org?subject=unsubscribe>
  56 List-Archive: <http://ozlabs.org/pipermail/ccan>
  57 List-Post: <mailto:ccan@ozlabs.org>
  58 List-Help: <mailto:ccan-request@ozlabs.org?subject=help>
  59 List-Subscribe: <https://ozlabs.org/mailman/listinfo/ccan>,
  60         <mailto:ccan-request@ozlabs.org?subject=subscribe>
  61 Sender: ccan-bounces+rusty=rustcorp.com.au@ozlabs.org
  62 Errors-To: ccan-bounces+rusty=rustcorp.com.au@ozlabs.org
  63 Status: R
  64 X-Status: NT
  65 X-KMail-EncryptionState:
  66 X-KMail-SignatureState:
  67 X-KMail-MDN-Sent:
  68
  69 This is a multi-part message in MIME format.
  70 --------------050107030903080507030408
  71 Content-Type: text/plain; charset=ISO-8859-1
  72 Content-Transfer-Encoding: 7bit
  73
  74 Some of this stuff seems a little trivial to include, but if we're going
  75 to do so...
  76
  77 The result of nCr is guaranteed to be an integer after each iteration,
  78 and so there's a) no reason to keep a separate numerator and denominator
  79 and b) no reason to do a minimum of nine (9!) divisions every iteration.
  80 Only a single gcd() is needed, and even that can often be skipped,
  81 requiring only 2-3 divisions per iteration. This is illustrated in
  82 choose.c (attached). You can easily add the check for the smaller r (_m
  83 in this implementation), upgrade the types to long, etc., as desired. If
  84 one really cared about speed, the divisions could be entirely replaced
  85 by multiplications and a small lookup table, since m and n are known to
  86 have a very limited range (or the result will overflow).
  87
  88 Also included are a gcd() implementation without tail recursion and
  89 egcd(), the "extended" gcd, as well as a nice illustration of the use of
  90 egcd, a Chinese Remainder Theorem solver for systems of linear
  91 congruences. I don't have time to format these into a nice module with
  92 test cases right now, but feel free to take what you want and throw the
  93 rest in "junk". The code is (C) 1998-2001, except crt.c, which is (C)
  94 1999-2001, 2007. I'm releasing it here under the LGPLv2 license.
  95
  96 --------------050107030903080507030408
  97 Content-Type: application/x-bzip;
  98  name="nmbrthry.tar.bz2"
  99 Content-Transfer-Encoding: base64
 100 Content-Disposition: inline;
 101  filename="nmbrthry.tar.bz2"
 102
 103 QlpoOTFBWSZTWdZHi4IAD0t/nv/QAEB7//+/u2e8i//v/+4AQAAIAAGEgAAIYA798qVUUAAX
 104 YNLYVbSAAAKUAAKAAAAcGQaNAGTTENNBkGIYQNAaMTEaAAAaCjTEBIHqAADT1D1AAGgAAAAA
 105 HBkGjQBk0xDTQZBiGEDQGjExGgAAEmpFNRlNT/RGVN5U2mptT2qabUNqBiAyAADI8o09Eaeo
 106 cGQaNAGTTENNBkGIYQNAaMTEaAAAKkgggjQEZAQ0Mk0jU8U9Gmo0eU9TxpQZkaMjU2p9kDMf
 107 V9wivZ4gOTqn7wGbkUSRyyEA29t22fDfGfQl4fTBxbWtte1ra3VtnHjpqhvvQpVKhSqEVIKR
 108 LJUUqJKoTo/kUfaDk4lVemwZOWUGotQXUVLMhTZuP2LZrGWV8VUvVp+8vi9qmK+7B9lHCkb8
 109 yh+x2DE6DhzYZfIlH8CYGAmOI79GiqE3TyGgJLphSoomCpKsFYI2q9VcqgvgHEGoRkZPGHjJ
 110 EPGFISTMkk5VIkWMIRGIiJBBA4Azk8QZLHw6jf1iIqr1V3v3GzlSqccvyMsyOsZOTBs8jevS
 111 x14Jnzbf7BdiquJnDPRuUFDECxCenKDoOj2LHN2GS1m5RQvG5gwvTJRZSjGWtjotTKdCmkra
 112 1zR2WMOLDZO/l1fN/gS6tPBoaZ/hjO+8WfuNsr1W1l+bHI8OsHGWE1GrTp1YJYREyyZy9c+9
 113 06L2EwM23ZlsZHez1GrkMsnNtTYp+I1dzbgd9+DetnZ19jswy4v49VuWeh1as99KWZVItzcv
 114 4OHU2NU2UwpS/jfhl3FcWnucnCbFVw8TZ6Xm3aNODbUpG6zBTuMObVevJ4WdrfFbrMeJyWYM
 115 u9exZ2vzPQaaDLzpeqbU6b9JqYdDXa15etqjbqnhs9Lg8vzYbvFpvbV4tF/fm+DusbKaWmzR
 116 Z1s+FJlSYdZo61zc1UaX+7XL0rqYd7LUazNZ5utbmw5JRolpuWZxGNd9Noycmprj5ltmkd6y
 117 yUp0KFa7vHl7GiaKb8d27rV62nG9lU4G63TDm0qlk1wzGb4XS5Te6rLP9NTLlMG11mGmsmJV
 118 3FlePq4plnV6VOQ4ztVdxVS3FKU6+7orHFqp+lqxe1dP420bLOA4Ow0ceGzJS97t7WS/tVY6
 119 kpPiP5yVVZ7nZ1b4cztTr9nPkUPzsfHs+dfJrZ+e0zcx9vk6lzLNnE2qSXcH5l09cMAxOYN8
 120 stkO0dgpOUT+rWB14IblgbmNKNyIWNRDAccl0GhVDEVrnXMgqKsDDMgCpeGEQLTuHyqrF+lu
 121 5p/Jn2p0Tsy4P6newwulHD4Kw7vExPXdop7DtX2eHx1bM8LrRTgUXlusfJ3vm7XRk6MuDfKe
 122 Dzb697/Wn3fNwtanCca1Rx4Wy59HYcO/14e3+zUu7X9vG7V713oYasOCzlkr0rNVLtWz23q9
 123 6epbu4bM0qtbcWvRdsqcGLVTBq3bJJbw7PW5QLVahD52yLYc3q5QrQoqqlV12tdh3LOOmo/V
 124 /0hvIlzY7JPmutRVxV37HvLzFKxUrK6ope0sNEidcP3dB0DT5bkDJA4z6YYpeBeBfOi1JmMU
 125 xcQqqqGERAk5F7ANET46LJVgN7ZYWjeoHKZEtgiVB9NJzzDOnO0mjXWHNwcKZxfN22s4VFr7
 126 1rrr9bbZW3XZuzBnfbdeGkLbPbnbVhui+l7VritrYqaXb5q0mZo1cxfRto14cbcMWqG25qq3
 127 k73e+T7HoYMj26UWez6Gcfebb8frKx8/XqW46WybNaipIn1UGcEMDoozesCoanJMcM0gWdxy
 128 MRrJYXMhdZtVcufBtl2dNWeVVzWtpni9fsiij+vi22w/a8el2WHh5AGLdgB2I2TRmskWLA4Z
 129 rqYCndoy0AGfVM9pzCk2aR4ODHeyyaTMh4P5nu2lrwKGdIFoUdpLznlMS7C//pSyXgsfVlcv
 130 aySqk20aLsLe/YiIgi8M5gcWMeTQbeutHWJOHeKDmAQRDu/a1bIZc9XMlbcKuHhAbNyJChhk
 131 48K3zdvvriqqqrsdpRSl5NNtrXXve5VH59b3eP04uupUpScIeZL0onepLa0hVLGnpw4leWf/
 132 jS2M2y0s1kqqoqt6Fk9HsWjef7fX2z/y9SdHyWfPN3E+hY2SjAw/6rv0UkmVlvfKTJtCjFw/
 133 UVJio+M2H6tGEoZ4xyVKikor5R+uJwTmazsPA4Kh30i1IfP6vv3YorytYm8Re0loVP0HttPp
 134 lSOpJHZzV61lnm+HfZShdqdT7ut56CmrVNZH5CgwUnxKm7fdwbNaj9dWqScrLnptHtrJT2Fm
 135 aoqVVFi1L2VXp8sQwVJz5qUVULiriyhd5ZeXz2ybz9nX3p4JiOB+EsWKjhC2FzpcWdA6p/77
 136 fxdXuPfT4OKXovFpwMT0MNF7ZYq1o/Sz9OEY30XlypGpUl4stO1imMJxZLKZqqNFrDgzoviZ
 137 SlKsJmh8IyqGLRs2Zi74MN12cLHzF2V1MReqil5O3Y63EfTxaFsYcrGLy9E4tZ3DRJiJvPV8
 138 fY973uKHBNfP3VVO1MqrsVNKSn/edS6YPJNLfr8WZP2mTl7TymVnkpW89bRJ/zoc5qeT1ihS
 139 72XNrVKpeHJXrhkuYkruxlV9pOKlnNd6ptG3XJUKVI7xSUntOvRUTjmG57FAh5QSQoQWlQRJ
 140 RSUEQnGB+YaNbpKTVRLzYxE3MJb3vcVLrlCr1Ve5T3VW5suh6jk2YsdFmk+07nhFUZrBKECx
 141 Ko3aIMSeZJEQiCRGFJSiooqCqSlT8uLSXlHmqS0WSYlxdKYF7JkqGqup9T22WUs+3qWilxbu
 142 qfj+3K+ivvbFi1F9ftuvUrl8eDVnSn5R87sr5ye4WOpTAu+g+o5yc6k+VVXF85xeSeL1KUUw
 143 /k1jxqJz+uRnmmZg7BQ4zP3LWu28jxSyyUpZaftdnbYuvFFVVJHXJI417zeP45k5KqKoqlSH
 144 dJpHM9RiGHepu8dEnFPom81qST3LaJ5OD+1SnxegcFKKpVKYPqT5cPwT4tJpqmF3UnFkeGBq
 145 UpSZXcJLl9EsLDgh2MjdVivpKRSjwcZ10edfZ6vwZYZXtYqvx/VrWJmnBGqycJ5JSx1o65HV
 146 DuJeYk/fWOW9/fTrVLVnMr3VeZkVSg3cFKkOKXsepcqyrFeD8ZdaqrTJdR0NLMFrMXkWXKWm
 147 JaKlB50WYGy0XzE1nRZKWbSGCpF5eKMSli65iUNmyrCx+VN5QtKEMBwN0KKN0PR6P+5+rz9W
 148 93ddauvRPkSQxgaUrslQ6dvbCWVJKVFSopaWQtJoixdPi9Z8UPO8o+r4sLVMv65JPrHBD2Ki
 149 GELxH46UOUicJFIuZlKWRaH1w+Q+1TpPmdsPsScCdb/iPVJzcUpRntdWP+XZ3MUYI6lpD4LL
 150 +qyGSp6YlTpLFLJVRFKMvqaOnqNDWa1FUopSo1iXnqt7P00s+/e1OFkm0jaTxTdfjwkkyXg5
 151 pbzk8YelmT0QrpCvQ4N2G9ouscJeWpPYqNdWVl2imlMMmcsVmxfweOl8LFkUosKa7sfzat1l
 152 lPu09H3u/wpO/1cxUa81Op0VTRYstKU1OmYaNdYz0lTWrFklkwURu310KLpW0M/iRuaUXllI
 153 3ZbMWpL0ReSpZKTxcdV2FehgWaV4KXSpmsVU0sWU405WVaLSzTp0vzorposnBrD11aOuRwQ2
 154 YRySn4Yp4nVqNpNHCRD8KklKhd/nHfeTKinVC0mpspUqU71lpTKyWqrWFq8Ki6koVFUqUmMw
 155 nL3dFlRTJ0kkzGqd3uUnwWTxs4fr1xj0ecHKf8OiS52vAtPaPbQ7ke6c3wYlk81PyK5+uST3
 156 dQxP5w/pDrf0+iQ0DTzffT0Kemzzz540M+frmgo9tSSlQe06nkWvzaLSXzFUvwbLHfQnrko8
 157 Io/YU5q/o6/979nHjdrOZbZWy8Onro7O0qFuos+UqWfQs7Iau1FvsHCk93tOx950SxD/+LuS
 158 KcKEhrI8XBA=
 159 --------------050107030903080507030408
 160 Content-Type: text/plain; charset="us-ascii"
 161 MIME-Version: 1.0
 162 Content-Transfer-Encoding: 7bit
 163 Content-Disposition: inline
 164
 165 _______________________________________________
 166 ccan mailing list
 167 ccan@ozlabs.org
 168 https://ozlabs.org/mailman/listinfo/ccan
 169
 170 --------------050107030903080507030408--