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)))
