[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gcl-devel] Re: contiguous blocks exhausted
From: |
Camm Maguire |
Subject: |
[Gcl-devel] Re: contiguous blocks exhausted |
Date: |
12 Dec 2003 10:20:42 -0500 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 |
Greetings!
Matt Kaufmann <address@hidden> writes:
> ; 1,462,993 cons cells, 1,061,547,136 other bytes, 0 static bytes
^^^^^^^^^^^^^
If this means what I think it means, then GCL will have to be compiled
with a larger number of maximum pages. Right now that is set at 128M
by default. This is easy to do.
It might not be a bad idea to hardcode the default maxpages to 4G on
32bit systems, the maximum amount addressable. For 64bit systems, I
don't know what a sane default would be. This would no affect the
default image size much.
> To be fair to GCL, I don't think things would go any better in C without some
> work. The numbers involved far exceed 2^64.
>
> So, unfortunately, my suggestion is either to switch to Allegro Common Lisp if
> you can, or else to think about an algorithm that keeps the numbers in the GCL
> fixnum range.
>
Fixnum's are of course much faster, but there is something else you
can do for a dramatic speedup on computations like this:
(si::set-gmp-allocate-relocatable t)
I'm considering making this the default. It depends on a local patch
to the gmp library which ideally I'd like to be supported upstream,
but what we have now does appear to work.
> Let me know if you have any questions.
>
If anyone would like me to try these options and report back, I can do
that.
Take care,
> -- Matt
> Date: Thu, 11 Dec 2003 20:45:51 -0700 (MST)
> From: Cynthia Campos <address@hidden>
> X-Sender: <address@hidden>
> Content-Type: TEXT/PLAIN; charset=US-ASCII
> Reply-To: address@hidden
> Sender: address@hidden
> X-Listprocessor-Version: 8.2.10/020311/17:52 -- ListProc(tm) by CREN
>
> Hi all,
>
> this is the first time I've written to the helplist. I'm trying to
> implement the AKS primality testing algorithm and to do so, I need to
> implement a function computes the remainder of the binary expansion of a
> polynomial of the form (x + a)^n divided by another polynomial of the form
> (x^r -1). I also have to compute the remainder of (x^n + a) divided by
> (x^r - 1). When this is done, I need to check that the mod of each
> element by n is equal.
>
> After many different implementations, I keep getting the following error:
>
> Error: Contiguous blocks exhausted.
> Currently, 26670 pages are allocated.
> Use ALLOCATE-CONTIGUOUS-PAGES to expand the space.
> Fast links are on: do (si::use-fast-links nil) for debugging
> [SGC for 0 CONTIGUOUS-BLOCKS pages..(2498 writable)..(T=10).GC finished]
>
> For example, I got this error when i ran the following:
>
> (lastclause 2 487 349)
>
> However, when I restarted acl2 and loaded everything, I tried this same
> function and it was successful.
>
> I'm including the code that I've written. The majority of the functions
> are written for the specific case of dividing by a polynomial of the form
> (X^r -1). I'm sure I'll have to prove theorems about some of the
> assumptions I've made, but I'm barely in the beginning stages.
>
> In order to reproduce the error, you can just run
> (lastclause 10 487 349)
>
> The factorial, binomial and mod-gcd books also need to be included.
>
> Any ideas would sure be of help because I'm unsure if this is a
> programming error.
>
> Thanks,
> Cynthia
>
> (defun nat-p (n)
> (if (and (integerp n)
> (> n 0))
> t
> nil))
>
> (defun bin-expansion (x y k n acc)
> (declare (xargs :measure (nfix (1+ (- n k)))))
> (if (and (integerp k) (integerp n) (<= 0 k) (<= k n))
> (bin-expansion x y (1+ k) n (cons (* (choose k n)
> (expt x k)
> (expt y (- n k)))
> acc))
> acc))
>
> (defun be (a n)
> (bin-expansion 1 a 0 n nil))
>
> (defun changelist (key new left right)
> (cond ((zp key) (cons left (cons (- (car right) new) (cdr right))))
> ((and (>= key 0)
> (listp left)
> (listp right))
> (changelist (1- key)
> new
> (cons (car right) left)
> (cdr right)))))
>
> (defun nl (pair)
> (if (consp pair)
> (append (reverse (car pair)) (cdr pair))
> nil))
>
> (defun polymod (pr cfl r)
> (cond ((and (zp pr)
> (consp cfl))
> (cdr (nl (changelist r (* (car cfl) -1) nil cfl))))
> ((and (consp cfl)
> (nat-p pr)
> (> pr 0))
> (polymod (- pr 1)
> (cdr (nl (changelist r (* (car cfl) -1) nil cfl)))
> r))
> (:else -900)))
> (defun comparelistswithmod (lh index rhi ra n length)
> (cond ((null lh) 199)
> ((and (int= length 1)
> (consp lh)
> (int= (mod (car lh) n) ra))
> (comparelistswithmod (cdr lh) (1+ index) rhi ra n (1- length)))
> ((and (consp lh)
> (not (int= index rhi))
> (zp (mod (car lh) n)))
> (comparelistswithmod (cdr lh) (1+ index) rhi ra n (1- length)))
> ((and (consp lh)
> (int= index rhi)
> (int= (mod (car lh) n) 1))
> (comparelistswithmod (cdr lh) (1+ index) rhi ra n (1- length)))
> (t -10)))
>
> (defun lastclause (a n r)
> (cond ((zp a) 899)
> ((or (not (nat-p a))
> (not (nat-p n))
> (not (nat-p r))) -3)
> ((> (comparelistswithmod
> (polymod (- n r) (be a n) r)
> 1 (- r (- n r)) a n r)
> 0)
> (lastclause (- a 1) n r))
> (:else -899)))
>
>
>
>
--
Camm Maguire address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
- [Gcl-devel] Re: contiguous blocks exhausted,
Camm Maguire <=