Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

g > Subject: Re: [racket] Math - factorial.rkt, binomial.rkt and > memoization > > On 04/09/2013 11:41 AM, Hendrik Boom wrote: > > On Tue, Apr 09, 2013 at 08:26:31PM +0200, Jos Koot wrote: > >> Would it be possible to use > >> <http://en.wikipedia.org/wiki/Stirli

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

On 04/09/2013 11:41 AM, Hendrik Boom wrote: On Tue, Apr 09, 2013 at 08:26:31PM +0200, Jos Koot wrote: Would it be possible to use Stirling's approximation for a fast inexact first approximation for factorials of very big numbers and from

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

On Tue, Apr 09, 2013 at 08:26:31PM +0200, Jos Koot wrote: > Would it be possible to use > Stirling's > approximation for a fast inexact first approximation for factorials of very > big numbers and from there quickly get to an exact factorial

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

Would it be possible to use Stirling's approximation for a fast inexact first approximation for factorials of very big numbers and from there quickly get to an exact factorial? (if exactness is required) I don't know for I haven't thought th

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

On Tue, Apr 9, 2013 at 3:30 PM, Pierpaolo Bernardi wrote: while the for version should be almost all big x big. > oops, no. The for version should be almost all fix x big. Here's a count considering also the type of the result of the multiplication: > (fact 100) #hash(((fix fix -> fix) . 4

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

On Tue, Apr 9, 2013 at 2:51 PM, Laurent wrote: > On Tue, Apr 9, 2013 at 2:42 PM, Matthew Flatt wrote: > >> (for/product ([p (in-range (+ m 1) (+ n 1))]) p) > > > > But I don't fully understand why a simple (for/product ([p (in-range 1 > (add1 n))]) p) is as fast as the iota variants. > I don't

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

On Tue, Apr 9, 2013 at 2:42 PM, Matthew Flatt wrote: > (for/product ([p (in-range (+ m 1) (+ n 1))]) p) This fact/for variant is a clear winner: > (time (void (fact/for 100))) cpu time: 6948 real time: 6956 gc time: 964 > (time (void (factorial 100))) cpu time: 9936 real time: 9951 gc

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

At Tue, 9 Apr 2013 14:02:27 +0200, Laurent wrote: > But if you write all 10 cases, aren't the lists constructed anyway before > calling `*'? Applying `*' to N arguments doesn't construct a list of N arguments. There's a continuation frame that accumulates the N arguments, but in a way that tends t

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

On Tue, Apr 9, 2013 at 2:02 PM, Laurent wrote: > But if you write all 10 cases, aren't the lists constructed anyway before > calling `*'? > I'll leave the answer to someone who knows exactly how the compiler works. Intuitively, I thought my case should be better, but measuring them gives no app

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

But if you write all 10 cases, aren't the lists constructed anyway before calling `*'? On Tue, Apr 9, 2013 at 2:00 PM, Pierpaolo Bernardi wrote: > Or, more lispy: > > ;; from included; to excluded. > (define (mult from to) > (case (- to from) > ((0) 1) > ((1) from) > ((2) (* from

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

Or, more lispy: ;; from included; to excluded. (define (mult from to) (case (- to from) ((0) 1) ((1) from) ((2) (* from (+ from 1))) ((3) (* from (+ from 1) (+ from 2))) ;; ... (else (let ((middle (quotient (+ from to) 2))) (* (mult from middle) (mult middle t

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

But why generate lists which are immediately discarded? ;; from excluded; to included (define (mult from to) (case (- to from) ((0) 1) ((1) to) ((2) (* (- to 1) to)) ((3) (* (- to 2) (- to 1) to)) ;; ... (else (let ((middle (quotient (+ from to) 2))) (* (mult

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

On Mon, Apr 8, 2013 at 9:34 PM, Bradley Lucier wrote: > (define (iota m n) > (let loop ((result '()) > (n (- n 1))) >(if (<= m n) > (loop (cons n result) > (- n 1)) > result))) > > (define (partial-factorial m n) > ;; computes the product (m+1) * ..

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

On Mon, Apr 8, 2013 at 9:34 PM, Jens Axel Søgaard wrote: > > Would it make sense to use memoization more broadly for the definition > of the factorial > > in the math lib, maybe with a `provide'd parameter to control how many > values can be > > memoized? > > An interesting question. First of all

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

> Would it make sense to use memoization more broadly for the definition of the factorial > in the math lib, maybe with a `provide'd parameter to control how many values can be > memoized? An interesting question. First of all it seems that especially binomial can be improved. Second I think there

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

On Apr 8, 2013, at 3:11 PM, users-requ...@racket-lang.org wrote: I would never recommend against using GMP for bignum code, but I use code like this for factorial, based on the idea of binary splitting: (define (iota m n) (let loop ((result '()) (n (- n 1))) (if (<= m n)

Re: [racket] Math - factorial.rkt, binomial.rkt and memoization

Hi Laurent, I am curious to see how fast the libgmp versions of factorial and binomial are on your computer. Om my computer libgmp is much faster than the Racket one. Since the libgmp versions converts a Racket bignum into a mpz, there is some overhead, so a proper solution would be to use