[gambit-list] newbie: bitwise and arithmetic runtime speed for u64
Bradley Lucier
lucier at purdue.edu
Wed Apr 1 13:15:01 EDT 2020
On 3/31/20 3:50 PM, Paolo Montrasi wrote:
> I am asking here for an advice in improving runtime speed crunching
> bitwise operations on u64 integers since I have no experience using
> scheme and Gambit.
> Looking at the documentation I see that fixnum is providing some help
> but I apparently u64 integers are not "compatible" with fixnum operations
>
> > (fixnum? 18446744073709551615)
> #f
>
> Can you share suggestions for my next exercise
That may be possible using some of Gambit's low-level, internal, unsafe,
very-bad-indeed routines for manipulating bignum "adigits" (for
"addition digits", although they're the size used for many other
things), which are 64 bits, unsigned, on 64-bit machines. (They're only
14 bits wide in the universal backend, though.)
You'll find these routines in _num.scm:
;;; Sets x[i] to x[i] & y[j] (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-and! x i y j))
;;; Sets x[i] to ~x[i] & y[j] (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-andc1! x i y j))
;;; Sets x[i] to x[i] & ~y[j] (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-andc2! x i y j))
;;; Sets x[i] to ~(x[i] ^ y[j]) (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-eqv! x i y j))
;;; Sets x[i] to x[i] | y[j] (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-ior! x i y j))
;;; Sets x[i] to ~(x[i] & y[j]) (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-nand! x i y j))
;;; Sets x[i] to ~(x[i] | y[j]) (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-nor! x i y j))
;;; Sets x[i] to !x[i] (accessing x as adigits)
(define-prim (##bignum.adigit-bitwise-not! x i))
;;; Sets x[i] to ~x[i] | y[j] (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-orc1! x i y j))
;;; Sets x[i] to x[i] | ~y[j] (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-orc2! x i y j))
;;; Sets x[i] to x[i] ^ y[j] (accessing x and y as adigits)
(define-prim (##bignum.adigit-bitwise-xor! x i y j))
There's also
(define-prim (##bignum.make k x complement?)
which makes a new bignum with k adigits, copying x if it's given, and
complementing things if the last argument is #t. It may be easier to
just call
(define-prim (##bignum.copy x)
(##bignum.make (##bignum.adigit-length x) x #f))
Using one of
(define ##bignum.adigit-ones (##fixnum->bignum -1)) ;; the 0th
adigit is all ones
(define ##bignum.adigit-zeros (##fixnum->bignum 0)) ;; the 0th
adigit is all zeros
as a starter.
Now, ##bignum.adigit-ones and ##bignum.adigit-zeros are unnormalized
bignums, as could be many other results one can get by using these
routines that manipulate adigits, so I wouldn't try to print them using
the usual library routines, but this could get you started.
Brad
More information about the Gambit-list
mailing list