Re: [racket-users] chaining operations on bignum not scalable
On Sunday, July 30, 2017 at 12:35:09 AM UTC+2, Ryan Culpepper wrote: > On 07/29/2017 02:48 PM, rom cgb wrote: > > Hi, > > > > Probably due to all operations not being in-place, chaining operations on > > bignums is very costful. > > > > for example, using bitwise-bit-field[1] on bignums is atrocious. > > > > I also tried > > > >(define (reverse-bits n) > > (for/fold ([reversed 0]) > >([i (in-range (integer-length n))]) > >(bitwise-ior (bitwise-arithmetic-shift-left reversed 1) > > (or (and (bitwise-bit-set? n i) 1) 0 > > Here's a version that runs in about a sixth of the time for me. > > First, parameterize your function by a "chunk length": > >;; reverse-chunk : Nat Nat -> Nat >;; Return a natural from the lowest len bits of n, reversed. >(define (reverse-chunk n len) > (for/fold ([reversed 0]) >([i (in-range len)]) >(bitwise-ior (arithmetic-shift reversed 1) > (if (bitwise-bit-set? n i) 1 0 > > Then create an outer loop that processes one chunk at a time: > >(define CHUNK 32) ;; should be less than fixnum size > >;; reverse-bits : Nat -> Nat >(define (reverse-bits n) > (let loop ([n n] [nlen (integer-length n)]) >(cond [(< nlen CHUNK) > (reverse-chunk n nlen)] > [else > (bitwise-ior >(loop (arithmetic-shift n (- CHUNK)) (- nlen CHUNK)) >(arithmetic-shift > (reverse-chunk (bitwise-bit-field n 0 CHUNK) CHUNK) > (- nlen CHUNK)))]))) > > > [...] Having in-place operations would help > > > > (define (reverse-bits n) > > (for/fold ([reversed 0]) > > ([i (in-range (integer-length n))]) > > (bitwise-arithmetic-shift-left! reversed 1) > > (bitwise-ior! reversed (or (and (bitwise-bit-set? n i) 1) 0 > > > > What do you think? > > I believe the chunking version would still be faster than the in-place > version. Both are quadratic: the chunking version constructs > 2*nlen/CHUNK intermediate bignums, and the in-place version would do > nlen 1-bit left shifts. But the 2/CHUNK advantage in the constants is > significant. > > Ryan Thank you but your loop is not tail recursive and freeze on large bignums (millions bits). Also, bitwise operations are much faster when n is a power of two. (define (reverse-bits n) (for/fold ([reversed 0]) ([i (in-range (integer-length n))]) (bitwise-ior (bitwise-arithmetic-shift-left reversed 1) (or (and (bitwise-bit-set? n i) 1) 0 (define nbits (expt 2 (expt 2 18))) ;; 262 145 bits (void (time (reverse-bits nbits))) (collect-garbage) (void (time (reverse-bits (sub1 nbits cpu time: 7 real time: 7 gc time: 0 cpu time: 6051 real time: 6055 gc time: 106 Growing the numbers of bits vs growing of time (for ([i (in-list (for/list ([n (in-range 10)]) (- (expt 2 (* 10 n)) 1)))]) (printf "~A " (integer-length i)) (collect-garbage) (void (time (reverse-bits i 10 cpu time: 855 real time: 855 gc time: 11 20 cpu time: 3508 real time: 3509 gc time: 56 30 cpu time: 8419 real time: 8422 gc time: 337 40 cpu time: 15590 real time: 15583 gc time: 776 50 cpu time: 23475 real time: 23475 gc time: 935 60 cpu time: 33464 real time: 33447 gc time: 1318 -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] chaining operations on bignum not scalable
On 07/29/2017 02:48 PM, rom cgb wrote: Hi, Probably due to all operations not being in-place, chaining operations on bignums is very costful. for example, using bitwise-bit-field[1] on bignums is atrocious. I also tried (define (reverse-bits n) (for/fold ([reversed 0]) ([i (in-range (integer-length n))]) (bitwise-ior (bitwise-arithmetic-shift-left reversed 1) (or (and (bitwise-bit-set? n i) 1) 0 Here's a version that runs in about a sixth of the time for me. First, parameterize your function by a "chunk length": ;; reverse-chunk : Nat Nat -> Nat ;; Return a natural from the lowest len bits of n, reversed. (define (reverse-chunk n len) (for/fold ([reversed 0]) ([i (in-range len)]) (bitwise-ior (arithmetic-shift reversed 1) (if (bitwise-bit-set? n i) 1 0 Then create an outer loop that processes one chunk at a time: (define CHUNK 32) ;; should be less than fixnum size ;; reverse-bits : Nat -> Nat (define (reverse-bits n) (let loop ([n n] [nlen (integer-length n)]) (cond [(< nlen CHUNK) (reverse-chunk n nlen)] [else (bitwise-ior (loop (arithmetic-shift n (- CHUNK)) (- nlen CHUNK)) (arithmetic-shift (reverse-chunk (bitwise-bit-field n 0 CHUNK) CHUNK) (- nlen CHUNK)))]))) [...] Having in-place operations would help (define (reverse-bits n) (for/fold ([reversed 0]) ([i (in-range (integer-length n))]) (bitwise-arithmetic-shift-left! reversed 1) (bitwise-ior! reversed (or (and (bitwise-bit-set? n i) 1) 0 What do you think? I believe the chunking version would still be faster than the in-place version. Both are quadratic: the chunking version constructs 2*nlen/CHUNK intermediate bignums, and the in-place version would do nlen 1-bit left shifts. But the 2/CHUNK advantage in the constants is significant. Ryan -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. #lang racket/base (provide (all-defined-out)) ;; reverse-bits0 : Nat -> Nat ;; The original version (ported R6RS -> Racket) (define (reverse-bits0 n) (for/fold ([reversed 0]) ([i (in-range (integer-length n))]) (bitwise-ior (arithmetic-shift reversed 1) (if (bitwise-bit-set? n i) 1 0 ;; ;; reverse-chunk : Nat Nat -> Nat ;; Return an integer from the lowest len bits of n, reversed. (define (reverse-chunk n len) (for/fold ([reversed 0]) ([i (in-range len)]) (bitwise-ior (arithmetic-shift reversed 1) (if (bitwise-bit-set? n i) 1 0 ;; (define CHUNK 32) ;; reverse-bits : Nat -> Nat (define (reverse-bits n) (let loop ([n n] [nlen (integer-length n)]) (cond [(< nlen CHUNK) (reverse-chunk n nlen)] [else (bitwise-ior (loop (arithmetic-shift n (- CHUNK)) (- nlen CHUNK)) (arithmetic-shift (reverse-chunk (bitwise-bit-field n 0 CHUNK) CHUNK) (- nlen CHUNK)))]))) ;; Useful for REPL debugging ;; (define (b n) (number->string n 2)) ;; (define (r s) (b (reverse-bits (string->number s 2 (define (test n) (unless (equal? (reverse-bits n) (string->number (list->string (reverse (string->list (number->string n 2 2)) (error 'test "failed on ~s" n))) ;; ;; random-bignum : -> Nat ;; Make a bignum with size between 1 and 100 bytes. (define (random-bignum) (define nbytes (+ 1 (random 100))) (for/fold ([n 0]) ([i (in-range nbytes)]) (+ (arithmetic-shift n 8) (random 256 ;; For deterministic testing: (random-seed 17) (define SIZE #e5e4) (define ns (for/list ([_ (in-range SIZE)]) (random-bignum))) ;; Make sure reverse-bits is correct: (for-each test ns) ;; Benchmarks: (printf "Original version:\n") (collect-garbage) (for ([i 4]) (time (for-each reverse-bits0 ns))) (printf "Chunking version:\n") (collect-garbage) (for ([i 4]) (time (for-each reverse-bits ns)))
Re: [racket-users] chaining operations on bignum not scalable
Il giorno 29 luglio 2017, alle ore 20:48, rom cgb ha scritto: >Hi, >Probably due to all operations not being in-place, chaining operations on >bignums is very costful. >for example, using bitwise-bit-field[1] on bignums is atrocious. >I also tried > (define (reverse-bits n) > (for/fold ([reversed 0]) > ([i (in-range (integer-length n))]) > (bitwise-ior (bitwise-arithmetic-shift-left reversed 1) > (or (and (bitwise-bit-set? n i) 1) 0 >but it's not much better. Having in-place operations would help > (define (reverse-bits n) > (for/fold ([reversed 0]) > ([i (in-range (integer-length n))]) > (bitwise-arithmetic-shift-left! reversed 1) > (bitwise-ior! reversed (or (and (bitwise-bit-set? n i) 1) 0 >What do you think? Personally, I think that mutable integers is a feature we are better doing without. If you need a mutable vector, they are already in the language. If you want 1-bit per element mutable vectors, then there are packages available implementing this data structure. Cheers -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] chaining operations on bignum not scalable
Hi, Probably due to all operations not being in-place, chaining operations on bignums is very costful. for example, using bitwise-bit-field[1] on bignums is atrocious. I also tried (define (reverse-bits n) (for/fold ([reversed 0]) ([i (in-range (integer-length n))]) (bitwise-ior (bitwise-arithmetic-shift-left reversed 1) (or (and (bitwise-bit-set? n i) 1) 0 but it's not much better. Having in-place operations would help (define (reverse-bits n) (for/fold ([reversed 0]) ([i (in-range (integer-length n))]) (bitwise-arithmetic-shift-left! reversed 1) (bitwise-ior! reversed (or (and (bitwise-bit-set? n i) 1) 0 What do you think? [1] https://github.com/racket/r6rs/blob/master/r6rs-lib/rnrs/arithmetic/bitwise-6.rkt#L89 -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
