Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #6905

Re: Conversion of a number from string to vector<int>

Followups directed to: comp.lang.c++

Show all headers | View raw

Juha Nieminen wrote:

> Anonymous <anonymous@no.net> wrote:
>> Do anyone want to write an efficient function for converting a
>> non-negative arbitrary-precision number in base 10 from string to
>> std::vector<int>. The vector must represent the number in base B, where
>> B is int and arbitrary. End each element in the vector represents the
>> digit of the number in base B. The most significative digit must be on
>> the top of the vector. The code must be portable and must not rely on
>> types greater than int. Only the std library is allowed.
> 
>   Maybe it's not the most efficient solution that could be, but it should
> be efficient enough, as well as easy: Interpret the last character in the
> string and convert it to its equivalent value between 0 and 9 (IIRC the
> standard even guarantees that the characters '0' through '9' will always
> be contiguous, so you can do a simple "character - '0'") and assign it to
> a variable. Then take the second-to-last character and add it likewise to
> the character, but multiplied by 10, then the third-to-last, multiplied by
> 100 and so on. After each such addition check if the value in the variable
> exceeds B, and if so, add the variable value module B to the vector,
> divide the variable by B, and then start over (adding the next character,
> then the next one multiplied by 10 and so on).
> 
>   (Disclaimer: I haven't tested the algorithm in any way.)

Consider going from base 10 to base 3:

  1 ->  1
  10 ->  101
  100 -> 10201
  ...

As you can see, powers of 10 always end in 1. That implies:

  1 ->  ..1
  11 -> ..2
  111 -> ..0
  1111 -> ..1
  11111 -> ..2
  ...

I.e.: the last digit after conversion depend on _all_ digits of the input. 
So, the step ".. add the variable value module B to the vector ..." cannot 
just mean to append that value mod B and move on to the next entry in the 
vector.

The Art of Computer Programming Vol 2, Chapter 4.4 by D.E. Knuth deals with 
radix conversion; and your proposed method is very close to Method 1a. For 
the problem at hand, it can be specialized as follows:

Given u = (...cba) in base 10, you compute U = (...xyz) in base B by

    z = u mod B
    y = floor(u/B) mod B
    x = floor( floor(u/B) / B ) mod B

The computations on the RHS need to be carried out in multi-precision 
arithmetic. This can be done in base 10 arithmetic as u is given in base 10. 
This requires writing B in base 10, which is much simpler as B fits in an 
int.


Best,

Kai-Uwe Bux

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Conversion of a number from string to vector<int> Anonymous <anonymous@no.net> - 2011-06-18 19:59 +0200
  Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-18 20:08 +0100
    Re: Conversion of a number from string to vector<int> Anonymous <anonymous@no.net> - 2011-06-18 23:55 +0200
      Re: Conversion of a number from string to vector<int> Victor Bazarov <v.bazarov@comcast.invalid> - 2011-06-18 18:26 -0400
    Re: Conversion of a number from string to vector<int> Juha Nieminen <nospam@thanks.invalid> - 2011-06-19 06:15 +0000
      Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-19 08:02 +0100
        Re: Conversion of a number from string to vector<int> Anonymous <anonymous@no.net> - 2011-06-19 12:19 +0200
          Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-19 16:07 +0100
            Re: Conversion of a number from string to vector<int> Anonymous <anonymous@no.net> - 2011-06-19 17:50 +0200
            Re: Conversion of a number from string to vector<int> Juha Nieminen <nospam@thanks.invalid> - 2011-06-20 06:12 +0000
              Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-20 09:57 +0100
        Re: Conversion of a number from string to vector<int> Juha Nieminen <nospam@thanks.invalid> - 2011-06-20 06:09 +0000
          Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-20 09:48 +0100
          Re: Conversion of a number from string to vector<int> Ian Collins <ian-news@hotmail.com> - 2011-06-20 20:59 +1200
            Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-20 10:17 +0100
              Re: Conversion of a number from string to vector<int> Lasse Reichstein Nielsen <lrn.unread@gmail.com> - 2011-06-20 22:47 +0200
                Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-20 22:05 +0100
  Re: Conversion of a number from string to vector<int> Ian Collins <ian-news@hotmail.com> - 2011-06-19 08:35 +1200
  Re: Conversion of a number from string to vector<int> Juha Nieminen <nospam@thanks.invalid> - 2011-06-19 06:23 +0000
    Re: Conversion of a number from string to vector<int> Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-19 12:14 +0200
    Re: Conversion of a number from string to vector<int> Anonymous <anonymous@no.net> - 2011-06-19 13:13 +0200
      Re: Conversion of a number from string to vector<int> Pete Becker <pete@versatilecoding.com> - 2011-06-19 11:42 -0400
        Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-19 20:54 +0100
        Re: Conversion of a number from string to vector<int> Anonymous <anonymous@no.net> - 2011-06-19 23:06 +0200
          Re: Conversion of a number from string to vector<int> Pete Becker <pete@versatilecoding.com> - 2011-06-19 17:18 -0400
          Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-20 00:11 +0100
            Re: Conversion of a number from string to vector<int> "Paul" <pchristor@yahoo.co.uk> - 2011-06-20 00:32 +0100
    Re: Conversion of a number from string to vector<int> Juha Nieminen <nospam@thanks.invalid> - 2011-06-20 06:18 +0000
  Re: Conversion of a number from string to vector<int> Sam <sam@email-scan.com> - 2011-06-21 06:05 -0500

csiph-web