Velocity Reviews > C++ > Conversion of a number from string to vector<int>

# Conversion of a number from string to vector<int>

Anonymous
Guest
Posts: n/a

 06-18-2011
Hello,

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.

For example:

std::vector<int> v = f("253", 127);

would give

v[0] = 126
v[1] = 1

thanks.

Paul
Guest
Posts: n/a

 06-18-2011

"Anonymous" <(E-Mail Removed)> wrote in message
news:itip2s\$nkn\$(E-Mail Removed)...
> Hello,
>
> 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.
>
> For example:
>
> std::vector<int> v = f("253", 127);
>
> would give
>
> v[0] = 126
> v[1] = 1
>
>

http://www.cplusplus.com/reference/c.../cstdlib/atoi/

HTH

Ian Collins
Guest
Posts: n/a

 06-18-2011
On 06/19/11 05:59 AM, Anonymous wrote:
> Hello,
>
> 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.

Homework?

Have you looked at strtol and friends?

--
Ian Collins

Anonymous
Guest
Posts: n/a

 06-18-2011
> http://www.cplusplus.com/reference/c.../cstdlib/atoi/

As I said, the requirements are:

- arbitrary precision
- portability with use of std lib in case
- conversion from const char* to std::vector<int>, each element is a
digit in base B

atoi() does not accomplish all the above requirements, none of them to
be precise.

Victor Bazarov
Guest
Posts: n/a

 06-18-2011
On 6/18/2011 5:55 PM, Anonymous wrote:
>> http://www.cplusplus.com/reference/c.../cstdlib/atoi/

>
> As I said, the requirements are:
>
> - arbitrary precision
> - portability with use of std lib in case
> - conversion from const char* to std::vector<int>, each element is a
> digit in base B
>
> atoi() does not accomplish all the above requirements, none of them to
> be precise.

http://lmgtfy.com/?q=arbitrary+preci...on+from+string

V
--

Juha Nieminen
Guest
Posts: n/a

 06-19-2011
Paul <(E-Mail Removed)> 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.
>>
>> For example:
>>
>> std::vector<int> v = f("253", 127);
>>
>> would give
>>
>> v[0] = 126
>> v[1] = 1
>>
>>

> http://www.cplusplus.com/reference/c.../cstdlib/atoi/

Your incompetence and comprehension capabilities never cease to amuse.

Care to actually give us actual code on how atoi() can be used for this

Juha Nieminen
Guest
Posts: n/a

 06-19-2011
Anonymous <(E-Mail Removed)> 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.)

Paul
Guest
Posts: n/a

 06-19-2011

"Juha Nieminen" <(E-Mail Removed)> wrote in message
news:4dfd93f0\$0\$2848\$(E-Mail Removed)...
> Paul <(E-Mail Removed)> 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.
>>>
>>> For example:
>>>
>>> std::vector<int> v = f("253", 127);
>>>
>>> would give
>>>
>>> v[0] = 126
>>> v[1] = 1
>>>
>>>

>> http://www.cplusplus.com/reference/c.../cstdlib/atoi/

>
> Your incompetence and comprehension capabilities never cease to amuse.
>
> Care to actually give us actual code on how atoi() can be used for this
>

He seems to be trying to convert a string to an int, this is what atoi does.

Kai-Uwe Bux
Guest
Posts: n/a

 06-19-2011
Juha Nieminen wrote:

> Anonymous <(E-Mail Removed)> 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

Anonymous
Guest
Posts: n/a

 06-19-2011
Paul ha scritto:
> He seems to be trying to convert a string to an int, this is what atoi
> does.

Basically, I am improving a constructor for big integers passed as
strings by the user. The class provides basic math operations in
arbitrary precision. It is everything done. When I implemented the
constructor initially, every char of the string was a digit in a
vector<char>. This was not really efficient. Factorial("1000") required
about 70s on my machine. So I decided to "group" more chars into ints,
as (almost) many chars as possible, that is by building a vector<int>
from the given number. This actually is 7 times faster than before, but
is still not perfect, since not all the possible bits of the integers
are used. The reason is that each digit in the vector<int> is in base B,
where B is a power of 10, not of two:

class BIGINT {
// Bitset must be signed (for diff. operation).
typedef signed int Bitset;

// vector is 25 times faster than list or twice than deque.
typedef std::vector<Bitset> Sequence;

// -1 to avoid overflows in sum.
static const int DGTS = std::numeric_limits<Bitset>::digits10 - 1;

BIGINT(const char* p = 0) {
// ...
size_t l = strlen(p);
for (size_t i = 0; i < l {
Bitset x = 0, f = 1;
for (int j = 0; j < DGTS && i < l; j++, i++, f *= 10)
x += (p[l - i - 1] - '0') * f;
module.push_back(x);
}
// ...
}
}