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 2 of 2 — ← Prev page 1 [2]

#6907

Juha Nieminen ha scritto:
> 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.)

It's basically what I had done initially (see my previous thread). But I 
would prefer base B, where B is power of two, not of 10, to profit by 
all the possibile bits of the integer.

thanks

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

#6909

On 2011-06-19 07:13:27 -0400, Anonymous said:

> 
> It's basically what I had done initially (see my previous thread). But 
> I would prefer base B, where B is power of two, not of 10, to profit by 
> all the possibile bits of the integer.
> 

Use an unsigned int, and represent the values in base UINT_MAX + 1. 
That uses all the bits.

To convert a text string, just use the obvious <g> approach:

set the current value to 0
set the current position in the string to the leftmost character
while the character at the current position is in '0'..'9'
	multiply the current value by 10
	add the value represented by the digit to the current value
	move the current position one place to the right

Try it with pencil and paper a few times to get the feel of it.

-- 
  Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The 
Standard C++ Library Extensions: a Tutorial and Reference 
(www.petebecker.com/tr1book)

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

#6911

"Pete Becker" <pete@versatilecoding.com> wrote in message 
news:2011061911425631676-pete@versatilecodingcom...
> On 2011-06-19 07:13:27 -0400, Anonymous said:
>
>>
>> It's basically what I had done initially (see my previous thread). But I 
>> would prefer base B, where B is power of two, not of 10, to profit by all 
>> the possibile bits of the integer.
>>
>
> Use an unsigned int, and represent the values in base UINT_MAX + 1. That 
> uses all the bits.
>
> To convert a text string, just use the obvious <g> approach:
>
> set the current value to 0
> set the current position in the string to the leftmost character
> while the character at the current position is in '0'..'9'
> multiply the current value by 10
> add the value represented by the digit to the current value
> move the current position one place to the right
>
> Try it with pencil and paper a few times to get the feel of it.
>
> -- 

Ok say the string is something ridiculously large like 
345678912345678546789435678123432567664334343457788933333331

I make that 60 chars long. So how do we calculate the first UINT value?
Normally we would need to calculate:
3*10^59 % UINT_MAX+1

The above can be calculated by doing a decimal shift on the massive number, 
and then multiplying the result so if we shift the massive number 50 places 
to the right we need to multiply the reuslt by the amount shifted, 10^50. 
For example:

2000 /8 =250;
2/8 = 0.25 * 10^3 //shifted only 3 places

But problem is we cannot multiply UINT_MAX * 10^50.
We lose precision if we divide away all our integers because we have yet to 
calculate the remainder, so we need to keep the MAX_RADIX small yet large 
enough to hold a massive integer without needing a million vector elements.
Then we still have long long for doing integer arithmetic without losing too 
much precision.
That would require a vector of size 26 to store the massive 60 digit 
integer.
64bit int is about 19 decimal digits long , so any string with more digits 
than this will need to implement something like the decimal shift algorithm 
I mentioned. But if its to be portable you cannot even expect that 64bit 
int.

Maybe I am missing some other way of doing this, I am not sure in your 
explanation where you say:
"set the current value to 0"
you lose me. The current value of what?
Can you maybe post a simple example?

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

#6912

Pete Becker ha scritto:
> On 2011-06-19 07:13:27 -0400, Anonymous said:
> Use an unsigned int, and represent the values in base UINT_MAX + 1. That 
> uses all the bits.
> 
> To convert a text string, just use the obvious <g> approach:
> 
> set the current value to 0
> set the current position in the string to the leftmost character
> while the character at the current position is in '0'..'9'
>     multiply the current value by 10
>     add the value represented by the digit to the current value
>     move the current position one place to the right
> 
> Try it with pencil and paper a few times to get the feel of it.

I don't think the algorithm you are describing can use all the bits 
available. As I said in my previous thread, the algorithm you are 
talking about, which is similar to the one I wrote initially, can 
represent the number in base B, where int B is a power of 10. Since the 
base it's a power of 10, it cannot profit by all the available bits in 
the integer. In other words:

10^std::numeric_limits<unsigned int>::digits10 -1 < 
2^std::numeric_limits<unsigned int>::digits - 1,

on my architecture:
10^9-1 < 2^32-1,
999999999 < 4294967295,

which is about two bits lost.

Below is the actual algorithm again:

#include <vector>
#include <limits>
#include <string>

typedef unsigned long Bitset; // the more is sizeof() , the more math 
ops are fast
static const int DGTS = std::numeric_limits<Bitset>::digits10;

std::vector<Bitset> f(const char* p = 0) {
     std::vector<Bitset> module;
     size_t l = std::string(p).length();
     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);
     }
     return module;
}

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

#6913

On 2011-06-19 17:06:36 -0400, Anonymous said:

> Pete Becker ha scritto:
>> On 2011-06-19 07:13:27 -0400, Anonymous said:
>> Use an unsigned int, and represent the values in base UINT_MAX + 1. 
>> That uses all the bits.
>> 
>> To convert a text string, just use the obvious <g> approach:
>> 
>> set the current value to 0
>> set the current position in the string to the leftmost character
>> while the character at the current position is in '0'..'9'
>> multiply the current value by 10
>> add the value represented by the digit to the current value
>> move the current position one place to the right
>> 
>> Try it with pencil and paper a few times to get the feel of it.
> 
> I don't think the algorithm you are describing can use all the bits 
> available. As I said in my previous thread, the algorithm you are 
> talking about, which is similar to the one I wrote initially, can 
> represent the number in base B, where int B is a power of 10. Since the 
> base it's a power of 10, it cannot profit by all the available bits in 
> the integer.

No, the 10 here is the base of the input. The algorithm I describe is 
simply interpreting a text string that uses base 10 to describe a 
numeric value (extending the algorithm to handle additonal bases is 
left as an exercise). The base B is whatever you use to implement your 
high precision math. Those two bases are independent of each other.

-- 
  Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The 
Standard C++ Library Extensions: a Tutorial and Reference 
(www.petebecker.com/tr1book)

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

#6914

"Anonymous" <anonymous@no.net> wrote in message 
news:itlocr$ocl$1@speranza.aioe.org...
> Pete Becker ha scritto:
>> On 2011-06-19 07:13:27 -0400, Anonymous said:
>> Use an unsigned int, and represent the values in base UINT_MAX + 1. That 
>> uses all the bits.
>>
>> To convert a text string, just use the obvious <g> approach:
>>
>> set the current value to 0
>> set the current position in the string to the leftmost character
>> while the character at the current position is in '0'..'9'
>>     multiply the current value by 10
>>     add the value represented by the digit to the current value
>>     move the current position one place to the right
>>
>> Try it with pencil and paper a few times to get the feel of it.
>
> I don't think the algorithm you are describing can use all the bits 
> available. As I said in my previous thread, the algorithm you are talking 
> about, which is similar to the one I wrote initially, can represent the 
> number in base B, where int B is a power of 10. Since the base it's a 
> power of 10, it cannot profit by all the available bits in the integer. In 
> other words:
>
> 10^std::numeric_limits<unsigned int>::digits10 -1 < 
> 2^std::numeric_limits<unsigned int>::digits - 1,
>
> on my architecture:
> 10^9-1 < 2^32-1,
> 999999999 < 4294967295,
>
> which is about two bits lost.
>
> Below is the actual algorithm again:
>
> #include <vector>
> #include <limits>
> #include <string>
>
> typedef unsigned long Bitset; // the more is sizeof() , the more math ops 
> are fast
> static const int DGTS = std::numeric_limits<Bitset>::digits10;
>
> std::vector<Bitset> f(const char* p = 0) {
>     std::vector<Bitset> module;
>     size_t l = std::string(p).length();
>     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);
>     }
>     return module;
> }
>

You do not use Bitset to its full capactiy by limiting it on digits10. For 
example a 8 bit char can represent  a value range of 0...255 but limiting it 
with digits10 it can only represent 0..99.
Imagining your Bitset was a byte for easy counting:
If you get two '1' chars your byte is full with its maximum int value of 
11(restricted by digits10). You would have used less than 5% of its 
potential 255 value. You could have squeezed 4 or 5 chars into that byte 
instead of two.

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

#6915

"Paul" <pchristor@yahoo.co.uk> wrote in message 
news:3nvLp.10417$J65.5498@newsfe14.ams2...
>
> "Anonymous" <anonymous@no.net> wrote in message 
> news:itlocr$ocl$1@speranza.aioe.org...
>> Pete Becker ha scritto:
>>> On 2011-06-19 07:13:27 -0400, Anonymous said:
>>> Use an unsigned int, and represent the values in base UINT_MAX + 1. That 
>>> uses all the bits.
>>>
>>> To convert a text string, just use the obvious <g> approach:
>>>
>>> set the current value to 0
>>> set the current position in the string to the leftmost character
>>> while the character at the current position is in '0'..'9'
>>>     multiply the current value by 10
>>>     add the value represented by the digit to the current value
>>>     move the current position one place to the right
>>>
>>> Try it with pencil and paper a few times to get the feel of it.
>>
>> I don't think the algorithm you are describing can use all the bits 
>> available. As I said in my previous thread, the algorithm you are talking 
>> about, which is similar to the one I wrote initially, can represent the 
>> number in base B, where int B is a power of 10. Since the base it's a 
>> power of 10, it cannot profit by all the available bits in the integer. 
>> In other words:
>>
>> 10^std::numeric_limits<unsigned int>::digits10 -1 < 
>> 2^std::numeric_limits<unsigned int>::digits - 1,
>>
>> on my architecture:
>> 10^9-1 < 2^32-1,
>> 999999999 < 4294967295,
>>
>> which is about two bits lost.
>>
>> Below is the actual algorithm again:
>>
>> #include <vector>
>> #include <limits>
>> #include <string>
>>
>> typedef unsigned long Bitset; // the more is sizeof() , the more math ops 
>> are fast
>> static const int DGTS = std::numeric_limits<Bitset>::digits10;
>>
>> std::vector<Bitset> f(const char* p = 0) {
>>     std::vector<Bitset> module;
>>     size_t l = std::string(p).length();
>>     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);
>>     }
>>     return module;
>> }
>>
>
> You do not use Bitset to its full capactiy by limiting it on digits10. For 
> example a 8 bit char can represent  a value range of 0...255 but limiting 
> it with digits10 it can only represent 0..99.
> Imagining your Bitset was a byte for easy counting:
> If you get two '1' chars your byte is full with its maximum int value of 
> 11(restricted by digits10). You would have used less than 5% of its 
> potential 255 value. You could have squeezed 4 or 5 chars into that byte 
> instead of two.
>
Err actaully you couldn't get anymore than 3 chars if you are not converting 
it to a higher base..

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

#6924

Juha Nieminen <nospam@thanks.invalid> wrote:
>  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).

  Btw, this doesn't work if adding the next digit to the value would overflow
the variable, so it can't be used if what you want is to use all the bits in
an int as the modulo.

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

#6997

[Multipart message — attachments visible in raw view] — view raw

Anonymous writes:

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

No, I don't think anyone would want to do you homework assignment for you,  
for free.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web