Ruby内部で学ぶ10進数変換処理

## Rubyでの10進数変換処理

Rubyでは、`to_i` メソッドに基底（2進数の場合は、2）を引数に指定して、実行することにより10進数に変換が出来ます。

```ruby
irb(main):001> "100".to_i(2)
=> 4
```

右桁から計算するのが一番直感的ですが、

```ruby

  target_str = '101'
  reversed_target_str = target_str.reverse!
  base = 2
  total_decimal = 0
  
  reversed_target_str.each_char.with_index do |target_char, index|
    target_int = target_char.to_i
    
    decimal_value = target_int * (base ** index)
    
    total_decimal += decimal_value
  end
```

Ruby内部ではどのように計算されているのでしょうか。

## Rubyのソースコード確認
### Rubyで書かれている処理

`string.rb`の`to_i` メソッドを確認しても、10進数への変換処理が書かれていないです。

```string.rb
  # Returns the result of interpreting leading characters in +self+
  # as an integer in the given +base+ (which must be in (2..36)):
  #
  #   '123456'.to_i     # => 123456
  #   '123def'.to_i(16) # => 1195503
  #
  # Characters past a leading valid number (in the given +base+) are ignored:
  #
  #   '12.345'.to_i   # => 12
  #   '12345'.to_i(2) # => 1
  #
  # Returns zero if there is no leading valid number:
  #
  #   'abcdef'.to_i # => 0
  #   '2'.to_i(2)   # => 0
  def to_i(base = 10) end
```

`string.rbs` を参照することにより、`string.c`に処理が書かれていることが分かります。

```string.rbs
  # <!--
  #   rdoc-file=string.c
  #   - to_i(base = 10) -> integer
  # -->
  # Returns the result of interpreting leading characters in `self` as an integer
  # in the given `base` (which must be in (0, 2..36)):
  #
  #     '123456'.to_i     # => 123456
  #     '123def'.to_i(16) # => 1195503
  #
  # With `base` zero, string `object` may contain leading characters to specify
  # the actual base:
  #
  #     '123def'.to_i(0)   # => 123
  #     '0123def'.to_i(0)  # => 83
  #     '0b123def'.to_i(0) # => 1
  #     '0o123def'.to_i(0) # => 83
  #     '0d123def'.to_i(0) # => 123
  #     '0x123def'.to_i(0) # => 1195503
  #
  # Characters past a leading valid number (in the given `base`) are ignored:
  #
  #     '12.345'.to_i   # => 12
  #     '12345'.to_i(2) # => 1
  #
  # Returns zero if there is no leading valid number:
  #
  #     'abcdef'.to_i # => 0
  #     '2'.to_i(2)   # => 0
  #
  def to_i: (?int radix) -> Integer
```

### C言語で実装されている処理

rubyでの`to_i`は`rb_str_to_i`を呼び出していることが分かります。

```string.c
rb_define_method(rb_cString, "to_i", rb_str_to_i, -1);
```

```string.c
/*
 *  call-seq:
 *    to_i(base = 10) -> integer
 *
 *  Returns the result of interpreting leading characters in +self+
 *  as an integer in the given +base+ (which must be in (0, 2..36)):
 *
 *    '123456'.to_i     # => 123456
 *    '123def'.to_i(16) # => 1195503
 *
 *  With +base+ zero, string +object+ may contain leading characters
 *  to specify the actual base:
 *
 *    '123def'.to_i(0)   # => 123
 *    '0123def'.to_i(0)  # => 83
 *    '0b123def'.to_i(0) # => 1
 *    '0o123def'.to_i(0) # => 83
 *    '0d123def'.to_i(0) # => 123
 *    '0x123def'.to_i(0) # => 1195503
 *
 *  Characters past a leading valid number (in the given +base+) are ignored:
 *
 *    '12.345'.to_i   # => 12
 *    '12345'.to_i(2) # => 1
 *
 *  Returns zero if there is no leading valid number:
 *
 *    'abcdef'.to_i # => 0
 *    '2'.to_i(2)   # => 0
 *
 */

static VALUE
rb_str_to_i(int argc, VALUE *argv, VALUE str)
{
    int base = 10;

    if (rb_check_arity(argc, 0, 1) && (base = NUM2INT(argv[0])) < 0) {
        rb_raise(rb_eArgError, "invalid radix %d", base);
    }
    return rb_str_to_inum(str, base, FALSE);
}
```

`rb_str_to_inum`内に行くと、最終的には
`util.c`の`ruby_scan_digits`関数に辿り着きます。

```util.c
const signed char ruby_digit36_to_number_table[] = {
    /*     0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f */
    /*0*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*1*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*2*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*3*/  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1,
    /*4*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
    /*5*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
    /*6*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
    /*7*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
    /*8*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*9*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*a*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*b*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*c*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*d*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*e*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
    /*f*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
};

NO_SANITIZE("unsigned-integer-overflow", extern unsigned long ruby_scan_digits(const char *str, ssize_t len, int base, size_t *retlen, int *overflow));
unsigned long
ruby_scan_digits(const char *str, ssize_t len, int base, size_t *retlen, int *overflow)
{
    RBIMPL_ASSERT_OR_ASSUME(base >= 2);
    RBIMPL_ASSERT_OR_ASSUME(base <= 36);

    const char *start = str;
    unsigned long ret = 0, x;
    unsigned long mul_overflow = (~(unsigned long)0) / base;

    *overflow = 0;

    if (!len) {
        *retlen = 0;
        return 0;
    }

    do {
        int d = ruby_digit36_to_number_table[(unsigned char)*str++];
        if (d == -1 || base <= d) {
            --str;
            break;
        }
        if (mul_overflow < ret)
            *overflow = 1;
        ret *= base;
        x = ret;
        ret += d;
        if (ret < x)
            *overflow = 1;
    } while (len < 0 || --len);
    *retlen = str - start;
    return ret;
}
```

n進数を10進数に変換する処理だけを抜き出す

```ruby
do {
    int d = ruby_digit36_to_number_table[(unsigned char)*str++];
    // 一部割愛
    ret *= base;
    // 一部割愛
    ret += d;
    // 一部割愛
} while (len < 0 || --len);
```

2進数 "100"を10進数に変換する処理を考えてみます。

`int d = ruby_digit36_to_number_table[(unsigned char)*str++];`
`ruby_digit36_to_number_table`配列は、ASCII文字をその対応する整数値にマッピングします。
'0'は0に、'1'は1にマッピングされます。

`ret *= base;`
ここで、現在の結果に基数（この場合は2）を掛けます。次の桁に移動するための重みを付けています。

`ret += d;`
ここで、新たに取得した数値を現在の結果に加えます。

このループは、文字列のすべての文字に対して実行されます。
例えば、"100"という文字列では、ループは3回実行されます。
各イテレーション後の変数の値は次のようになります

```
ret: 0
base: 2

1回目：
d: 1
ret *= base: 0
ret += d: 1

2回目：
d: 0
ret *= base: 2
ret += d: 2

3回目：
d: 0
ret *= base: 4
ret += d: 4
```

となり、4を返します。

n進数を10進数に変換する処理は
Rubyでは、左桁から重みを掛けていって、計算していることが分かります。

## まとめ

Rubyでは10進数への変換処理は、左桁から計算していること（逐次変換法）が分かります。
右桁からの計算と違い、ループの途中までの計算結果を内部保存しておけば、

100
1001
10011
などリアルタイムに次の桁を入力された場合にも対応出来そうです。