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

Groups > comp.lang.c++ > #6887 > unrolled thread

Conversion of a number from string to vector<int>

Back to article view | Back to comp.lang.c++

Contents

  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

Page 1 of 2  [1] 2  Next page →

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

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.

[toc] | [next] | [standalone]

#6892

"Anonymous" <anonymous@no.net> wrote in message 
news:itip2s$nkn$1@speranza.aioe.org...
> 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/clibrary/cstdlib/atoi/

HTH

[toc] | [prev] | [next] | [standalone]

#6898

> There is a function called atoi that may help you.
> http://www.cplusplus.com/reference/clibrary/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.

[toc] | [prev] | [next] | [standalone]

#6899

On 6/18/2011 5:55 PM, Anonymous wrote:
>> There is a function called atoi that may help you.
>> http://www.cplusplus.com/reference/clibrary/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+precision+integer+C%2B%2B+conversion+from+string

V
-- 
I do not respond to top-posted replies, please don't ask

[toc] | [prev] | [next] | [standalone]

#6902

Paul <pchristor@yahoo.co.uk> 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/clibrary/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.)

[toc] | [prev] | [next] | [standalone]

#6904

"Juha Nieminen" <nospam@thanks.invalid> wrote in message 
news:4dfd93f0$0$2848$7b1e8fa0@news.nbl.fi...
> Paul <pchristor@yahoo.co.uk> 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/clibrary/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?

[toc] | [prev] | [next] | [standalone]

#6906

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

[toc] | [prev] | [next] | [standalone]

#6908

"Anonymous" <anonymous@no.net> wrote in message 
news:itkig0$ook$1@speranza.aioe.org...
> 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);
>         }
> // ...
>     }
> }


TBH I am still not 100% sure about your problem. I don't think this will 
solve your porblem but is it the sort of thing you mean but using bigger 
integers?

#include <iostream>
#include <vector>
#include <math.h>

std::vector<unsigned> numbers(std::string str, double r){
 std::vector<unsigned> v;
 std::string::iterator it;
 unsigned int temp=0;
 int power=str.length()-1;
 double dec=10;

 for (it=str.begin(); it<str.end(); it++, --power){
  temp += (*it&15)*pow(dec,power);
 }
 while(temp){
  v.push_back(temp%(int)r);
  temp = temp/r;
 }
 return v;
}

int main(){
 std::string str = "253";
 double radix = 127;
 std::vector<unsigned> v = numbers(str, radix);

 for(int i=0; i< v.size(); i++){std::cout<< v[i]<<std::endl;}
}


But instead of taking a number like "253" you want to handle massive 
integers which my temp variable wouldn't have the capacity for?

[toc] | [prev] | [next] | [standalone]

#6910

Paul ha scritto:
> But instead of taking a number like "253" you want to handle massive 
> integers which my temp variable wouldn't have the capacity for?

Yes, in your example temp might overflow with enough big integers

[toc] | [prev] | [next] | [standalone]

#6923

Paul <pchristor@yahoo.co.uk> wrote:
> double dec=10;
> 
> for (it=str.begin(); it<str.end(); it++, --power){
>  temp += (*it&15)*pow(dec,power);
> }

  You are using doubles to handle integers? Have you ever programmed in
a C family of languages? Do you understand the inherent rounding problems
associated with floating point values? (This is especially egregious since
the problem is solvable with integers, and the solution isn't any more
complicated.)

[toc] | [prev] | [next] | [standalone]

#6935

"Juha Nieminen" <nospam@thanks.invalid> wrote in message 
news:4dfee4dd$0$2831$7b1e8fa0@news.nbl.fi...
> Paul <pchristor@yahoo.co.uk> wrote:
>> double dec=10;
>>
>> for (it=str.begin(); it<str.end(); it++, --power){
>>  temp += (*it&15)*pow(dec,power);
>> }
>
>  You are using doubles to handle integers? Have you ever programmed in
> a C family of languages? Do you understand the inherent rounding problems
> associated with floating point values? (This is especially egregious since
> the problem is solvable with integers, and the solution isn't any more
> complicated.)
>


This code was a very rough draft to ask anonymous if this is the kind of 
behaviour he was looking for. Again you are fast to criticise me but you 
have posted nothing yourself. 

[toc] | [prev] | [next] | [standalone]

#6922

Paul <pchristor@yahoo.co.uk> wrote:
> He seems to be trying to convert a string to an int,

  No, he isn't. He is trying to convert a string containing a very large
(ascii representation of an) integer into a set of ints, which is something
atoi() won't do (nor can you easily even use it to implement the task in
question). If you tried to use atoi() for this, if the string represents
an integer larger than can fit in an int, he will get an incorrect answer.

> What is incompetent about trying to provide a helpfull suggestion?

  Because it was not helpful. atoi() cannot be used to solve the problem.
If you tried to give us some actual code you would see it yourself.

[toc] | [prev] | [next] | [standalone]

#6933

"Juha Nieminen" <nospam@thanks.invalid> wrote in message 
news:4dfee42a$0$2831$7b1e8fa0@news.nbl.fi...
> Paul <pchristor@yahoo.co.uk> wrote:
>> He seems to be trying to convert a string to an int,
>
>  No, he isn't. He is trying to convert a string containing a very large
> (ascii representation of an) integer into a set of ints, which is 
> something
> atoi() won't do (nor can you easily even use it to implement the task in
> question). If you tried to use atoi() for this, if the string represents
> an integer larger than can fit in an int, he will get an incorrect answer.
>
>> What is incompetent about trying to provide a helpfull suggestion?
>
>  Because it was not helpful. atoi() cannot be used to solve the problem.
> If you tried to give us some actual code you would see it yourself.
>
I don't see any code coming from your direction.

[toc] | [prev] | [next] | [standalone]

#6937

On 06/20/11 06:09 PM, Juha Nieminen wrote:
> Paul<pchristor@yahoo.co.uk>  wrote:
>> He seems to be trying to convert a string to an int,
>
>    No, he isn't. He is trying to convert a string containing a very large
> (ascii representation of an) integer into a set of ints, which is something
> atoi() won't do (nor can you easily even use it to implement the task in
> question). If you tried to use atoi() for this, if the string represents
> an integer larger than can fit in an int, he will get an incorrect answer.
>
>> What is incompetent about trying to provide a helpfull suggestion?
>
>    Because it was not helpful. atoi() cannot be used to solve the problem.
> If you tried to give us some actual code you would see it yourself.

Even in C, atoi() should be avoided in favour of the strtol() family.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#6939

"Ian Collins" <ian-news@hotmail.com> wrote in message 
news:968gfuFsmeU5@mid.individual.net...
> On 06/20/11 06:09 PM, Juha Nieminen wrote:
>> Paul<pchristor@yahoo.co.uk>  wrote:
>>> He seems to be trying to convert a string to an int,
>>
>>    No, he isn't. He is trying to convert a string containing a very large
>> (ascii representation of an) integer into a set of ints, which is 
>> something
>> atoi() won't do (nor can you easily even use it to implement the task in
>> question). If you tried to use atoi() for this, if the string represents
>> an integer larger than can fit in an int, he will get an incorrect 
>> answer.
>>
>>> What is incompetent about trying to provide a helpfull suggestion?
>>
>>    Because it was not helpful. atoi() cannot be used to solve the 
>> problem.
>> If you tried to give us some actual code you would see it yourself.
>
> Even in C, atoi() should be avoided in favour of the strtol() family.
>
I don't know I have never used it, does it include isdigit infunction 
checking and stuff.
I learned how to mask a numeric char many years ago. I have never needed to 
use anything else.

I see some people are using the subtraction of char '0' technique, but this 
seems a bit weird to me as chars are not supposed to behave like that..
IIRC there is something in the standard about the chars '0' - '9' having 
special pirvaleges with arithmetic operators.
Does the following char arithmetic work?

'4'  *  '2'

Will give us an integer value of 8? Sorry too lazy to check, I m having my 
morning tea :)

[toc] | [prev] | [next] | [standalone]

#6978

"Paul" <pchristor@yahoo.co.uk> writes:

> I see some people are using the subtraction of char '0' technique, but
> this seems a bit weird to me as chars are not supposed to behave like
> that..

Like what?
The char type is an integral type. You can subtract them just fine.

> IIRC there is something in the standard about the chars '0' - '9'
> having special pirvaleges with arithmetic operators.

I doubt that.

> Does the following char arithmetic work?
>
> '4'  *  '2'

No, unless you want the result to be 2600.

> Will give us an integer value of 8? Sorry too lazy to check, I m
> having my morning tea :)

Not 8, no.

/L
-- 
Lasse Reichstein Holst Nielsen
 DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
  'Faith without judgement merely degrades the spirit divine.'

[toc] | [prev] | [next] | [standalone]

#6979

"Lasse Reichstein Nielsen" <lrn.unread@gmail.com> wrote in message 
news:7h8gz0vr.fsf@gmail.com...
> "Paul" <pchristor@yahoo.co.uk> writes:
>
>> I see some people are using the subtraction of char '0' technique, but
>> this seems a bit weird to me as chars are not supposed to behave like
>> that..
>
> Like what?
> The char type is an integral type. You can subtract them just fine.
>
>> IIRC there is something in the standard about the chars '0' - '9'
>> having special pirvaleges with arithmetic operators.
>
> I doubt that.
>
>> Does the following char arithmetic work?
>>
>> '4'  *  '2'
>
> No, unless you want the result to be 2600.
>
>> Will give us an integer value of 8? Sorry too lazy to check, I m
>> having my morning tea :)
>
> Not 8, no.
>
AH ok I see it now , sorry i misunderstood. 

[toc] | [prev] | [next] | [standalone]

#6897

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

[toc] | [prev] | [next] | [standalone]

#6903

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.)

[toc] | [prev] | [next] | [standalone]

#6905

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c++

csiph-web