Working with Ruby
Hi, I am Jan. This is my old Ruby blog. I still post about Ruby, but I now do it on idiosyncratic-ruby.com. You should also install Irbtools to improve your IRB.

Converting decimal to binary integers: custom methods vs. to_i [Update]

August 2009, ruby · ruby1-8 · ruby1-9 · thoughts · jruby

At my last entry, a question arose about what is the most efficient way to convert integers between the bases 2 and 10: either using built-in ruby methods (and even do lightweight string-operations) or calculating it manually. I had to find out ;). So I have written a little benchmark program, which does the conversion in three different ways:

  1. using built-in to_i-magic
  2. calculating it by hand
  3. using sprintf

It stops the time each method needs to get the fastest. The result might be surprising. [Update: improved the custom methods]

In most cases, the built-in functions are slightly faster than the custom methods. The following extract shows the output on my machine, using Ruby 1.9.1p0:

Speed test: using to_i and to_s - decimal to binary...0.15s Speed test: using to_i and to_s - binary to decimal...0.08s Methods ran correctly? yes Speed test: calculating it - decimal to binary...0.31s Speed test: calculating it - binary to decimal...0.11s Methods ran correctly? yes Speed test: using sprintf - decimal to binary...0.16s Speed test: using sprintf - binary to decimal...0.10s Methods ran correctly? yes

In Ruby 1.8.6p368, everything is a little bit slower:

Speed test: using to_i and to_s - decimal to binary...0.22s Speed test: using to_i and to_s - binary to decimal...0.30s Methods ran correctly? yes Speed test: calculating it - decimal to binary...0.33s Speed test: calculating it - binary to decimal...0.30s Methods ran correctly? yes Speed test: using sprintf - decimal to binary...0.26s Speed test: using sprintf - binary to decimal...0.32s Methods ran correctly? yes

An explanation for this is, that the built-in methods can calculate the result using native C, which often beats ruby implementations.

.to_i / .to_s is better than sprintf is better than calculating it manually.

I have also tried JRuby (1.3.1 —1.9) and the manual conversion was even worse:

Speed test: using to_i and to_s - decimal to binary...0.15s Speed test: using to_i and to_s - binary to decimal...0.26s Methods ran correctly? yes Speed test: calculating it - decimal to binary...0.34s Speed test: calculating it - binary to decimal...0.41s Methods ran correctly? yes Speed test: using sprintf - decimal to binary...0.13s Speed test: using sprintf - binary to decimal...0.33s Methods ran correctly? yes

Without the 1.9 switch, most times improve (but are still worse at calculating it in Ruby):

Speed test: using to_i and to_s - decimal to binary...0.13s Speed test: using to_i and to_s - binary to decimal...0.30s Methods ran correctly? yes Speed test: calculating it - decimal to binary...0.37s Speed test: calculating it - binary to decimal...0.35s Methods ran correctly? yes Speed test: using sprintf - decimal to binary...0.13s Speed test: using sprintf - binary to decimal...0.27s Methods ran correctly? yes

Also notable: in JRuby, the winner is – sprintf

Here is the code I used for benchmarking:

converting_bases 
 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

# # # # # # # # #
# Test, which way to convert the base of an integer from 2 to 10 and vice versa,
# is the most efficient one

class ST
  attr_reader :dec_to_bin, :bin_to_dec, :correct

  # abstract methods
  def desc; end
  def speedtest_dec_to_bin; end
  def speedtest_bin_to_dec; end

  # stop time
  def timer(&proc)
    started_at = Time.now
    yield if block_given?
    stopped_at = Time.now

    res = stopped_at - started_at
    puts '%.2fs' % res
    res
  end

  # do the testing
  def speedtest( to_test = (42**42)**42*(42**42)**42 )
    @cur = to_test

    print 'Speed test: ' << desc << ' - decimal to binary...'
    @dec_to_bin = speedtest_dec_to_bin

    print 'Speed test: ' << desc << ' - binary to decimal...'
    @bin_to_dec = speedtest_bin_to_dec

    puts 'Methods ran correctly? ' << ((@correct = (@cur == to_test)) ? 'yes' : 'no')
  end
end

# ruby's .to_i and .to_s functions
class ST::To_i < ST
  def desc; 'using to_i and to_s'; end

  def speedtest_dec_to_bin
    timer{ @cur = @cur.to_s(2).to_i }
  end

  def speedtest_bin_to_dec
    timer{ @cur = @cur.to_s.to_i(2) }
  end
end

# calculate it
class ST::Calc < ST
  def desc; 'calculating it'; end

  def speedtest_dec_to_bin
    timer{
      res = []

      while @cur != 0
#       res << (@cur.odd? ? '1' : '0')
#       @cur >>= 1
        new_cur = @cur >> 1
        res << ((@cur == new_cur << 1) ? '0' : '1')
        @cur = new_cur
     end
     @cur = res.reverse.join.to_i
    }
  end

  def speedtest_bin_to_dec
    timer{
      res = 0
      cur_exp = 1
      cur_missing_1 = 0 # counts the 0s for shifting
      @cur.to_s.reverse.each_byte{ |set|
        if set == 49
          cur_exp <<= cur_missing_1
          res += cur_exp
          cur_missing_1 = 1
        else
          cur_missing_1 += 1
        end
      }
      @cur = res
    }
  end
end

# using sprintf
class ST::Sprintf < ST
  def desc; 'using sprintf'; end

  def speedtest_dec_to_bin
    timer{ @cur = ('%b' % @cur.to_s).to_i }
  end

  def speedtest_bin_to_dec
    timer{ @cur = ('%d' % ('0b' + @cur.to_s)).to_i }
  end
end

# for the lazy ones ;)
def ST.demo
  jl1 = ST::To_i.new
  jl1.speedtest

  jl2 = ST::Calc.new
  jl2.speedtest

  jl3 = ST::Sprintf.new
  jl3.speedtest
end

# let's start
ST.demo

If you know a way to improve the manual calculation, please let me know ;)

Creative Commons License