From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Mikael Djurfeldt Newsgroups: gmane.lisp.guile.devel Subject: Re: Nearly finished (re)integrating GMP for bignums. Date: Mon, 03 Mar 2003 14:13:06 +0100 Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Message-ID: References: <87heb9pjni.fsf@raven.i.defaultvalue.org> <87r8adihxe.fsf@zagadka.ping.de> <87vfz6nw8i.fsf@raven.i.defaultvalue.org> Reply-To: djurfeldt@nada.kth.se NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: main.gmane.org 1046697552 9331 80.91.224.249 (3 Mar 2003 13:19:12 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 3 Mar 2003 13:19:12 +0000 (UTC) Cc: guile-devel@gnu.org Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 18ppqA-0002P9-00 for ; Mon, 03 Mar 2003 14:18:47 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18ppq0-0006y5-00 for guile-devel@m.gmane.org; Mon, 03 Mar 2003 08:18:36 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18pplz-0005bv-00 for guile-devel@gnu.org; Mon, 03 Mar 2003 08:14:27 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18pplO-0005Mg-00 for guile-devel@gnu.org; Mon, 03 Mar 2003 08:13:51 -0500 Original-Received: from kvast.blakulla.net ([213.212.20.77]) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18ppkt-00057b-00 for guile-devel@gnu.org; Mon, 03 Mar 2003 08:13:19 -0500 Original-Received: from dyna224-223.nada.kth.se ([130.237.224.223] helo=linnaeus) by kvast.blakulla.net with esmtp (Exim 3.36 #1 (Debian)) id 18ppkh-0007LT-00; Mon, 03 Mar 2003 14:13:07 +0100 Original-Received: from mdj by linnaeus with local (Exim 3.36 #1 (Debian)) id 18ppkg-0002ZP-00; Mon, 03 Mar 2003 14:13:06 +0100 Original-To: Rob Browning In-Reply-To: <87vfz6nw8i.fsf@raven.i.defaultvalue.org> (Rob Browning's message of "Wed, 26 Feb 2003 23:11:41 -0600") User-Agent: Gnus/5.090015 (Oort Gnus v0.15) Emacs/21.2 Original-cc: djurfeldt@nada.kth.se Original-cc: Marius Vollmer X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1b5 Precedence: list List-Id: Developers list for Guile, the GNU extensibility library List-Help: List-Post: List-Subscribe: , List-Archive: List-Unsubscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.devel:2016 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:2016 Rob Browning writes: > Mikael Djurfeldt writes: > >> Ideally, the bignum code would use the pluggable source of random bits >> in random.c and the GMP generators would be provided as optional >> plugins for random.c. Rob, is this possible? > > For now, I think I'd like to consider just translating the existing > scm_c_random_bignum to manipulate mpz_t values rather than the old > bignum digits. > > If you (or anyone else) is familiar with this function, could you > explain the critical parts? I can probably figure out how to > translate it eventually by just looking at the code, but that process > would probably go a lot faster if I had an overview. Sorry for not answering earlier. I've been away on vacation. The logic is very simple: SCM scm_c_random_bignum (scm_t_rstate *state, SCM m) Takes a random state (source of random bits) and a bignum m. Returns a bignum b, 0 <= b < m. It does this by allocating a bignum b with as many base 65536 digits as m, filling b with random bits (in 32 bit chunks) up to the most significant 1 in m, and, finally checking if the resultant b is too large (>= m). If too large, we simply repeat the process again. (It is important to throw away all generated random bits if b >= m, otherwise we'll end up with a distorted distribution.) Here's the step-by-step description: 1. Compute a 32-bit bitmask for use when filling bits into the most significant long word in b's bit space. A combination of conditionals and an 8-bit lookup table (scm_masktab) is used. 2. Allocate b and assign the bit space address to the variable "bits". 3.1 Generate the most significant bits using the mask. 3.2 Fill up the rest of the bit space. 3.3 Use scm_i_normbig to cut away leading zeros and/or convert to inum. 3.4 If b >= m, go to 3.1. 4. return b > I'd like to know things like how critical it is that it operate on > 16-bit chunks -- what interdependencies does that create, etc. No dependencies, except that you'd obviously have to adjust the conditionals for generating the mask. > If possible, it'll probably be faster and easier to work with larger > chunks when manipulating the mpz_t's. I suggest you work with 32-bit chunks since this is what is returned by scm_the_rng.random_bits (state). Best regards, Mikael _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel