Re: Integer to byte string - Speed improvements

On 8/31/06, Phrogz <gavin@xxxxxxxxxxxx> wrote:
I'm writing code that needs to store an integer as a sequence of bytes.
Array#pack works for 1-, 2-, and 4-byte integers, but I want to be able
to support Bignums as well.

I have working code below. I'm happy with it. However, I thought I'd
pose the question to the list: how much faster can you make the below
code run?

# The natural log of 2 (for base-2 logarithms)
Math::LOG2 = Math.log( 2 )

No need for these, I'm on a campaign to let integers be integers.


class Integer
# Converts the integer into a string, where the value of each
character
# is a byte in the bit representation of the integer.
# Low-order bytes appear first in the string.
#
# If the number of characters is not specified, the fewest number of
# characters that can represent the integer is used.
#
#
def to_bytestring( num_chars=nil )

replace these four lines:
unless num_chars
bits_needed = Math.log( self ) / Math::LOG2

By the way, this won't work for negative integers. Dealing with
negative numbers provides some interesting questions which I'll ignore
for now.

num_chars = ( bits_needed / 8.0 ).ceil
end

with

raise RangeError.new("Can't convert negative integer to bytestring")
num_chars ||= self.size

if pack_code = { 1=>'C', 2=>'S', 4=>'L' }[ num_chars ]
[ self ].pack( pack_code )
else
I might try getting rid of the multiplication
(0...(num_chars)).map{ |i|
(( self >> i*8 ) & 0xFF ).chr
}.join
end

With something like:

result = []
i = self
until i == 0
result << (i & 0xFF).chr
i >>= 8
end

So following those ideas:
rick@frodo:/public/rubyscripts$ cat tobytes.rb
class Integer
def to_bytestring(num_chars=nil)
raise RangeError.new("Can't convert negative number to
bytestring") if self < 0
num_chars ||= self.size
mask = 0xFF << (8 * num_chars - 1)
while (self & mask) == 0
mask >>= 8
num_chars -= 1
end

result = []
bits_left = self
until bits_left == 0
result << (bits_left & 0xFF).chr
bits_left >>= 8
end
result.join
end

# Creates an integer from a byte string.
# See Integer#to_bytestring for more information.
def self.from_bytestring( str )
val = 0
index = 0
str.each_byte{ |b|
val += b << 8 * index
index += 1
}
val
end

end

[
0x48,
0x6948,
0x646c726f57206f6c6c6548,
0x217962755220666f207463657073612074656577732061207369206d756e676942
].each{ |i| puts i, i.to_bytestring, '' }


rick@frodo:/public/rubyscripts$ ruby tobytes.rb
72
H

26952
Hi

121404708493354166158910792
Hello World

3876042760240808297111079005855559646422331404814505579794973210389374306838850
Bignum is a sweet aspect of Ruby!



--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

.

Relevant Pages

  • [SUMMARY] Symbolify (#169)
    ... the five quiz-permitted characters give easy access to ... def symbolify ... I'm going to examine the next string in a few steps, ... Dana's `symbolify` function is very similar to Alex's solution above: ...
    (comp.lang.ruby)
  • Fwd: Please Forward: Ruby Quiz Submission
    ... Subject: Please Forward: Ruby Quiz Submission ... it could be mistakenly interpreted as valid string 'a" ... I also do not check for control characters in strings, ... def split_stateful ...
    (comp.lang.ruby)
  • Integer to byte string - Speed improvements
    ... to support Bignums as well. ... # Low-order bytes appear first in the string. ... # characters that can represent the integer is used. ... def self.from_bytestring ...
    (comp.lang.ruby)
  • String buffer
    ... The append method appends a string to the end of the string buffer. ... The readmethod reads and removes n characters from the beginning ... def push_first: ...
    (comp.lang.python)
  • String buffer
    ... The append method appends a string to the end of the string buffer. ... The readmethod reads and removes n characters from the beginning ... def push_first: ...
    (comp.lang.python)