Re: [R] bitwise addition

From: Marc Schwartz <MSchwartz_at_mn.rr.com>
Date: Mon 15 May 2006 - 05:43:17 EST

On Sat, 2006-05-13 at 23:53 -0400, jim holtman wrote:
> Using the algorithm in the reference
> www.everything2.com/index.pl?node_id=449702 and the 'bitops' package,
> here is some code that will select the numeric values with a specified
> number of bits. It takes less than 12 seconds to select from 21-bit
> numbers. If I had more memory, I would expect that for 25-bit numbers
> it would take about 200 seconds to compute the indices.
>
> > mask1 <- 0x55555555
> > mask2 <- 0x33333333
> > mask4 <- 0x0f0f0f0f
> > mask8 <- 0x00ff00ff
> > mask16 <- 0x0000ffff
> > require(bitops)
> [1] TRUE
> > x <- 0:(2^21 - 1) # test all number with 21 bits
> > system.time({
> + x <- bitAnd(x, mask1) + bitAnd(bitShiftR(x, 1), mask1)
> + x <- bitAnd(x, mask2) + bitAnd(bitShiftR(x, 2), mask2)
> + x <- bitAnd(x, mask4) + bitAnd(bitShiftR(x, 4), mask4)
> + x <- bitAnd(x, mask8) + bitAnd(bitShiftR(x, 8), mask8)
> + x <- bitAnd(x, mask16) + bitAnd(bitShiftR(x, 16), mask16)
> + })
> [1] 10.40 0.87 11.82 NA NA
> > # print the first 10 numbers
> > which(x == 9)[1:10] - 1 # account for sequence starting at zero
> [1] 511 767 895 959 991 1007 1015 1019 1021 1022

Very nice Jim. I was not aware of the bitops package.

BTW, FWIW: x <- 0:(2^25 - 1)

> system.time({

+  x <- bitAnd(x, mask1) + bitAnd(bitShiftR(x, 1), mask1)
+  x <- bitAnd(x, mask2) + bitAnd(bitShiftR(x, 2), mask2)
+  x <- bitAnd(x, mask4) + bitAnd(bitShiftR(x, 4), mask4)
+  x <- bitAnd(x, mask8) + bitAnd(bitShiftR(x, 8), mask8)
+  x <- bitAnd(x, mask16) + bitAnd(bitShiftR(x, 16), mask16)
+  })

[1] 52.803 9.016 67.885 0.000 0.000

> str(x)

num [1:33554432] 0 1 1 2 1 2 2 3 1 2 ...

> object.size(x)
[1] 268435484

That compares to:

  [1] 4.880 0.700 5.706 0.000 0.000

for x <- 0:(2^21 - 1) on my system. So the timing seems less than linear as the size of 'x' increases.

Now, if Nameeta indeed requires the binary representations of the values as character vectors as she noted, she will likely have to be cautious in approaching that process from a RAM and time efficiency perspective.

I tried doing this on my system in one step and quickly ran out of RAM (2 Gb) and swap (1 Gb) as I watched both go to 0% free on gkrellm. So this will likely need to be done stepwise to avoid multiple internal copying of large objects.

Here is one approach.

For example:

# Using x <- 0:(2^25 - 1)
> length(which(x == 9))
[1] 2042975

So, first converting the above values to binary, again using digitsBase() from sfsmisc:

> system.time(z <- digitsBase(which(x == 9) - 1, ndigits = 25))
[1] 22.125 5.189 29.080 0.000 0.000

> str(z)

basedInt [1:25, 1:2042975] 0 0 0 0 0 0 0 0 0 0 ... - attr(*, "class")= chr "basedInt"
- attr(*, "base")= num 2

# z is 400 Mb
> object.size(z)

[1] 408595348

# Now paste() the results into single character vectors
> system.time(mat <- matrix(apply(z, 2, paste, collapse = ""),

              ncol = 1))
[1] 349.762 4.196 391.827 0.000 0.000

> str(mat)

chr [1:2042975, 1] "0000000000000000111111111" ...


# mat is 128 Mb
> object.size(mat)

[1] 130750524

> head(mat, 10)

      [,1]

[1,] "0000000000000000111111111"
[2,] "0000000000000001011111111"
[3,] "0000000000000001101111111"
[4,] "0000000000000001110111111"
[5,] "0000000000000001111011111"
[6,] "0000000000000001111101111"
[7,] "0000000000000001111110111"
[8,] "0000000000000001111111011"

[9,] "0000000000000001111111101"
[10,] "0000000000000001111111110"

Note however, that even after forcing gc() I get:

> gc()

           used (Mb) gc trigger (Mb) max used (Mb) Ncells 2271012 60.7 7706096 205.8 9405098 251.2 Vcells 93910018 716.5 193159857 1473.7 170025834 1297.2

Before gc(), gkrellm was showing 12% RAM free, after it shows 38% free.

So even with 2 Gb of RAM, the above is pushing the envelope of practicality I suspect.

HTH, Marc Schwartz



R-help@stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html Received on Mon May 15 05:47:51 2006

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.1.8, at Mon 15 May 2006 - 08:10:08 EST.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.