Re: [Jscheme-user] Arbitrary precision integers

[Ken A. <kan...@bb...>]

At 02:56 PM 1/5/2004 -0500, bor...@ko... wrote:
>Hi all,
>
>This is more of a question to Jscheme developers. Are there any plans to
>support arbitrary precision integers? A simple way would be by using the
>java.math.BigInteger class. I read a bit the source code and it doesn't
>seem such a huge modification. However, this is probably not the most
>efficient implementation. For example, I tried something like this:
>
>(define (fact n) 
>  (let ((one (BigInteger. "1")))
>        (if (= 0 (.intValue n)) 
>             one
>             (fact (.mulitply n (.subtract n one))))))

Your definition is wrong.  Try this:
(define fact 
    (let ((one (BigInteger. "1")))
      (lambda (n)
        (if (= 0 (.intValue n)) 
            one
            (.multiply n (fact (.subtract n one)))))))

>And then I had to stop the evaluation of (fact (BigInteger "1000")) after
>20 minutes on a 1.6GHZ, 512MB laptop. Scheme implementations that I've
>played with in the past would return the result almost right away on much
>slower machines.
>
>Anyway, the concern is really practical, not just for the sake of it. I'm
>getting integer overflows while trying to solve a very practical problem. 

Have you tried using longs?

>If you have thought about this and have ideas about what to do, I am
>willing to help with coding, testing etc. 
>
>BTW, I think Jscheme is great!

Thanks!

I've been thinking there should be an extension library that would let you do this.  Perhaps we can develop one.
Here's a simple one that provides big integers and big rational numbers, i've been playing with.

(import "java.math.BigInteger")
(load "elf/basic.scm")

(define (big n)
  (if (instanceof n BigInteger.class) n
      (BigInteger. (.toString n))))

(define (bop1 f) (lambda (n) (f (big n))))
(define (bop2 f) (lambda (a b) (f (big a) (big b))))
(define babs (bop1 .abs))

(define b+  (bop2 .add))
(define b/ (bop2 .divide))
(define b= (bop2 .equals))
(define bgcd (bop2 .gcd))
(define bmax (bop2 .max))
(define bmin (bop2 .min))
(define mod (bop2 .mod))
(define b* (bop2 .multiply))
(define bminus (bop1 .negate))
(define (bexp n e) (.pow (big n) e))
(define bremainder (bop2 .remainder))
(define bsignum (bop1 .signum))
(define b- (bop2 .subtract))

(define (Rat n d)
  (let* ((n (big n))
         (d (big d))
         (g (.gcd n d)))
    (cons (.divide n g) (.divide d g))))

;;; Structure and Interpration o Computer Programs, Second Edition, p. 84.

(define numer car)
(define denom cdr)
(define (r+ x y)
  (Rat (b+ (b* (numer x) (denom y))
           (b* (numer y) (denom x)))
       (b* (denom x) (denom y))))

(define (r- x y)
  (Rat (b- (b* (numer x) (denom y))
           (b* (numer y) (denom x)))
       (b* (denom x) (denom y))))

(define (r* x y)
  (Rat (b* (numer x) (numer y))
       (b* (denom x) (denom y))))

(define (r/ x y)
  (Rat (r* (numer x) (denom y))
       (r* (denom x) (numer y))))

(define (r= x y)
  (b= (b* (numer x) (denom y))
      (b* (numer y) (denom x))))