Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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.
 
Reply With Quote
 
 
 
 
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
>
>

There is a function called atoi that may help you.
http://www.cplusplus.com/reference/c.../cstdlib/atoi/

HTH

 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
Anonymous
Guest
Posts: n/a
 
      06-18-2011
> There is a function called atoi that may help you.
> 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.
 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      06-18-2011
On 6/18/2011 5:55 PM, Anonymous wrote:
>> There is a function called atoi that may help you.
>> 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
--
I do not respond to top-posted replies, please don't ask
 
Reply With Quote
 
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
>>
>>

> There is a function called atoi that may help you.
> 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
task? (Hint: It can't.)
 
Reply With Quote
 
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.)
 
Reply With Quote
 
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
>>>
>>>

>> There is a function called atoi that may help you.
>> 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
> task? (Hint: It can't.)
>

He seems to be trying to convert a string to an int, this is what atoi does.
What is incompetent about trying to provide a helpfull suggestion?

 
Reply With Quote
 
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
 
Reply With Quote
 
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.
> What is incompetent about trying to provide a helpfull suggestion?


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);
}
// ...
}
}
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
conversion of real number into binary number rajeswari01 Hardware 1 07-15-2011 05:30 AM
conversion of real number into binary number rajeswari01 Hardware 0 10-15-2010 12:30 AM
Conversion from Hexadecimal number into Decimal number dharmdeep@gmail.com C Programming 14 11-16-2006 07:51 PM
OT: Number Nine, Number Nine, Number Nine FrisbeeŽ MCSE 37 09-26-2005 04:06 PM
String to number conversion Mark Helm XML 0 03-05-2004 05:20 PM



Advertisments